昨天刚好考完物理会考, 然后很嗨地回到家呆了一阵子 (但是晚上睡不着觉).
标程竟然因为 -m32 被卡成了 270 分, 这真正的是丹尼尔再世, 一个博学多识的评测机! 一个正直的评测机! (雾)
而且本来下午应该回学校领奖的, 然后被一波国际大神嘲讽一发. 但是仍然要在这里膜一发拿到奖的诸位大神, 尤其是 @zsyzzsoft 大神~
其实早上考的还是凑合的, 只是本来想要虐场的结果反被王子建/何中天暴虐~
早上的题目还是有一点思考深度的, 主要是有一堆结论要推, 下载链接:task.pdf
第一题我们会发现有这样一些规律, 我就简单把过程推一遍吧:
\[ans = k^2 \cdot \sum_{i=1}^{k}(S_i-S_{average})^2\]
\[= \sum_{i=1}^{k}(k \cdot S_i - \sum_{j=1}^{k}S_j)^2\]
\[= \sum_{i=1}^{k}(k^2 \cdot S_i^2 - 2k \cdot S_i \cdot \sum_{j=1}^{k}S_j + (\sum_{j=1}^{k}S_j)^2)\]
\[= k^2 \cdot \sum_{i=1}^{k}(S_i^2) - 2k \cdot \sum_{i=1}^{k}S_i \cdot \sum_{j=1}^{k}S_j + k \cdot (\sum_{j=1}^{k}S_j)^2\]
不妨设 \(\sum_{i=1}^{k}S_i = a, \sum_{i=1}^{k}(S_i^2) = b\), 则有:
\[ans = b \cdot k^2 - a^2 \cdot k\]
我们会很快发现这个问题就转化成为将环上的 \(n\) 个数分成 \(k\) 段, 使其长度的平方和 最小. 我写了一个 \(O(n^3)\) 的做法, 拿了 40 分.
后来说如果用斜率优化可以干掉一个 \(n\) 变成 \(O(n^2 \log n)\), 但是我当时觉得斜率优化根本推不出来所以就没管它.
第二题做法就是直接搜索, 如果上上 A* 剪枝就可以快速地拿到很多分. 不过听 @hshs595 说这道题数据可能有点问题, 第三个点几乎所有人都被卡掉了.
第三题也是一个结论题. 我们发现区间内最大极差一定是将整个区间选中, 然后最大值和 最小值的差就是区间最大极差. 最小极差一定是相邻两个数之间的差的最小值. 第一个性质显然, 不用证了. 对于第二个性质, 我们考虑一段区间, 其极差最小. 假想这个区间的长度大于 \(2\), 那么中间若存在一个更大的数, 那么该区间无意义. 如果中间还有一个可以使极差更小的数, 那么还不如切掉端点减小极差 (意会就可以了). 综上所述, 我们就把一个 任意子区间的问题转化成了一个区间问题.
这个可以用 Splay 树来搞, 因为涉及插点删点的操作. 这样可以拿到 80 分. 如果打开 -O2 优化, 那么 Splay 可以拿到 100 分 (虽然暴力也是 100 分 = =) .
差不多这一天就是这个样子. 结果我也打在这里, 但是不带名字 (是不是很良心).
| 选手编号 | spaceship | interstellar | atom | 总分 |
|---|---|---|---|---|
| std | AAAAAAAAAA |
AAAAAAAAAA |
AAAAAAAAAA |
300 |
| B12 | AAAAAAAAAA |
AAWAAATAAA |
AAAAAAAAAA |
280 |
| B08 | AAAAAAAAAA |
AATTTTTTTT |
AAAAAAAAAA |
220 |
| C04 | AAATTAAAAA |
AABWWWWWAA |
AAAAAAWWWB |
180 |
| C27 | ATAWWAAAAA |
WWWWWWWAWW |
AAAAAAAAAA |
180 |
| A23 | ATATTAAAAA |
WWWWAWWWWW |
AAAAAAAAAB |
170 |
| A18 | AAAAWAAATT |
WWWTWWWWWW |
AAAAATAAAA |
160 |
| B03 | AAATBAAWAW |
ATTTTTTTTT |
AAAAABAABB |
140 |
| A10 | AAABBAAAAA |
?????????? |
WWAAAAAAWW |
140 |
| B21 | AAAAAAAAAW |
AAWWWWWAWA |
WBTATTBBWB |
140 |
| B02 | AAATTAAAAA |
AAWAWWWAWW |
ATTTTTTTTT |
130 |
| A08 | AAAAWAAAAA |
WWWWWWBWWW |
WWAAAAWWWW |
130 |
| B16 | TTATTAAATT |
AWTTTWTTTT |
AAAAATAAAT |
130 |
| A02 | AAATTAAAAA |
AMMMMMAMMM |
AAWWWWWWWW |
120 |
| C19 | AAAWBAAATT |
WWWWWWWWWW |
AAAAAAWWWW |
120 |
| A04 | WAAWTAAAAA |
AATTTTTTTT |
WWAAATWWWT |
120 |
| A28 | AWAWWAWAWW |
AWWWWWWWWW |
AAAAAABBBB |
110 |
| B26 | AAAWWAWWWT |
AAWAAWTAAA |
WWWWWWWWWW |
110 |
| C32 | WTATBAAAAT |
AAWTTTTWTT |
WWAAAAWWWW |
110 |
| B01 | AWAWWAAAAW |
WBWWWWWWWW |
AAWWWWAAAT |
110 |
| C25 | TBABBAWTTT |
WWWWWWWWAW |
AAAAATAAAB |
110 |
| B17 | AAWBBAWTBB |
WWWWWWWWAW |
AAAAAABBWB |
100 |
| C15 | AAWAAWWWWW |
AWWAWWWWWW |
WWAAAAWWWW |
100 |
| C24 | AAWAAAAAAW |
WWWWWWWWWW |
AAWWTBWWBB |
100 |
| A22 | AAAWWAAAAA |
WWWABBAWWW |
WWBBBBBBBB |
100 |
| A01 | AAWABWAWWB |
AWWWWWWWWW |
AAWAAWBBWB |
90 |
| A17 | TAAWWAAATT |
AAWWTTWWTW |
AAWWWWBBBB |
90 |
| C29 | AWWWWAAAWW |
AWWWWWWWWW |
WWAAAABBBB |
90 |
| C01 | ATABBAAAAA |
WTWAWTWWWT |
WAWWWWBBWB |
90 |
| C09 | ATATTAAAAW |
TTWTTTWWWW |
AATTTTTTTB |
80 |
| B20 | ---------- |
AAAWWWBWWW |
AAAAABWWWB |
80 |
| B24 | WAWWWWWWWW |
AWWWWWWWWW |
AAAAAATTTT |
80 |
| A12 | AAAAAAWWAW |
WWWWWWWAWW |
WWWWTTWWWT |
80 |
| A25 | BBWBBAWAAT |
---------- |
AAAAABWWBB |
80 |
| B05 | ATATTAWAAW |
WWWWAWAWWW |
WWTTTTTTTT |
70 |
| B28 | TTWTTTTTTT |
AWWWAAAWAW |
AATTTTTTTT |
70 |
| B29 | ATAWWAATTT |
WWWAWWAWWT |
ATTTTTTTTT |
70 |
| A27 | WWWBBAWWWW |
WWWAWWWAWW |
WWAAAABBBB |
70 |
| A15 | WTATTWWWWW |
AWWWWAWWAW |
AATTTTTTTT |
60 |
| A11 | TTATTAAATT |
WWWWAWWWAW |
WWWWWWWWWW |
60 |
| C06 | ATATTTTTTT |
TTTTWWWWAW |
AAATTTTTTT |
60 |
| B40 | AAAWWAAATT |
?????????? |
WWTTTTBTBT |
60 |
| C16 | ATATTAWWWW |
WWWWWWWWWW |
AAATTTTTTT |
60 |
| A05 | ATABBAWWTT |
WWWWAWWAWW |
---------- |
50 |
| B32 | BAAWWAWWTT |
WWWWWAWWWA |
WBWWWWBBWB |
50 |
| B19 | ATATTAATTT |
AWWWWWWWWW |
WWBBBBBBBB |
50 |
| B04 | BBWWWWWWWW |
WWWWAWWWAW |
AATTTTTTTT |
40 |
| A26 | ATWTTAAWWT |
BBWWWWABBB |
?????????? |
40 |
| C30 | AAWWWWWWWW |
WWWWWWWAWW |
WTTTTTTTTT |
30 |
| A24 | ATWTTWWWWW |
AAWTTWTWWW |
WWBBBBBBBB |
30 |
| B09 | ATWTTWWWWW |
AATTTTBTTT |
?????????? |
30 |
| C12 | WWWBBWWWWT |
AATTTTTTTA |
WWWWWTWWWT |
30 |
| B27 | WWWWWWWWWW |
AWWWWWWWAW |
WWTTTTTTTT |
20 |
| B38 | WWWWBWWWWW |
WWWWWWAWWA |
WWTTTTTTTT |
20 |
| C17 | BBWWWWWWWT |
ATWWWWAWWW |
WWWWWWBBWB |
20 |
| C26 | TTATTWWWTT |
WAWWWWWWWW |
BBBBBBBBBB |
20 |
| B15 | ATWTTWWWWW |
WWWWWWTWWW |
ATTTTTTTTT |
20 |
| C11 | ATWTBWWWWW |
WWWWWWWWWA |
WWTTTTTTTT |
20 |
| C13 | WTWTTWWWWW |
---------- |
AABBBBBBBB |
20 |
| C14 | WBWBBWWWWW |
AWWAWWWWWW |
WWWWWWWBWB |
20 |
| B07 | AAWBBWWWWW |
?????????? |
WBBBBBBBBB |
20 |
| B41 | AAWWWWWWWW |
?????????? |
?????????? |
20 |
| C03 | ATATTWWTTT |
?????????? |
WTTTTTTTTT |
20 |
| C20 | WWWWWWWWWW |
AATTTTTTTT |
WWWWWTWWWB |
20 |
| C21 | AAWBTWWWWW |
WWWWWWWWWW |
?????????? |
20 |
| A19 | WTWWWAATBB |
WWWWWWWWWW |
BBBBBBBBBB |
20 |
| C22 | WWWWWWWTTT |
AATBBBBTBB |
WWWWWWTTTT |
20 |
| A20 | WWWWWWWWWW |
WWWWWWWWWW |
WAATTBTTBB |
20 |
| B11 | ?????????? |
AATBTTTTTT |
?????????? |
20 |
| A29 | BBTBBTTTTB |
WWWWWWWWWA |
WWWWWWWWWW |
10 |
| B06 | BWWBBWWWWT |
WWWWWWWAWW |
WWWWWWWWWW |
10 |
| C18 | WTATTWWWWW |
TTTTTTTTTT |
WBWWWWBBWB |
10 |
| A09 | ABWWWWWWWW |
?????????? |
BBBBBBBBBB |
10 |
| C10 | WWWWWWWWWW |
WWWWWWBWWA |
WWTTTTTTTT |
10 |
| C05 | WAWWWWWWWW |
?????????? |
?????????? |
10 |
| A06 | ?????????? |
---------- |
---------- |
0 |
| A14 | TTWTBWWWWW |
WWWWWWWWWW |
WWTTTBTBBB |
0 |
| A30 | ?????????? |
?????????? |
---------- |
0 |
| B10 | ********** |
---------- |
---------- |
0 |
| B23 | WWWTBWWWWW |
********** |
?????????? |
0 |
| B33 | WWWTTWWWWW |
---------- |
WWTTTTBBBB |
0 |
| B34 | TTWTTWWWTT |
WWWWWWWWWW |
---------- |
0 |
| B36 | ?????????? |
?????????? |
?????????? |
0 |
| B39 | ?????????? |
?????????? |
?????????? |
0 |
| C08 | WTWTTWTTTT |
BBMMMMMMMM |
?????????? |
0 |
| C28 | BBBBBTBBBB |
WWWWWWWWWW |
WWTBBBBBBB |
0 |
| C34 | BBBBBBBBBB |
TTMTTTBTTT |
WWTTTTBBTT |
0 |
| C35 | ********** |
?????????? |
BBTTTTTTTB |
0 |
其中 @hshs595 和 @moorhsum 两位大神均拿了 180 分, 而 @Miloris 大神拿了 170 分, 同时 @hld67890 拿了 140 分. 我这种弱菜只能排在他们后面跟着 130 分了~
另外还有这次的官方成绩单, 下载在这里:在 2017-1-19 的竞赛.xlsx
附上整个考试后传到局域网 FTP 的文件夹:test0119.tar.xz
似乎实力被巨神续上了好开心~