7
有惊无险。一等应该有了。
那既然有了就重写一遍复赛吧。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
初赛
DAY -1
对。
DAY 0
不对。
DAY 1
对。
感觉还行,由于休息够了感觉比既报 J 又报 S 的更有优势。
好了看题。
我去什么 KMP?什么线段树?什么 Trie?吓哭了。
然后是一道 DAG 拓扑排序的题,我觉得答案可能有很多,但选项的答案特别小,而且前面几题都选的 D,这题为了保险就选了 B 了。
然后单选题印象最深的就是两个“编程”题。
第一个是 01 背包。
不难发现当物品的重量越大,价值也越大。
我们还注意到全选不行,但是可以放弃一个选。放弃一个中,放弃第二个是最优的。那有没有其他情况呢?可以发现最小两个的价值加起来已经超过第二个了,所以不存在其他情况。
第二个是那个任务的。
第一眼看到感觉像可反悔贪心,然后正常按右端点排序,结果发现可以无惩罚解决,然后就结束了。
后面发现可反悔贪心做法假了。
然后是组合题。
第一题是一个简单全排列问题,当时时间还有一个半小时,我干脆直接把所有全排列都打了一遍。
第二题有点难绷。不过这是 CSP 第一次出交互题,还是挺震惊的。
题目意思就是给你两个相同的蛋,猛锤超过 kkk 次就会爆炸,求这个 kkk。
solve1 很简单,就是暴力试。
我没看 solve2,先猜一下,应该是分块,尝试 O(n)O(\sqrt n)O(n ) 次。结果果然如此,但是为什么他的分块这么奇怪,以递减数列来分呢?不管了,肯定有他的道理。
正常写写到最后一题时才发现原来他这么做是为了平衡次数,减小常数。比如说第一块最坏需要查询 1+131+131+13 次,第二块最坏要查询 2+122+122+12 次,以此类推。
第三题看着很唬人,其实也就是个折半搜索。
注意值域是 [1,m][1,m][1,m] 就行。
然后完善程序第一题是一道免费边的题,一眼分层图最短路,秒切。
第二题是个小交互,仔细读十几分钟题后就发现是枚举所有可能组合就行了,可以证明每种情况都有它对应的组合。
最小测试轮数我不会证,但题目也没要证。
最后注意的一点是,CCF 还是这么喜欢阴人,它的每一种情况是前 111 后 000 的,所以枚举全排列需要选上一个排列(prev_permutation)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 1.5
去 ACGO 测了一下:我去??????93???????
错了几个很糖的错误,比如那个 DAG 答案就是以上都不对,猜蛋那题 check2 次数可能比 check1 多。可以看出我不会造 hack 数据
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY +∞+\INFTY+∞
还真是 939393。群友现在还不知道他们被拉爆了。(我向他们报的是 737373)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
复赛
DAY 0
做了一下超速检测,2h2h2h 才做完第一部分。我该在哪里停留?我问我自己。
DAY 1
不想那么多了,相信自己。
666 监考老师把 J 组解压密码当 S 组放上去了,硬控我 1min。
666 放上去的解压密码漏了个 4,硬控我 2min。
先开 T1。
什么鬼。不超过 n2\frac{n}{2}2n ?那就枚举最大的咯?
不管了,先拿暴力分再说。
令 dp[i][j][k]dp[i][j][k]dp[i][j][k] 分别为拿 iii 个 111,拿 jjj 个 222,拿 kkk 个 333 的结果。
好的,303030 以内的数据都过了。
现在开始想正解。
首先蒙个结论:最多的一定拿 n2\frac{n}{2}2n 。然后枚举最大的贪心就行。
结果发现样例没过,结论假了。
现在还剩 3h3h3h,没办法了,先开 T2。
第一眼,肯定是 MST。
诶 kkk 这么小?估一下时间复杂度吧。有分 k=5,k=10k=5,k=10k=5,k=10 的数据,nnn 还只有 10410^4104,那时间复杂度不出意外就是 O(nk2k)O(nk2^k)O(nk2k) 了。
注意到原来的有很多浪费,我们真正需要的只有 n−1n-1n−1 条边,就是原来的最小生成树。
然后枚举 kkk 二进制位,看看选哪些是最优的。此时我们只需要 nnn 个点和这几个点连通就行了。排序后 MST 即可。
时间复杂度 O(nk2klog(nk))O(nk2^k\log (nk))O(nk2klog(nk)),瓶颈在于排序。
然后看 T3。
我去 T3 怎么是字符串啊。有点难度,先打暴力。
好了暴力打好了,样例过。
先写一个哈希板子再说。
不对正解好像是 Trie 之类的。(UPD:瞎蒙蒙对的,难绷)
那算了,还是看看 T1 吧。
又想了 20min 还是没想出来,那就拼测试点吧。
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我为什么场切 000 题,这下得被群友打爆了 555555555555555555。
拼好了,O(n3)O(n^3)O(n3) 的可以拿前 111111 个点,错误的结论可以拿性质 A,B,随机数据也可以顺便过了。预估 80pts80pts80pts。
T3 后面还是想了想,弄了个 O(q∑Si)O(q\sum S_i)O(q∑Si ) 的暴力和性质 B。
我的想法是求出两个字符串的“核心”(即除了那一块其它都是相同的),然后求出“核心”的哈希值,暴力匹配即可。
相信 CCF 数据水,一定能过的。
加了个特判,说不定能过性质 B 呢。
最后 5min,没时间做 T4 了。检查了一下。
赛时预估 80+80+50+0=210pts80+80+50+0=210pts80+80+50+0=210pts。
code:
DAY 1.5
坐车回家时发现我的特判假了,210→190210\rarr 190210→190。
DAY 1.7
不是他们怎么都在讨论 ∣t1∣≠∣t2∣|t_1|\not= |t_2|∣t1 ∣=∣t2 ∣ 啊。
卧槽。出题人你吗。
190→160190\rarr 160190→160。
DAY 2
跟群友讨论分数。
他们都是 100,120100,120100,120 之类的,看来我还是挺强的。
写题解。诶我这 T1 暴力时间复杂度多少来着。我去是 O(n4)O(n^4)O(n4)。我*********
160→135160\rarr 135160→135。
T2 要是再寄我 OI 生涯真的得宣告结束了。
我该在哪里停留?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 3
郁闷地尝试口胡 T3。SA 做法假了。
DAY 4
在学校想出了一个 Trie 套 Trie O(LL)O(L\sqrt L)O(LL ),回家路上优化成了小常数 O(Llog2L)O(L\log^2 L)O(Llog2L)。
DAY 5
郁闷地补 T3。
DAY 6
出成绩了。
T1:期望 (55+eps)pts(55+eps)pts(55+eps)pts,实际 55pts55pts55pts。
T2:期望 (80−80eps+eps′)pts(80-80eps+eps')pts(80−80eps+eps′)pts,实际 80pts80pts80pts。
哎,还好。二等保住了,但一等也不可能了。
T3:期望 0pts0pts0pts,实际 30pts30pts30pts?!
我去!
出题人妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈。
看了看洛谷,发现出题人根本没有设置 ∣t1∣≠∣t2∣|t_1|\not=|t_2|∣t1 ∣=∣t2 ∣ 的点,感谢大哥不杀之恩。
最终分数:165pts165pts165pts。
那 1= 有希望了。
DAY +∞+\INFTY+∞
听说分数线是 152152152,6\sqrt66 线是 133133133。一等有了,就是不知道进不进 NOIP。
这场比赛我的问题还是挺多的。
首先是 T1,我不但没有想出简单的贪心正解,而且还估算错了时间复杂度,导致挂了 25pts25pts25pts。
然后是 T2,明明预先排序就可以做到 O(mlogm+knlogkn+2kknα(n))O(m\log m+kn\log kn+2^kkn\alpha(n))O(mlogm+knlogkn+2kknα(n)) 就可以 100pts100pts100pts 的,但是后面还是没想出来。
接着是 T3,没有仔细读题,样例 2 这么明显的反例都没看到,虽然最后还是得了分但还是得反思一下;我在选模数时选了一个巨大的模数 350234023535023402353502340235,这个是会爆 long long 的;我没有思考就开始胡乱拼点,导致特殊性质没拿到,原先的 50pts50pts50pts 还挂成了 30pts30pts30pts。
T4 20pts20pts20pts 特别好拿,但是我没看题,痛失 20pts20pts20pts。
这些错误希望 NOIP 和明年的 CSP 等都不会再犯。
不管怎么说,已经结束了,安心准备下一场考试吧。
有帮助,赞一个