幽默的一场机考，最终360/400，TAT……

金牌学长の疑惑
金牌学长の嘲讽
（来自金牌学长の嘲讽）

个人体感红+橙+橙+黄（cf1300-1400），前三题都是一次就AC，除了第一题稍微犯病拖了点时间，T2T3都拿到了一血，大约30分钟就都过了

考试前半小时感觉比较紧张，尤其是看到T3的题面一开始发现有个地方没法确定而且不知道怎么问老师的时候，但好在按照自己的理解写完代码交上去一发就A了，于是笑看打ACM的同学被单防一直WA70（乐）

给T4留了1个小时的时间，花20分钟推了个式子，写完测样例发现能过，高兴地交了一发，喜提WA20，怀疑是二分写挂了但死活找不出错，后来还干了各种nt操作，比如1e5还是1e6的数据表不直接写生成代码，非要先生成数据后复制进程序，喜提代码长度限制等等。。。

以下是回忆版的题目和题解，因为咕咕得太久，直到期末才开始写，有些细节不太记得了TAT

其中一些题目特意保留了一些原有的巧（chou）妙（xiang）叙述方式，建议先按照正常的机考时长（1.5h）自己尝试模拟一次，有助于培养考试时的手感。

A. 卷王Alice

Alice热爱学习，几乎每天都要去图书馆读书。由于她天天这么做，所以图书馆里的书已经被她看掉许多了！

现在，她想整理书架，把书架上编号在l到r之间的书去掉（包括l和r）——因为这些书她都已经读过了。你需要告诉她，她需要搬走哪些书，以及剩下的书的编号。

输入格式:
第一行一个整数n，表示书架上有n本书，1 <= n <= 1e7；

第二行两个整数l和r，表示需要去掉的书的编号范围。

第三行n个整数，a1,a2…an，表示书架上书籍的编号，其中1 <= ai <= n；

输出格式:
第一行一个整数，表示搬走的书的数量；

第二行为用空格分隔的整数，表示书架上剩下的书的编号。

样例

输入

8
3 6
1 2 3 4 5 6 7 8

输出

4
1 2 7 8

B. 图书管理

由于像Alice一样的卷王实在太多了，图书管理员Bob快要忙不过来了！

无奈之下，他只好邀请你帮他写一个简单的图书管理系统，具体要求如下：

  1. 命令R表示有人前来借阅书籍，Bob需要获取书架上最新的图书书名并借给他；如果书架上没有书，则输出警告EMPTY!

  2. 输入一个由英文字母构成的字符串（中间不含空格、特殊符号），表示图书馆新购入一本书籍，Bob需要将这本书放在书架上

输入格式：
第一行一个整数n，表示一共有n条指令；

接下来n行，每行可能是单个字母R，表示借出操作；或者是一个完全由英文字母构成的字符串s，表示购入的书籍名称

输出格式：
对于每个输入R，如果书架上有书，输出最新的图书名，否则输出一行EMPTY!。

样例：

输入1：

5
R
HARRYPOTTER
R
R
DATASTRUCTURE

输出1：

EMPTY!
HARRYPOTTER
EMPTY!

输入2：

7
TheWayToAK
AbnormalPsychology
LiangZiSiWei
R
R
R
R

输出2：

LiangZiSiWei
AbnormalPsychology
TheWayToAK
EMPTY!

C.常识拍卖

在ACM生涯中获得过多枚金牌的carvingfate和不愿透露姓名的学姐在退役后选择了开一家拍卖场。由于非常热爱算法竞赛，所以作为拍卖场主人的他们为这里设计了一些独特的规定，如果你想要参与他们举办的拍卖，一定要仔细阅读规则！

新一轮的拍卖要开始了！这一次的拍卖品是一块价值连城的宝石，拍下它的人将获得至尊の算法之力，不仅能轻松AK各种比赛，还能风淡云清地告诉其他人：这只不过是常识罢了！（可恶，又被装到了！）

参与拍卖的人群自觉地在会场外排起了长队，他们每个人都有一个独特的编号，同时手里举着一个牌子，表示自己的出价。每次新来排队的人会先看一眼队首手里举着的牌子，如果自己的出价低于队首，则会直接离开，不加入队伍。

作为拍卖场的主人，carvingfate拥有一些特权，比如每次他按下2，排在队首的人将提前进入会场，如果没有人在排队，则当作无事发生~

共有m个时间点，在某个时间点上，可能是carvingfate让队首的人进入会场，也有可能是新的竞拍者来到会场。在m个时间点都结束后，在排队的人会依次进入会场开始竞拍。

拍卖的规则是：价高者得，如果有多个人出价相同，则遵循先到先得原则。

carvingfate想考考你，是谁最终拍下了这枚宝石呢？请你算出买家的编号，以及宝石成交时的价格。

输入格式：

第一行一个字母m，表示共有m个时间点，其中1 <= m <= 1000000。

接下来m行，如果是一个数字2，代表carvingfate请队首进入了会场；如果是一个数字1，紧接着是两个由空格分割的数字x y，表示编号为x的拍卖者来到了会场，他的出价为y，1 <= x,y <= 100000000

输出格式：

对于每个指令2，输出一行一个数字，表示当下进入会场的拍卖者编号

最后输出一行两个数字x y，分别表示最终买家的编号，以及成交时的价格。

样例：

输入1：

5
1 1 3
1 2 4
1 3 5
2
1 4 3

输出1：

1
3 5

输入2：

8
1 1 4
1 3 2
2
1 4 3
1 2 5
2
2
2

输出2：

1
3
4
2
2 5

D. 谁爱吃麦当劳

结束了一天的敲代码后，天色已晚，大门落锁，助教学长总是会选择从枣阳路门翻墙而出，去麦当劳整点薯条（注：因为理科大楼离枣阳路门最近）

为了不必天天翻墙，学长研究了大门的密码，得到密码是一个n*n的二维矩阵中第k小的数，而这个矩阵a满足a[i][j] = i*i + j*j + i*j + 114514*(i-j)

现在，机智的学长已经完全掌握了密码，他邀请你今晚一起去麦当劳整点薯条，请你速速想出答案赴约，否则就要v他50请他吃下周的肯德基~

输入格式：

一行两个数字n k，表示矩阵的行列数，以及k的大小，1 <= n <= 5e4; 1 <= k <= n*n

输出格式：

一个数字，表示该矩阵中第k小的数

样例：

输入1：

2 1

输出1：

-114507

输入2：

10 5

输出2：

-801495

————————————题目结束————————————

 
 
 
 
 

题解

A. 卷王Alice

数组模拟的签到题，熟练的同学可以在10分钟（进阶要求应该是5分钟）之内完成

需要稍微注意一下两点文字游戏：

  1. 去掉的是“编号大小”在l和r之间的书，而不是“位置”（考试刚开始脑子不清醒，因为这个卡了几分钟）
  2. 注意输出的分别是“搬走了几本书”，以及“剩下的是哪几本书”（考试时确实只给了一个样例，而且正好8-4=4，坐在我旁边的同学因为这个破防了一个小时）

写代码应该没什么难度，参考如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	int book;
	int cnt;
	vector<int> ans;
	int l,r;
	cin >> l >> r;
	for (int i = 1;i <= n;i++) {
		cin >> book;
		if (book >= l && book <= r) {
			cnt++; //如果符合编号在l到r之间，说明这本书要被搬走，计数器+1
		} else {
			ans.push_back(book); //否则这本书要被保留
		}
	}
	cout << cnt << endl;
	for (int b:ans) {
		cout << b << " "; //输出要被保留的书的编号
	} 
	return 0;
}

B. 图书管理

看到“最新”，应该可以想到使用栈。要求可以被转化为简单的出栈和入栈操作，不过编码上可能存在一定困难，因为C语言的字符串比较难搞，以及作为新手，手写栈容易各种出错

简单的解决方案是使用C++的STL速通，毕竟是在机考，还是怎么快怎么来

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	stack<string> books;
	string ope,book;
	while (n--) {
		cin >> ope;
		if (ope == "R") {
			if (!books.empty()) {
				cout << books.top() << endl;
				books.pop();
			} else {
				cout << "EMPTY!" << endl;
			}
		} else {
			books.push(ope);
		}
	}
	return 0;
}

一位高水平的同学使用了类似ope[0] == 'R'的语句判断当前是借阅指令还是书名，需要注意的是书名同样可能是R开头的（乐），在此警示后人

C.常识拍卖

问题建模：维护一个队列作为“排在场外”的队伍，一个队列或者一个最大值表示“场内”的情况，每次有新人进队，需要先和场外队首比较决定是否入队；
每次2操作，将场外队首移入场内

比较容易出错的点在于：“在m个时间点都结束后，在排队的人会依次进入会场开始竞拍”，也就是说，最后无论是场外还是场内的人都能参加拍卖
一些同学在考试的时候没有看到这句话，以为只有进入拍卖场才能参加拍卖导致WA70，我做题的时候其实也有点不确定，忘了最后是因为扫到了这个条件，还是靠一点“揣测出题人意图”的直觉写对了

至于这道题为什么现在叫常识拍卖：（原题不叫这个名字，具体是啥我们也忘了）

好吧（摊手

写码时需要重点注意几点：

  1. 奇怪的输入方式（原题是不是这么输入其实我也有点忘了，但确实不太常规）
  2. 队列判空
  3. 用结构体或哈希表或元组维护拍卖者“出价”和编号两个信息
  4. 最后拍卖遵循“价高者得，同等价格先到先得”的原则
#include<bits/stdc++.h>
using namespace std;

int main() {
	int m;
	cin >> m;
	int ope,a,b;
	deque<int> q; //拍卖场外的队伍，使用了双端队列方便后面的遍历操作 
	map<int,int> money; //一个哈希表，表示编号为i的人的出价为money[i] 
	int maxn = 0; //维护单个变量作为“目前拍卖场内出价最高的人的出价”
	int person; //维护拍卖场内出价最高的人的编号 
	
	while (m--) {
		cin >> ope;
		if (ope == 2) {  //先输入2的情况，出队
			if (!q.empty()) {
				int p = q.front();
				cout << p << endl; //输出队首
				if (money[p] > maxn) { //比较“拍卖场内当前出价最高的人 ”和“新人”哪个出价更高 
					maxn = money[p];
					person = p;
				}
				q.pop_front(); //删除队首 
			} 
		} else { //先输入1的情况，说明后面还要输入两个数字 
			cin >> a >> b; 
			if (q.empty() || q.front() <= b) { //只有两种情况下才会加入队伍：队伍为空或者出价比队首高 
				money[a] = b;
				q.push_back(a); 
			}
		} 
	}
	
	for (auto p:q) { //遍历场外的队列 
		if (money[p] > maxn) {
			maxn = money[p];
			person = p;
		}
	} 
	
	cout << person << " " << maxn << endl;  
	return 0;
}

D. 谁爱吃麦当劳

一道实际上思维难度不大的经典二分题，但是考前听说“压轴题考推式子”，于是在打表找规律的歪路上一去不复返。。。

以下是考场上的错误思路：
考场上打了个10*10的表，惊喜发现如果把右上角的点看作第一条对角线，左下角的点看作最后一条对角线，把所有对角线头尾相接，得到的序列是升序的
于是就可以然后二分求k在第m条对角线上，如果是上三角，x = k - m*(m-1)/2，y = n + x - m
不过考场上脑子一抽，忘记了还有上三角和下三角的区别，所以后面毫无意外地WA了，，，一个小时调得头大还是没找到原因
后面讲题的时候，金牌学长认为这个方法有可能是对的，但是因为只打了10*10的表，数字特别大的时候可能并不遵循这个规律，所以还是寄了

以下是金牌学长给的官方题解：

算法步骤如下：

  1. 限定一个区间，比如[-1200,1200]
  2. 首先二分法，求在矩阵中，小于0（因为mid = (-1200 + 1200)/2）的元素个数，即对值域（答案）二分

假设j固定，在i的区间[0,正无穷]上，是一个单调递增函数，所以可以想到二分

所以求小于0的元素个数算法如下：

  1. 从1-N遍历每个j
  2. 对于每个j，对i进行二分，每次找到小于等于k的最大索引，累加得到答案

官方代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll INF = 0x3f3f3f3f3f3f3f;

ll m;
ll n;

ll Get(ll x,ll y) {
	return x*x + y*y + y*x + 114514*(x-y);
}

bool solve(ll x) { //枚举小于当前x的个数有几个 
	int tot = 0;
	for (int j = 1;j <= n;j++) { //枚举每一列 
		int l = 0,r = n+1;
		while (r - l > 1) {
			int mid = (l+r) >> 1;
			if (Get(mid,j) < x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		tot += l; //将满足的每列的行的个数相加 
	}
	return tot < m; //如果小于当前x的数是小于m的，说明是x太小了，还可以放大 
} 

int main() {
	scanf("%lld %lld",&n,&m);
	ll lb = -INF,ub = INF;
	while (ub-lb > 1) {
		ll mid = (lb+ub) >> 1;
		if (solve(mid)) {
			lb = mid;
		} else {
			ub = mid;
		}
	}
	cout << lb << endl;
	return 0;
}