这场因为主办方出包所以不算分
七题里面我写了 ABD 三题
放弃 C 改去写 D 写完没多久就发现公告不算分了
E 想了一下没想出来觉得麻烦就跑去洗澡了
https://codeforces.com/contest/1780
A. Hayato and School
加起来是奇数有两种可能
奇奇奇或偶偶奇
B. GCD Partition
只需要考虑 k = 2 的情况
假如 k >= 3 是最佳解，也就是
m := gcd(b_1, b_2, ..., b_k)
有最大值，则考虑
m' := gcd(b1, b_2 + ... + b_k)
因为 b_2 + ... + b_k 还是会被 m 整除
所以 m' >= m，因此只需要考虑 k = 2 的情况
O(n) 从左到右找分割点即可
C. Bon appetit!
这题还是卡了我一阵子的
主要是我反复检查我题叙到底有没有看错
不然那个 NP-complete 感都要穿出萤幕了
就只差现场造个 reduction 出来
有快五千人写出来(假解)让人很疑惑
D. Bit Guessing Game
这题很有趣，是 interactive 问题
有另一支程式和你的程式互动
也就是你拿到的输入会受到你之前的输出影响
题目是猜数字，会告诉你以二进制表示时有几个 1
你可以选择减去某个数字，减完之后还是回答你有几个 1
不过如果扣到负的会直接输
N <= 10^9 配上必须在 30 次以内猜出来
感觉就在暗示一次要能找出一个 bit
方法是减去 1 可以让最右端的 1 变成若干 1
像 101000 - 1 = 100111
根据数量差距就能知道最右边的 1 在什么位置
只要记得每一轮要把上轮造出的 1 也一起扣掉就好