学长出的模拟赛,风格挺好。
赛时
8:00 T1 会了一个 \(O(n^2\log n)\) 的做法,先写一下,看看能不能过样例。
8:20 过了小样例,大样例跑得慢但是是对的。
8:40 发现一个好的做法,可以枚举 \(c_i\) 最小的那一天选了哪个,再枚举 \(k\) 天,这样纯枚举复杂度是 \(O(k)\) 的。但是有些细节不太好处理。
现在转化成了一个经典问题,很多次遇到了,但我还是不会。
欸,好像会了。时间复杂度 \(O(k\log n)\)。贪心不好写,枚举解决!
9:05 ok,大样例全过了。最慢的点 \(0.4\) s。
T2 怎么还有 SPJ,这么神秘。下发了 checker 但是不知道怎么用。
9:35 T3 会了 \(O(m^n)\) 的爆搜,有了 \(15\) pts。
完了,不会 \(2^n\) 做法。
T4 一次旅行不可能经过很多的点,这样很浪费。也不可能经过一个点,
T4 直接模拟旅行不太可做,可以将题意转化为分成若干个连通块,而这是树,转化为哪些条边需要断掉。这样可以 \(2^{n-1}\) 枚举,计算每个连通块的贡献。
也许可以树形 DP,设 \(dp_i\) 为断掉与父亲的边时 \(i\) 子树内的答案,但是我不会转移,唐完了。
10:25 T4 的 \(10\) pts 写完了。
一次旅行经过的点数不可能大于 \(3\),也就是每个连通块的大小小于等于 \(3\),也不可能是 \(1\)。
欸,结论假了,寄。
\(10\ 1\ 1\ 1\ 11\) 这样,\(5\) 个数全选上是最优的。
10:55 把链 \(O(n^2)\) 的性质写了。
11:30 T2 通过找大样例规律拿了输出方案数的 \(20\) pts。
又写了 \(n=1\) 的分。
想冲一下 \(n,m\le 4\),打算手玩。
玩得我头晕了,还有两种情况没写,不写了。
寄。
估分:\(100+28+15+20=163\)。
得分:\(100+28+15+20=183\),rank 2。
赛后
T1 怎么除了我 A 掉的做法都是一样的啊,我就这么独特(。
T2 可以手玩一下发现一下消除 \(3\) 行或 \(3\) 列,感觉如果不考虑证明该做法最优还是简单的,但是细节肯定不少。
T3 容斥 + DP,赛时没写出 \(O(n^4)\) 的做法,亏大了。
T4 树形 DP,朴素 \(O(n^3)\)。然后 \(O(n\log n\log V)\) 的做法是一个 dsu on tree 加权值线段树,挺对的。
\(O(n\log V)\) 的做法是线段树合并优化 DP,很可订正。
感觉把状态列出来,再加上朴素转移,很困难。之后还是比较简单的。
总结
要多玩样例,找找规律,发掘性质,多拿性质分,从性质中推出正解。
对于数学还是要加强。
标签:10,12,20,log,DP,枚举,NOIP2024,做法,模拟 From: https://www.cnblogs.com/zhujiangyuan/p/-/NOIP2024_12