ABCD 都打的可以,然而 E 的 +10 直接葬送了大概率过的 F1 ……
先猜了个 \(n-k+1\) 的结论,但是没有写搜索查正确性(事实上确实不正确),于是两次罚时,第一次是交互格式错了。
然后又猜了个 \(\min(n-k+1,(n-1)/(k-1))\) 的结论,过了几个小的搜索数据(\(n\le 6\))的,大一点的没跑,于是又两次罚时。
五分钟后发现 7 3
都跑不过去,立刻全部删掉重新想。想出来的解法是对的,但依然吃了五发罚时。
猜 \(n-k+1\) 的时候写了个搜索做对拍,因为玩的小样例次数都 \(\le n-k+1\),搜索设定了只会搜出来次数 \(\le n-k+1\) 的解,导致把 4 3
这种虽然两次不行,但是四次可以的情况判定为无解,再加上 5 2
这种确实是无解的,误以为 \(n,k\) 奇偶性不同就无解。
这个错误的判无解方式沿用到我的正确解法里面,吃了五发罚时才发现这个问题 ……
警示:猜结论最好能证明出来。猜结论至少跑个中等强度的数据。猜的结论测出错时,要立刻把所有基于这个结论的东西都视作未证明的东西,包括搜索。
下面记录一下 E 的正确解法。
题目转化为 \(n\) 个杯子,每次翻 \(k\) 个,要求全部翻面,最少几次。
考虑每个杯子被翻的次数 \(c_i\),有:\(2\not\mid c_i\)、\(\sum c_i=k\cdot times\),这是比较显然的。
因为每个杯子的地位是相同的,考虑构造一个 \(\{c_i\}\),记 \(sum=\sum c_i\),目标是让这个 \(c_i\) 满足上面两个条件的同时,让能达成 \(c\) 的操作次数最小。
对于一个序列 \(c\),显然要至少 \(\max c_i\) 次操作才可行(因为不能一次操作重复翻杯子)。因为 \(\dfrac{sum}{k}\) 是操作次数,所以必须有 \(\max c_i\le \dfrac{sum}{k}\) 才有可能可行。赛时直接数学直觉,猜这个也是充分条件过了。
如果这个结论成立,目标就是构造一个 \(c\) 满足:\(2\not\mid c_i\)、\(k\mid\sum c_i\)、\(\max c_i\le \dfrac{\sum c_i}{k}\) 这些条件,然后使 \(\sum c_i\) 最小。
初始设定 \(c_i=1\),因为必须是奇数,所以改变 \(c_i\) 只能 \(+2\)。因为要让最大值小于平均数,肯定是尽量平均的 \(+2\),如此循环直到 \(k\mid \sum c_i\)。
于是得到算法:令 \(p=1\),每次令 \(c_p+2\),然后 \(p\leftarrow p+1\)(\(p=n\) 则 \(p\leftarrow 1\)),直到 \(k\mid sum\),找到最优的 \(c\) 数组。判无解可以在这个过程中做:当 \(sum/k>500\) 则无解。
然后是怎么通过 \(c\) 还原操作:每次取 \(c\) 最大的 \(k\) 个位置,然后全部 \(-1\) 即可。
最后一个问题:为什么一个 \(c\) 数组在满足 \(2\not\mid c_i\)、\(k\mid \sum c_i\)、\(\max c_i\le \dfrac{sum}{k}\) 就能构造出合法序列?
按照 \(\max c_i\) 的大小归纳。
当 \(\max c_i=1\),显然。
当 \(\max c_i>1\),记 \(mx=\max c_i\),因为 \(mx\le sum/k\),所以 \(sum\ge k\cdot mx\ge 3k>2k\);同时 \(n=\sum \dfrac{c_i}{c_i}\ge \sum \dfrac{c_i}{mx}=\dfrac{sum}{mx}\ge k\)。所以一定可以进行两次操作都包含 \(mx\)。于是 \(mx\rightarrow mx-2\),由归纳假设知可行。
官方题解:我们只关心当前奇数次的杯子个数,建立 \(0\sim n\),第 \(i\) 个点表示当前有 \(i\) 个奇数,求 \(0\rightarrow n\) 的最短路即可。
另外 F 是个没有技术含量的缩点。
标签:CF1534,le,记录,max,sum,mid,dfrac,mx,模拟 From: https://www.cnblogs.com/FLY-lai/p/18400800