竞赛总览
CSDN 编程竞赛七十期：比赛详情 (csdn.net)
吐槽：前两个题目疑似忘记设置测试数据（这也是个老问题了）。其中第二题显示已通过，后来发现只有后两个出现过多次的题（第三题、第四题）能得分，体验很差。
竞赛题解
题目1、小张的手速大比拼
在很久很久以前，小张找到了一颗有 N 个节点的有根树 T，树上的节点编号在 1 到 N 范围内。他很快发现树上的每个节点 i 都有一个对应的整数值 V [i]。一个老爷爷对他说，给你一个整数 X，如果你能回答我的 M 个问题，我就给你购买一些零食。对于每个问题 Q [i]，请你找到在 T 中以节点 Q [i] 为根的子树中的所有节点中（包括 Q [i]），有没有两个节点 A、B（A != B）的值 V [A] ^ V [B] 的异或和为 X。如果有这样的两个节点， 请你输出 YES。否则输出 NO。
这道题无法通过任何测试点，不知道是博主个人原因还是其它问题。代码就不放了。
题目2、坐公交
公交上有N排凳子，每排有两个凳子，每一排的凳子宽度不一样。有一些内向和外向的人按照顺序上车。外向的人（0）只会选择没人的一排坐下。如果有很多排符合要求，他会选择座位宽度最小的坐下。内向的人（1）只会选择有人的一排坐下。如果有很多排符合要求，他会选择座位宽度最大的坐下。数据保证存在合理。输出每个人所在的排。
初始情况下，所有凳子都是空的。因此，第一个出现的人，类型一定为 0。类型为 0 的人会选择座位宽度最小的坐下，因此，读入所有输入数据之后，先为凳子排序，按凳子宽度升序排序。
再进一步分析，会发现类型为 1 的人选择有人的一排凳子坐下，而每排凳子只有两个。这意味着，对于这一排凳子而言，一定是类型为 0 的人先入座，然后类型为 1 的人再入座。凳子被坐满之后，由于没人下车，这排凳子会被占用，相当于消失了（因为之后的人无法再坐到上面了）。
类型为 1 的人的入座顺序取决于类型为 0 的人的入座顺序。例如，有 3 个类型为 0 的人入座，那么再来一个类型为 1 的人，他的选择范围仅限于这 3 个类型为 0 的人所在凳子编号之内。
类型为 1 的人的具体入座编号，不仅取决于类型为 0 的人的入座顺序，还取决于类型为 1 的人的选择方式。
如果选择座位宽度最小的坐下，与类型为 0 的人的入座顺序相同，那么可以用队列来处理；
如果选择座位宽度最大的坐下，与类型为 0 的人的入座顺序相反，那么可以用栈来处理。
#include <cstdio>
#include <algorithm>
#include <stack>
node data [100005];
int main () {
int n; scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
data [i].id = i; scanf ("%d", &data [i].width);
}
char c;
std::sort (&data [1], &data [1 + n], cmp);
std::stack<int> s; int p = 1; // p 表示类型为 0 的人应选择的凳子编号（这里指按凳子宽度排序之后的编号）
for (int i = n * 2; i >= 1; i--) {
scanf ("%c", &c);
if (c == '0') {
s.push (p);
printf ("%d", data [p].id);
p += 1;
} else {
int d = s.top ();
s.pop ();
printf ("%d", data [d].id);
}
if (i != 1) printf (" ");
}
return 0;
}参考代码如上所示。由于选择了使用逐个字符的方式来读入上车顺序，因此读入凳子宽度之后，还需要吃掉一个字符的换行符。
题目3、三而竭
一鼓作气再而衰三而竭。小艺接到一个任务，总任务量是n，但小艺总是喜欢把任务分开做。第一天，小艺能完成 x 份任务；第二天，小艺能完成 x / k 份任务；第 t 天，小艺能完成 x / (k ^ (t - 1)) 份任务。小艺想知道自己第一天至少完成多少才能完成最后的任务。
这里隐藏了一个要点：每天完成的任务都是整数份。
总任务量是 n，第一天能完成 x 份。如果 x = n，那么必定能够完成任务（只需 1 天即可完成任务）。
如果 x < n，不一定能够完成任务（每天能够完成的任务量会被除以 k，到一定天数之后，当天能够完成的任务量变为 0，此时如累计任务量不达标，则无法完成任务）。
只需要从 1 到 n 尝试，判断第一天完成对应任务量的任务，最终能不能完成整个任务即可。
#include <cstdio>
int main () {
int n, k; scanf ("%d %d", &n, &k);
int l = 1, r = n;
while (l < r) {
int m = (l + r) * 0.5;
int data = calc (m, k);
if (data < n) l = m + 1;
else if (data >= n) r = m - 1;
}
for (int i = l; i <= r; i++) {
if (calc (i, k) >= n) {
printf ("%d", i);
break;
}
}
return 0;
}参考代码如上所示。先二分确定大致范围，再精确查找。需要注意的是，在使用二分法缩小范围之后，右边界有可能为恰好无法完成任务的最大起始日任务量，因此精确查找范围需要扩大到 [l, r + 1]。
题目4、争风吃醋的豚鼠
对 N 个节点两两建边，不存在三个节点之间相互相连的情况（即 3 个节点连接成环）。那么，最多能建立多少条边？
之前出现过多次的题目，代码不放了。