华东师范大学“游族杯”全国高校程序设计网络挑战赛（2020.5）

——爬就爬，我自己能爬的，我最会爬了

开始之前先挂上比赛链接，题目下载链接和可能会有的官方题解的链接：

比赛链接：https://acm.ecnu.edu.cn/contest/273/
问题集（PDF）：官方下载或者备份下载
官方题解：官方下载或者备份下载

就不说结果了，说了实在是太丢人了

傻逼就傻逼，下面是这次的题目：

Amateur Chess Players

前面哔哔了一堆国际象棋但是结果和国际象棋没有任何关系（

8×8的棋盘上，摆着 n 个白子，m 个黑子；白子先动：操作可以消除一条直线上的所有的子，这个直线可以不是横平竖直对角线；问谁的子先销完。

签到题。

#include <iostream>

using namespace std;
using longs = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; string s;
    cin >> n;
    for (int i = 0; i < n; ++ i)
        cin >> s;
    cin >> m;
    for (int i = 0; i < m; ++ i)
        cin >> s;
    if (n <= m) cout << "Quber CC" << endl;
    else cout << "Cuber QQ" << endl;

    return 0;
}

读错题目属实害人，第一题必然不可能是计算几何。

Binary String

这是一个交互题，给人一种既视感感觉在某年区域赛见过差不多的题目：

程序构造了一个长度 n 的二进制字符串，您可以向交互机器发起 1024 次请求，格式如下：
? <binary string shorter than n> ：询问这个字符串是不是程序构造的字符串的子序列，是返回 1，否返回 0；如果询问格式不正确将返回 -1 并且 WA。
! <binary string with n bits> ：询问这个字符串是否是程序构造的字符串，交互机器将立刻退出并且返回评测结果。
交互程序会先输入字符串的长度 n，随后您可以进行询问，并且获得验证：切记您需要预留 1 次请求的机会用来提交答案，也就是询问最多 1023 次。n 小于 1000；

比较有趣，但是题目也不像上次那个交互题那样猜测次数提供了一个指示。

~~看了题解才发现原来这是所有的题目里官方难度评价最高的一个题目吗（~~

首先，因为是询问子串，使用二分的方法询问 0 或者是 1 的数量是很容易想到的，因为这两个数量是零和的，所以只需要询问其中一种就可以了；之后就是二进制字符串的一种惯用的猜测方法：向一种数字种插入另一种数字；因为子序列还是遵循了原序列的顺序的，所以可以一直向一个指定的数字的左侧插入另一个数字：这个过程也可以二分的；最后总复杂度是 O(nlogn)；

具体的说，我们假设有 n 个 0，m 个 1；我们向 0 中插入 1，需要使用这种方法来测试：

首先，我们将 n 个 0 摆放在一起，这一定是一个正确的子序列；
然后，我们从左向右遍历 0：在第 1 个 0 的左侧插入 1，这个插入的 1 的数量可以在 [0, m] 中二分；
找到插入数量 x 之后，尝试在第 1-2 个 0 之间插入 1，在 [0, m-x] 的范围内二分数量；
直到处理到 m - Σx = 0 或者处理完所有的 0 之后，将剩余的未使用 1 全部补在字符串的末尾；

这样就可以写出代码了。~~又是一个读错了题目然后xjb做的题目~~

1	代码 RE 了，正在调试中

事实证明这题目哪里有那么麻烦嘛== 都是读错了题目的锅（

Coronavirus Battle

一个图论题目。

有一个三维空间，其中有 n 个白细胞；病毒总会从 (-x, -y, -z) 的方向进攻：一个白细胞 (x, y, z) 可以存活，只有当存在一个白细胞 (x₀, y₀, z₀)，满足 x₀ ≤ x && y₀ ≤ y && z₀ ≤ z 且 x₀ < x || y₀ < y || z₀ < z 成立的时候；如果存在这样的细胞，那么这个细胞去世，其他细胞存活；否则，所有没有保护的细胞都将去世；
如果所有的白细胞都死了，那么游戏结束；你需要输出在游戏结束前病毒攻击的轮数，并输出一个数列 a：其中 ai 表示第 i 个白细胞存活的轮数。
输入的数据是白细胞个数 n ≤ 1e5，以及种子 k1，k2：可以用给定的随机数生成器生成这些白细胞的坐标，种子和生成的白细胞位置坐标的范围是 unsigned long long 的。

Decay of Signals

给一颗 n 个节点的无向树，每一个节点上有一个权值 ai，每一条边的长度为 1；假设从节点 u 到节点 v 的最短路，这样定义一条最短路径的“值”：
$s = \frac {Π_{i=1}^m a_{p_i}} {m}$
m 是这条最短路经过的边数， $p_i$ 表示这些边； $a_{p_i}$ 表示这些边在这条路径中的终点的权值，即 $a_u$ 没有被包含在其中；现在要求求出全树中这个 s 值最小的最短路，并且分数形式输出这个 s 值。

Even Degree

Find / -type f -or -type d

所以说为什么要多此一举呢（

给定 n 个字符串，描述了 n 个绝对路径；问在这个文件系统中存在的 *.eoj 文件的数量；
数据规模：n ≤ 1e5，绝对路径字符串的总长度不会超过 1e6

Geralt of Rivia

Heat Pipes

现在有一些温室和热管，热管的作用是保证它所连接的两个温室的温差等于 1 度；现在告诉你温室和热管的布局，要求你设计一种温度设定方法，让这些温室的温度可以覆盖一个区间内所有的温度（整数）。
一共有 t 组测试数据：每一组包含温室数量 n，热管数量 m，温度区间 [a, b]，以及用来描述热管情况的 m 行，每行包括两个整数，指明热管连接的两个温室。
数据规模：N ≤ 2000，M ≤ 50000，a ≤ b ≤ n；N, M 指的是所有测试用例的 n, m 的和

Idiotic Suffix Array

首先你需要了解后缀数组——当然不了解也不是做不了：

给了一个后缀数组的代码，可以用来生成后缀数组 SA；然后告诉你一个长度 n，告诉你一个数组 k，要求构造一个长度为 n 的仅由小写字母构成的字符串，根据它构造出的后缀数组满足 SA[k - 1] == 0；此外这个字符串的所有后缀中，第 k 个后缀的字典序排列最小。