Good Bye 2019

总结

# 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 去点,都是线性复杂度

上一篇:学习笔记_关系运算符


下一篇:Standard支付:为什么区块链对业务很重要