Educational Codeforces Round 189
| 编号 | CF2225 |
|---|---|
| 难度 | Div.2 |
| 赛后订题 | A,B,C,D,E,F |
Solution
A
设 \(k = \frac{y}{{x}}\)，那么只要 \(k > 2\) 即可，因为 \(z = (k-1)x\) 是一个合法的解。
B
手玩发现如果非法的话分段，比如 aa 和 bb 的中间都分一下段。
最后会发现只要段数不超过 \(3\) 都是可以的，否则都不行。
简单说两句吧，大于 \(3\) 是显然的，因为只能操作一段。
- 段数为 \(1\) 时，随便找一个点反转一下，第二步不做。
- 段数为 \(2\) 时，随便找一个段反转一下，两种情况：
- 要么直接合法了，不做第二步。
- 要么不合法（首尾相同），第二步做一下即可。
- 段数为 \(3\) 时对中间段反转，然后讨论同 \(2\) 段。
C
直接 dp 即可，因为要么竖着放要么两个并排放。
D
简单手玩一下发现异或和为 \(0\) 的最小子段长度为 \(4\)，并且所有连续的都可以由这些拼接而成。
我们发现这样的段可以分为两类，且这两类互不干扰：
- 第一类（奇段）：\([0,3],[4,7],[8,11],\dots \to [4k,4k+3]\)。
- 第二类（偶段）：\([2,5],[6,9],[10,13],\dots \to [4k+2,4k+5]\)。
其中 \(k \ge 0\)。
因此我们计算出 \(x\) 左右分别有多少奇/偶段开头/结尾，然后乘法原理即可。
个数的计算直接解不等式，把 \(k\) 的取值范围解出来就好。
最终的答案为：
E
有点看不懂题解。先放着吧。
神仙题。首先来看这种构造方法，被称为 六边形堆积。
可以看作是在边长为 \(2r\) 的等边三角形的三个顶点上作为圆心，放置三个半径为 \(r\) 的圆。
最后整个矩形被若干等边三角形覆盖。所以我们分析覆盖率只需要对一个等边三角形去做就行，很好算 \(\frac{\pi}{2\sqrt 3} = 0.90\)，非常好！
找到覆盖方法后，我们考虑到这些点都是在一个矩形内均匀选择的，因此问题在于怎样放能够放的比较满。
注意到确定了一个圆的位置，剩下的就都确定了。
因此我们考虑随便确定一个圆的位置，记为原点。然后从这里出发去做。
做法和官方题解是一样的，设原点 \((x_0,y_0)\)，那么显然有：
注意这里 \(\sqrt3r\) 向上取整的原因是避免重叠。
然后为了可以算出来 \(row,col\)，但是可能不太准，所以给个正负一的偏差，也就是 \(col+1,col-1,row+1,row-1\) 这些都算一遍。
然后我们可以判定得到的这个圆能否覆盖住当前枚举的这个点，可以的话加入个 set 里，然后 break 掉即可，因为一个点一个圆就够了，多了不优。
最后判定覆盖点的总数是否达标即可。
啊其实是有个小问题的，洛谷讨论帖：https://www.luogu.com.cn/discuss/1284915。
我使用的是 官方题解 的做法，就是随机选网格原点的这种。
因为网格 \(w = 2r, h= \sqrt 3 r\)，所以说网格原点的随机选取看成网格平移的话，那么这个平移的范围本质上应该是不超过 \(2r\) 的。
所以我把随机选取网格原点的这两行代码，从 \([0,100000)\) 中均匀随机改为了从 \([0,2r)\) 中均匀随机。
提交发现可以 AC，正确性应该是没有问题的。
但是这样的话时间会比从 \([0,100000)\) 中均匀随机快很多，各测试了三次，结果如下。
随机区间 第一次测试时间 第二次测试时间 第三次测试时间 \([0,100000)\) 921ms 843ms 1390ms \([0,2r)\) 62ms 78ms 78ms 感觉差异还是挺显著的。不过这两种随机方式应该本质相同吧？为什么会有这么大的时间差异呢？求指教！
F
好久没写哈希，莫名奇妙错得调了很长时间。
注意到两个事情这题就很好做了。首先是，划分段数为 \(k\) 一定不劣。
证明方法是可以每次把字典序不是最大的段和其他的段合并，而且下界是 \(k\)。
其次是题目让求第 \(k\) 段字典序最大是啥，而段与段之间的排序方法是按字典序升序。
所以对于任意一种划分方法，字典序最大的段就是第 \(k\) 段，如果一段排序后不是第 \(k\) 段，那么它就一定不是最大的字典序，不会对答案产生影响。
因此，我们考虑枚举答案。先枚举起点 \(i\)，考虑找到终点 \(x\)。
这里需要满足：
- 对于 \([1,i-1]\)，除非 \(i = 1\)，都被分成了至少 \(1\) 段。即 \(i > l\)。
- 对于 \([x+1,n]\)，除非 \(x = n\)，同上。
- 总段数为 \(k\) 段。
由于前面的 \([1,i-1]\) 的区间是固定的，我们自然希望让这个区间划分的段数尽可能的多，这样后面分的段数就少，答案的长度更大不劣。
由此 \([1,i-1]\) 区间的段数为 \(\lfloor \frac{i-1}{l}\rfloor\)。那么在 \([x+1,n]\) 区间就需要有 \(k-\lfloor \frac{i-1}{l}\rfloor-1\) 段。贪心地，让这些段的长度都尽可能的小，即为 \(l\)。
所以 \(x = n-\max(0,k-\lfloor \frac{i-1}{l}\rfloor - 1) \times l\)。
注意盘掉一些不合法的东西，比如 \([i,x]\) 的长度不足 \(l\)，\(x < i\)（其实本质和前者相同）等。
摘出来了 \(O(n)\) 个可能成为答案的子串后，只需要找到字典序最大的就可以了！
直接二分+哈希，具体来说先二分两个字符串相同的前缀，然后比较后一位大小即可。
擂台法只需要比较 \(O(n)\) 次即可找到最大值，时间复杂度 \(O(n \log n)\)。