总结

#	Name
A	Card Game standard input/output1 s, 256 MB
B	Interesting Subarray standard input/output2 s, 256 MB
C	Make Good standard input/output2 s, 256 MB
D	Strange Device standard input/output1 s, 256 MB
E	Divide Points standard input/output1 s, 256 MB
F	Awesome Substrings standard input/output8 s, 512 MB
G	Subset with Zero Sum standard input/output2 s, 256 MB
H	Number of Components standard input/output8 s, 256 MB
I	Xor on Figures standard input/output5 s, 256 MB

又是一年goodbye

3小时9个题，有现场赛内味了，虽然码量仍然符合cf风格，也依然只会写4个题

当场通过abcd、赛后通过efg

A 67879420

比较最大值即可

B 67885936

给一个序列，求任意一个子串满足极差不小于长度

显然如果有解，必然存在相邻两项的极差大于 1

C 67906974

给一个序列，求添加不超过 3 个数字使得 \(a_1 + a_2 + \dots + a_m = 2\cdot(a_1 \oplus a_2 \oplus \dots \oplus a_m)\)

显然这个序列是无用条件，其实只有异或和以及和是有用条件

相当于求 \(a+x=2\cdot(b \oplus x)\)

或\(a+x+y=2\cdot(b \oplus x \oplus y)\)

考虑如果 \(b\) 为 0，就是求 \(a+x=2 \cdot x\) ，即 \(x=a\) 即可

那么先用一个数使得 \(b\) 变为 0，即输出 \(b\) 即可

D 67922016

交互题

有一个无相同元素的序列，\(n,k,m\) 分别表示序列长度，询问区间大小和询问第 \(m\) 大（升序后第 \(m\) 个位置）

现在你不知道 \(m\) 和序列中任何一个数，可以询问不超过 \(n\) 次，每次会回答你答案的下标和大小，求 \(m\)

对于前 \(k+1\) 个数字进行询问，每次去掉其中某一个数字即可，共询问 \(k\) 次

对于其中最小的数（因为它会回答你数的大小）进行分析

由于没有比它更小的数，所以它必然是这 \(k+1\) 个数中第 \(m\) 大的数字，那么也就是说这 \(k+1\) 个数中比它小的数的数量为 \(m-1\)，比它大的数的数量为 \(k-m+1\)，那么有 \(k-m+1\) 次询问会回答这个数字，所以设它的出现次数为 \(x\)，答案为 \(m=k+1-x\)

E 68035235

\(n\) 个二维坐标整点，对其黑白染色，记两点之间的距离为欧几里得距离，记 \(set1\) 为黑黑和白白间的距离集合，\(set2\) 为黑白间距离集合，使得 \(set1 \and set2 = \emptyset\) 且 \(set1,set2\) 非空

首先对其中一个点作为坐标原点建系并重新计算坐标

那么可以将点按奇偶分为四类：
\[ a(0,0), b(0,1), c(1,0), d(1,1) \]
其中选择的原点为 \(a(0,0)\) 类，\(ab,ac,bd,cd\) 类间的距离的平方都为奇数，\(ad,cb,aa,bb,cc,dd\) 间距离平方都为偶数，所以染色为 \(ad\) 为黑色， \(bc\) 为白色即可

• 但是虽然 \(a\) 集合必不为空集，若 \(b,c\) 若都为空集：
  • \(aa,dd\) 间距离能被 4 整除 \(ad\) 间距离模 4 为 2，可以将 \(ad\) 染成不同的颜色
  • 若 \(d\) 也为空集，考虑将四个集合的坐标再缩小一倍重新求解，必然会出现奇数点

一开始还以为是 \(2-sat\) ，然后写了写没过样例

F 68040330

给一个 01 序列，求其中满足串中 1 的数量可以整除串长的子串数量

当子串 \((i+1, r)\) 满足 \(r - i == k \cdot (pre_r - pre_i)\) 时它是一个合法串，我们设置一个 \(T\)

• 对于 \(1\le k \le T\) 的串
  • \(i - pre_i \cdot k == r - pre_r \cdot k\) 所以只需要使用 map 储存前缀出现的 \(i - pre_i \cdot k\)，对于每个 \(r\) 加上它的答案即可，复杂度 \(O(n\cdot T)\)
• 对于 \(T < k\) 的串
  • \(pre_r-pre_i=\frac{r-i}{k}\)，故 \(pre_r-pre_i \le n/T\)，对于每一个起点离散化的计算后 \(n/T\) 个 1 即可，复杂度 \(O(n \cdot \frac{n}{T})\)

若选取 \(T\) 为 \(\sqrt{n}\)，整体复杂度为 \(O(n\sqrt{n})\)

注意如果第一部分使用 map 储存前缀会多出一个 \(log\) 复杂度，可以考虑适当减小 \(T\) 并用数组存储以减小复杂度

实际上直接开 \(n \cdot \sqrt{n}\) 的数组并不会超过内存，但是达到了 \(9\cdot 10^7\) 的数量级属实不敢尝试

使用减小 \(T\) 的方式反而会因为寻址更快达到更优的常数，经测验直接根号的运行时间 \(5s\) 左右，固定 \(T=150\) 的话运行时间答到了 \(2s\) 。本质不算一个好题，为了防止暴力的 \(O(n^2)\) 解法卡掉了一些常数

G 68036447

给一个序列 \(a\) ，其中每个数都满足 \(i-n\le a_i\le i-1\)

求一个和为 0 的子序列

这题是真的妙，就是对于每个数可以构造出： \(i \to a_i-i\) 两者和为 \(a_i\) 然后将 \(a_i-i\) 取反则 \(1 \le i-a_i \le n\) ，若对每个数都建这样一个单向边，则形成一张 \(n\) 个点，\(n\) 条边的图，必然存在环，环中所有点的和就是 0

求环可以直接 dfs(1) 搜出一个可行解，也可以暴力一点直接 topsort 去点，都是线性复杂度