CodeChef 是印度一个类似 Codeforces 的网站
也是一场会有上万人比的大型网站
这次是第一次写他们的比赛
比赛分成四个等级 div1~4
因为我积分是 0 所以只能去 div4
被迫写了一堆连水题都算不上的题目
好在这场比完之后分数就到 div2 了
不同 div 之间还是会有很多共同的题目
像 div3 少了 div4 的前两题 但比 div4 又多了一题更难的
虽然这题并没有 div3 的人写出来
看起来实际上 div4 前排的比 div3 要强
应该都是刚创帐号的人
这次有八题，八题都有写出来
排在 div4 里的第 4 名
没有 penalty 所以爽传就传
我觉得不太好就是了
https://i.imgur.com/gLOglBm.png
P1 TAXSAVING
给 X, Y 要你计算 X - Y
这也太烂了 = =
P2 Profit Increment
给 X, Y 计算 Y + X / 10
这两题都是国小数学应用题加第一堂程式课的等级
P3 Two Ranges
给两个范围 [a, b] 和 [c, d] 问联集有多大
分重叠和不重叠的 case 就可以了
P4 Three Powers of Two
给一个以二进制表示的数字字串(长度 <= 2e5)
问是否能够表示成恰好三个二的次方数的和
corner case 题，有 > 3 个 1 会失败
恰 3 个会成功
恰 2 个会成功 (大的那个以小一位的两个表示)
恰 1 个必须 >= (100)_2 才能以两个小二位及一个小一位构成
恰 0 个会失败
P5 Prefix Ones
给一个只以 01 组成的字串
要在移除一个 substring (可空) 后开头是连续的 1 越长越好
其实就是原本开头连续 1 的长度，
再加上这之后最长的连续的 1 的个数
P6 Equal Hamming Distance
https://www.codechef.com/START75D/problems/EQUALHAMMING
从这题开始像平常会写到的题目
如果 A[i] = B[i] 则不管选什么都不会影响差距
所以可能性直接乘二
假设 I_1, I_2, ..., I_k 都能使 A[I_i] =/= B[I_i]
如果 k 是奇数则不可能成功，必须要让选 A 或 B 的数量一致
所以会是 k!/(k/2)!/(k/2)!
赶快复制以前写过的乘法反元素
最后乘回 2^{A[i]=B[i]的个数} 就好
P7 Chefs Favourite Function
https://www.codechef.com/START75D/problems/CHEFFFUNC
可以证明 f(x) 就是以二进制表示时 0 的个数
不过在这里我们只需要证明 f(x) <= log2(x) 就好
g(x) 比较重要，可以发现是以下的数列
1, 3, 2, 7, 6, 5, 4, 15, ...
重点是要去证明
g(2^k) = 2^{k+1} - 1
g(2^k+i) = g(2^k) - i, for 0 <= i < 2^k
因为 x <= 10^9 让我们有 f(x) <= 32
所以只要找到 [L, R] 范围内最大的 2^k
再去检查 [2^k, 2^k+32] 就好， O(log^2 x)
P8 Minimum Replacement
https://www.codechef.com/START75D/problems/MISREP
假设 A[i] <= A[j]
会把 A[i], A[j] 变成 0, A[j] - A[i]
最后一个人一定会是每个人乘上 +1 或 -1 的总和
因此，如果存在解让他是 0，把负的移项
就会变成两群和一样的 subset (联集是整个 A)
而如果存在两群和一样的切割法
则借由不断挑两群各一个非零的成员来做就好
因为每次会减少一样的值所以两边和永远一样
所以这是经典的 partition problem 问题，属于 NP-complete
但因为 A_i <= 300，可以很简单的用 DP
来达到 O(N*NK) psuedo-polynomial
N 和 K 都 <= 300 所以这样就可解了
_____________
我觉得体验没有到很好，可能会再比个几场试试水温