模拟赛总结

校内模拟赛 · 合集

WARNING 糖分超标。

NOIP 模拟赛 #1

题目链接（内） 题目链接（外）

老师：有亿点难度。

赛时

先看了看 T1，发现很熟悉。但是不会 DP。

先把树建出来，然后对着小样例推了推式子，都能对，然后跑了一下大样例，没一个式子能过大样例。

能写个暴力，但是只有十分不想写，先扔着，溜了。

然后看 T2，会写 \(O(nm)\) 的做法，一看咋还是只有十分，先走了。

然后看 T3，发现所有相同的性质好像能写，写了个式子溜了，但是 WA。

然后看 T4，还是只会暴力，写了，然后回去看 T1。然而边界没写好 TLE。

回去写了 T1 的暴力，然后开始再推式子。

考虑了二分 + Check，但是不会 Check；又考虑对于每个叶子节点计算以它为最终答案的取值约束范围，但是不会 QWQ。

然后考虑每个 max、min 至少包含 ? 的情况，是 \(n\) 减去从根节点往下和根节点相同的函数个数，猜猜性质然后和暴力拍拍就对了。

然后去放放风卫生间，想到 T2 树的性质，可以在树上跑个 DFS 然后 if (siz[y] >= w[x]) fa[y] = x; 跑一下并查集，看看每个点是否 Get(i) == 1，码了一下过了大样例。（还挺贴心有部分分的样例）

然后考虑图是链的性质，考虑也用并查集，维护向左向右的范围，但是会被卡，不太好优化。

发现 T4 一个假了的性质，给了一下优化。没啥用，该 T 还是 T，但是 OI 赛制不知道，至少拿有暴力分不太慌了。

然后罚坐几分钟就结束了。

估分：\(23+20+5+10=58\)；实际：\(23+20+0+0=43\)。

赛后

1
2
3
sto Hthntd orz
sto Sorato orz
sto PineappleSummer orz

听说 T2 是 Kruskal 重构树，一看还真是。

发现机房大佬 @Hthntd 过了 T3 的 60 分，突然发现赛时没咋看 T3，一看发现“最多 \(15\) 个组”，这真就裸的装压啊，至少能写个 \(O(2^kkn)\) 的部分分啊……

发现 T4 性质假了，赛时应该暴力跑跑打出来看的，不能瞎猜啊……

暴力挂了、暴力分没打满、正解没看出来，菜就多练。

都是 luogu 原题，盲猜：蓝 + 紫 + 蓝 + 蓝；但是 紫（P8997） + 紫（P8393） + 蓝（P8394） + 紫（P8996）。

NOIP 不能考这么难吧……

讲评后

T1 的思路大体是对的，式子差一点，推的不是太准确。听完感觉式子比较好推，但是赛时没推出来。

T2 重构树也比较简单，讲了之后发现很对，但是赛时不太好看出来。

T3 的正解就是状压 + 二分优化，也感觉比较显然。

T4 是个大数据结构，好像是权值线段树，确实比较难。

总结

  • 注意时间分配，不要一直卡 T1，有可能其他题的部分分其实比较简单，但是不敢写。

  • 注意数据范围中特殊的地方，特别是 \(k\le15\) 这种明显提示做法的。

  • OI 赛制，注意验证结论的正确性。不行打个表，反正有现成代码。

  • 赛后感觉比较简单的，赛时没有想出来，还是要深度思考。

NOIP 模拟赛 #2

题目链接（内） 题目链接（外）

老师：比昨天简单。

赛时

先看了看 T1，发现这场部分分比较大，先写了 30 的模拟分，然后溜了。

看见 T2，写了 40 分的特殊性质，感觉很水。突然发现题面直接给有第一问的解法，按照模拟直接可以过？然后浅推一下性质，发现了第二问的解法，两问手动拍一下过了。

然后 T3，感觉不会，就是让我写 \(n\le10\) 的暴力都难，突然有了个 DSU + BIT 的想法，开始码，快写完感觉假了，造了个反例，直接 GG。

开 T4，不会一点，写个暴力枚举，回去看 T1。

打个表发现，\(\bmod 8=0\) 的数都很大，本身大的也大，就把这两种的最大的 \(2k\) 个塞进去，过了大样例。

然后看了一眼 T2，开了个 long long。

然后考虑 T3，写了个没有 ? 的性质，然后开始写 \(O(n^3)\) 的写法，写了半天到最后十几分钟，终于过了所有样例，然后随随便便手造俩 PRP 和 ?R?，全给 hack 掉了，时间全浪费了，哭哭。

赛后

1
2
sto Sorato orz
sto whrwlx orz

刚结束突然会了 T1 \(k\le10^5\) 的做法，但是赛时只有十分。咋回事呢？一看代码：

1
2
3
4
5
void Main() {
  l = read(), r = read(), k = read(), c = read();
  // if (r - l + 1 <= 100010) return SubtaskI::Main();
  if (k <= 100010) return SubtaskII::Main();
}

服了把第一档注释掉了，直接挂了 20 分。

然后 T3 的瞎搞多混过了一个点，得了 50。

看见 @Sorato、@Hthntd 一众大佬过了 T4 的 50 分，发现是个显然的 \(O(n^3)\) DP，但是当时就光想着 DFS 了。

该拿的分要么没写要么挂掉。

还是两套的 A1，A2，B1，B2 qwq。

讲评后

T1 是一个比较麻烦的二分答案，但是很好理解，细节比较多，应该赛时磕磕能写。

T2 是模拟 + 找规律，算是复习了手写有理数。

T3、T4 是 DP，还要推推式子，同时正解都很简洁，思考不能太复杂。

总结

  • 考试是没保存代码，都是在上一个版本直接改的，导致 T3 的版本问题很大，实现耽误了很长时间。

  • 赛时适当磕一磕题目，但是不要走偏。

  • OI 赛制，注意提交代码中的 // 的 #ifdef 该有的不该有的都检查一遍。还要 freopen() 文件名。

NOIP 模拟赛 #3

题目链接（内） 题目链接（外）

分，就是用来挂的。

赛时

T1

第一眼按照字典序排序然后顺序输出，码了一下过了样例，也测了大样例。

但是发现了 ab abaa 一组反例，于是改成了两个数字循环比较，但是好像不是严格弱序，连续 std::sort() 之后结果不一样。

然后发现 \(|s| \le 10\)，感觉可以循环为长度为 \(\operatorname{lcm}_{i=1}^{10}60\) 之后按这个排序。

码了一半然后发现，可以直接按照两个字符串相加的字典序排序 

1
sort(s + 1, s + 1 + n, [](string x, string y) { return x + y < y + x; });

T2

发现操作次数小于 \(50\) 很有用、只需要对一个串操作两个性质。

于是设 \(f(i, del, ins)\) 表示匹配的 \(A\) 第 \(i\) 位，\(B\) 删除 \(del\) 个，插入 \(ins\) 个的最小代价，转移：

\[ \begin{aligned} f(i+1, del,ins)&\stackrel{\text{min}}{\longleftarrow}f(i, del,ins)+[a_{i+1}\neq b_{i+del-ins+1}]\\ f(i+1,del+1,ins)&\stackrel{\text{min}}{\longleftarrow}f(i,del,ins)+1\\ f(i+1,del,ins+1)&\stackrel{\text{min}}{\longleftarrow}f(i,del,ins)+1 \end{aligned} \]

感觉有点 TLE，但是后两维相加不超过 \(50\)，所以时间能过。

其实这里第一维可以滚动，但是不想优化了。

T3

一眼结论题，先写了个 DFS，打了个 \(8\times8\) 的表去找规律。

发现找不到，于是跑着 DFS 打 \(10\times10\)。

然后去写 T4 了，之后回来发现 \(m=10, n=10\) 要打到天荒地老，遂放弃。

发现可以状压，时间复杂度 \(O(n^2\sum_{i=1}^m{n\choose i})\)。

然后去找 \(n=m\) 的规律，但是没时间了，开摆。

T4

好奇怪。

先手玩一下 \(n=2\)，发现了一些东西。

然后就写，过了样例。

为了骗分，写了每次让前两个组合，但是没过大样例，反正骗分，就交了。

赛后

期望得分：\(100+100+30+12=232\)；

实际得分：\(100+0+30+4=134\)

T2 爆零了，发现是 \(\color{red}\text{Runtime Error}\)，开始怀疑越界，突然想起数组开过大 OJ 会报 RE，一算空间发现需要 \(2\text{ GiB}\)，但是限制 \(512\text{ MiB}\)，寄， \(100 \text{ pts}\to0\text{ pts}\)。然后加了个滚动数组，于是 \(\color{lightgreen}\text{100 Accepted}\)，难受。

T4 也挂了，只过了样例。

讲评后

T1 好高深，还要涉及 Order Theory，但是结论可以直接猜。

T2 就是 DP，比较简单，但是太坑。

T3 是 破环成链方法在组合计数中的简单应用，很好理解但是赛时没想到。

T4 是 [ROI 2018] Addition without carry，神奇死难 \(\color{black}\text{NOI/NOI+/CTSC}\)，我觉得还是去看咋拿 \(12\text{ pts}\) 就好了。

总结

  • 注意空间，能滚动的滚动，能压的就压，因为只要 MLE 就没分了。实在不行开 std::vector<>，至少还能拿点分。

NOIP 模拟赛 #4

题目链接（内） 题目链接（外）

又挂分了。

赛时

T1

想了一会，发现每次询问独立这个性质很好，所以就把每一次修改后 \(id\) 的答案映射到原来的操作的结果上。

但是细节比较多，写了一个小时写出来了。

T2

发现如果把蛇形数组展开就是一个裸的线段树上二分。

但是不太会展开。

突然发现可以先算圈数，在根据每一圈内部圈数的计算，时间复杂度 \(O(1)\)。

T3

感觉和之前 ABC 的 Odd Similar 比较像，但是不太会。

写了个暴力扔上去了。

T4

题目说 \(S_1 < S_2\)，但是没说到底咋比较，所以就不写了（）

赛后

期望得分：\(100+100+10+0=210\)；

实际得分：\(100+25+12+5=142\)。

T2 又炸了，发现只过了 \(Q\) 小的点，发现是动态开点线段树数组开的时候写了 used[N] 了，

讲评后

T1 确实是这样，挺好。

T2 太可恶了，明明这么简单的题但是没有过。

T3 是一个最短路，挺好想的但是赛时不会。

T4 人类智慧，AT 上最短解很好理解。但是可能常数有点大。

总结

  • 数组一定要开够，不要开太大，但是也不要越界。

  • T3 那种多源的问题可以考虑能不能转化成相反问题然后转化成单源。

NOIP 模拟赛 #5

题目链接（内） 题目链接（外）

%% Larunatrecy。

赛时

T1

发现了一些没有的性质，想了好长时间还是不会。

扔了个暴力走了。

T2

发现是个很板子的 Kruskal 重构树，码了一下过了一堆样例。

但是有一个样例错了就很搞人心态。

T3

看范围猜分块，但是按照操作分块和按照度数分治多不太会。

还是暴力，嘿嘿。

T4

题看懂了，但是没有暴力搜索分？

扔了个随机数，也快结束了。

赛后

期望得分：\(20+100+20+0=140\)；

实际得分：\(20+90+20+0=130\)

连着不知道多少次 T2 炸了，发现是最后输出答案 ans + H - w[cnt] 之后没取模。啊啊啊啊啊！

然后发现作为多测的 T1 在不能暴力的点里边竟然有 \(10 \text{ pts}\) 全是无解？？？没拿啊啊啊！

讲评后

T1 是一个大胆贪心，但是赛时不会，感觉还是很好理解。

T2 很简单，但是写的有一点点复杂。

T3 是把图转化成序列，在序列上分块，细节好多 QWQ。

T4 是一个神奇区间 DP，好像是 \(*3500\)，不会啊啊啊。

总结

  • 取模封个 Mint 还是保险一点。

  • 难题的简单范围可能还要思考，不能只写纯暴力啊！

NOIP 模拟赛 #6

题目链接（内） 题目链接（外） 成绩表

Laru 老师出的题，至少比 DMY 简单 : )

赛时

T1

第一眼贪心，每次选最小的 \(\times2\)，为了不受 \(\bmod 2\) 的影响取对数。

突然听见别人说 \(m\le10^9\)，不会了。

想到之前有场 CF 有个类似的题，方法是二分最大值然后批量修改，再暴力计算剩下的。

但是可能是因为要二分实数的问题，细节有点爆炸。

发现 \(\times2\) 的话，有个如果最小值 \(\times2\) 之后大于最大值，那么一定能过。

分析复杂度 \(O(n\log n)\)，遂过，此时 \(\text{1 h}\)。

T2

先写暴力：将链上非 LCA 的点连到其父亲上，然后缩点跑 DP。

DP 式推了一小会，发现是 \(f_x=\prod\limits_{y\in\text{son}[x]}(f_y+1)\)。

突然发现这个 LCA 的操作可以树上差分搞，分析时间复杂度 \(O(m\log n)\)，写个树剖 LCA 卡卡常能过。

——但是树剖写不过，遂写倍增，但是有个 x = anc[x][t], y = anc[x][t]; 的智障错误卡了半小时，还好看出来了，遂过，此时 \(\text{2.5 h}\)。

等等，你不是说倍增常数大要写树剖的吗？

T3

死人大模拟。

赛时把 TC 6 和 TC 7 的输出往 CPH 里输的时候输反了，导致对着无解的找了至少 \(\text{10 min}\)。（雾）

于是写了 \(\text{40 min}\)，调了 \(\text{40 min}\)，但是还是 \(\texttt{TC #7}\color{red}\texttt{Failed}\)，没时间了，还是交吧。

T4

没时间啦~，随机输出个数看看 rp。

赛后

听说 T2 卡 \(\log\)，这不寄掉。

赛时期望：\(100+100+rp_1 + rp_2 = 200+rp_1+rp_2\)。

赛后期望：\(100+70+rp_1 + rp_2 = 170+rp_1+rp_2\)。

实际得分：\(100+65+20+0 = 185，\text{rk 3}\)。

T2 有个让两个儿子同时异或一个随机数的做法，这样在 LCA 处直接自己消了，太强了！

等等，T2 为什么还有 \(\color{violet}\text{RE}\) ？\(n\le2\times10^6\) ？我开的 const int N = 1E6 + 100; 逆天。

讲评后

T1 无话可说。

T2 以为正解是四毛子或者是欧拉序之类的，但是竟然可以在每次询问的 \(s,t\) 之间直接连边 Tarjan 跑边双缩点！Laru 老师太强了！%%%

T3 无话可说，想起了 CPS-2023 C. struct，咋都镇死人。

T4 感觉暴力 DP 和性质 DP 很可做，但是赛时光顾着写 T3 了，哭哭~

总结

  • 数组大小一生之敌，但是还是不要乱用 vector<> 罢……
  • 注意答题策略，比如这次的 T4 显然比 T3 好拿分。至少 T3 这种的能骗分。
  • @Hthntd 大佬 T1 \(\bmod 998,244,353\) 了，还是机房第一，太强了！

NOIP 模拟赛 #7

题目链接（内） 题目链接（外）

IOI 赛制

Laru 老师的题，不比 DMY 简单 :（

赛时

IOI 赛制，题目难度与顺序无关。

于是先看了三个题。

先看 A 感觉不太会；再看 B 发现可以骗分，正写着 cout << -1 听见说没有 -1 的点，于是开始写暴力，于是 \(52\text{ pts}\)；然后去看了 C，感觉是长剖。

于是赛时先写了 C 的长剖，发现不会遂写暴力，再写了 A 的暴力，然后又去磕 C 了。

A

沙普兰德想要给他的领导送礼

第一眼以为是先对所有 \(A\) 取 \(\min\)，然后按 \(C\) 排序，找 \(i\) 前后可以到达的区间内的最小 \(B_j\)，用 \(B_i+B_j\) 更新，结果一看样例假了，发现题意看假了，要把所有的送掉。

然后先写了个 \(C=1\) 的性质，发现有一个连边长度不超过三的性质，于是 \(O(qn)\) 可以写。然后考虑 DDP 优化，但是对 \(L\) 的约束不太会搞。

B

赵空玲要搬新家了，他要给客厅铺上地毯。

先写了一个暴力枚举 \(n\)，混了 \(\text{52 pts}\)。虽然没咋卡但是好像是暴力最高分。

然后考虑枚举 \(k \text{ st. } \dfrac{n(n + 1)(2n + 1)}{6} = km\)，然后二分找有没有 \(n\in N\) 的解，发现跑的极慢，不如暴力。

然后发现可能是个 exgcd 之类的，不会数学。

C

长链剖分，但是写挂了，于是开始对怕，拍了半个多小时，\(\color{red}\texttt{Failed}\) 一次改一次，最后 TC 1~20 都是 \(\color{lightgreen}\texttt{Passed}\)，但是还是过不去啊啊啊。

赛后 & 讲评

A 果然是 DDP，因为 \(L\) 可以离线修改所有可以做。

B 是数学，不会 NT 啊啊……

C 的长剖思路差不多，还是吗，没调出来啊。

总结

  • 离线思想不要只局限于那些板子，即使离线了也不会 DDP。
  • 长剖优化 DP 多练练。

NOIP 模拟赛 #8

题目链接（内） 题目链接（外）

Laru 老师太强了！

赛时

A

先想到暴力是枚举每个点，然后枚举长宽，检测矩形内点的个数，是 \(O(N^3C)\) 的。

大胆猜测，只有每个颜色所被覆盖的最小矩形的端点是有用的，可以做到 \(O(C^2N)\)。

但是发现：

1
2
3
4
5
6
000000
011000
000000
200300
200300
044000

可以 hack，所以改为矩形的四个边是有用的。考虑枚举上下区间，中间相当于问一定长度内完整线段的条数，可以 lower_bound() 搞，时间复杂度 \(O(C^3\log C)\)。

但是本地过不了 TC5~7 会 Timed Out，感觉是卡常？不管了。

B

第一眼就是二分答案 0/1 Check，先写了若干贪心和随机做法，样例都过不去。然后猜结论是每个 0 的块从右往左删，但是感觉不太对。就先过了。

之后回来写部分分，发现 \(N\le20\) 可以写状压，然后性质 C 可以完全贪心，于是拿了一半分。

C

一眼欧拉路，但是不会。

最后几分钟回来写状压，发现维护的信息太多不好合并，没时间写了啊。

遂 puts("-1");，赛时代码：// 记得上次模拟赛多测 -1 得了 10 pts。

D

完蛋数据结构吗，考虑 3 pts 的暴力，写了个树状数组。

估分：\(90+50+Rp+3=143\)；实际：\(90+50+4+3=147,\mathrm{rk 4}\)。

1
2
3
%%%   std.  %%%
%%%  HA-122 %%%
%%%  HA-123 %%%

赛后

A 太完蛋了，发现只有矩形上边界才能作为枚举上边界，但是全加入会导致 \(O((2C)^3\log C)\) 直接到了 \(10^{10}\) 级别，寄。

D \(O(N^2)\) 过了一车大佬，%%%。

讲评

A 可以双指针搞，就把 \(\log\) 也省了。啊啊啊什么赛时超大复杂度啊啊啊。

B 结论和当时猜的差不多，啊啊好难受。然后还有一个神奇转化之后扫序列，感觉很神奇。

C 正解是生成树从下往上跑做合并边，然后给所有奇点连上虚点直接跑欧拉路。感觉两步都是最近练的但是赛时没想到。

D \(K=4\) 是莫队二次离线 + 根号分治，然后缝合了 \(K\in\{2,3\}\)，感觉这种大数据结构还是好难。

总结

  • 复杂度优化谢谢喵！A 大常数带 \(\log\)，D 的不带修 BIT 导致很难受，然后 D 的前缀和还和正解有关好像。
  • 别搞乱搞，好好写部分分，不然比赛直接完蛋。

NOIP 模拟赛 #9

信心赛

赛时

A - cut

先手玩了玩小数据，发现了一个 DP 式子是 \(f(i,j)=f(i-1,j)+f(i-1,j-1)\)，获得部分分。然后考虑对着打的表找规律，发现和组合数有点关系，但是边界不一样，还是没推出来。

B - plan

第一眼发现这个题是真的水，因为它 \(t\) 一定并且可以分开做。考虑把 \(d_i\) 映射到 \(\operatorname{num}(d_i)\) 按照反悔贪心板子直接做就行了。

赛时 14:18 建的 plan.cpp，然后 14:29 就建 plague.cpp 了，这不比 A 简单。

C - plague

看到题目限制感觉是建最短路树，但是要求 \(1\to d\) 字典序最小不太会。睁开眼看了一下发现让求的是 \(d\to 1\) 字典序最小，那就直接会建了。

然后开了个 struct 造了两颗树，处理一下重复然后暴力跳 \(fa\) 就好了。

然后发现优化是个树剖板子，考虑 SegTree，发现 SegTree 写挂了，于是改 BIT，然后就有了抽象的：

1
2
3
4
5
6
7
struct SegTree {
  int p[N];
  void Add(int x, int d) { for (; x <= n; x += x & -x) p[x] += d; }
  int Ask(int x) { int res = 0; for (; x; x -= x & -x) res += p[x]; return res; }
  void Modify(int p, int l, int r, int ql, int qr, int d) { Add(ql, d); if (qr != n) Add(qr + 1, -d); }
  int Query(int p, int l, int r, int x) { return Ask(x); }
};

然后还有一个小时，没看 D，回去推 A 的式子，发现死活不会。

赛后

期望得分：\(60+100+100+\frac{10}{10^9+7}=260+\frac{10}{10^9+7}\)。

实际得分：\(60+100+100+0=260\)。

一看 A 咋一车 \(90\)？一问发现和我推的 DP 好像不一样，动一下脑子发现我赛时推结论的时候式子给的是 \(f(i,j)=f(i-1,j)+f(i,j-1)\)，按着这个推能推对就怪了。

一看 D 咋一车 \(50\)？一问玩出来 \(f(i)=\operatorname{lowbit} x\) 就有 \(50\) 分，直接亏死。

讲评

A 格路计数可以推一推，也可以直接在表上推，然后优化一下组合数求和算法就过了。但是你推的时候用另一个式子就是另一回事了……

B / C 就是俩板子，B 还有个普通贪心不反悔的写法，但是好像要上大数据结构，再想想吧。

D 推个式子然后跑拉格朗日插值……不管了。

总结

  • A 很可恶，赛时一定要保证自己在做的事情是在对的基础上的，不能瞎搞。对着一个错的式子推只能推不出来。
  • C 其实不用剖，dfn 序即可，写复杂了，还多了一只 \(\log\)，导致比暴力跳父亲还慢，因为随机树高是 log 的。
  • D 赛时应该玩玩 \(f(x)\) 的性质拿点分的 aaaaaa，但是赛时摆了。

NOIP 模拟赛 #10

题目链接（内） 题目链接（外）

最唐的一集。

赛时

看了 A 题，感觉这个好像可以二分答案，然后发现不太能 check，然后想要二分答案后二分左端点，发现没有单调性。

然后又想枚举一个集合里的数当基准值，让每个集合选的都尽量靠近这个数，感觉就很假。

然后又想改一下策略，考虑 calc(x) 表示每个数都是大于 \(x\) 的最小数，没有就是最大数的答案，然后拿这个函数跑样例，发现是 \(13,13,13,1,1,1,1,1,1,1,1,1,1,1,1,1,1,4,4,4,4,4\) 这个样子的，感觉可以跑三分。

又造了一堆样例数据，验证函数确实是长这样的，遂写三分。

然后过了 calc() 函数写的有点问题一直 RE，调了一会才过小样例，测大样例但是输出比答案大特别多，已经一个小时了，先跳了。

然后去看 B，发现是个构造，也先跳了。

看 C 是个期望，先写了个暴力，然后打了一下答案的分子的表，想找一下递推式，发现找不到，就回去调 A 题了。

打出来大样例最后的左右端点，发现到了 \([-1000000000,-999999998]\)，然后知道是因为有很长一段极限值的函数值是相同的，三分就炸了。

然后考虑限制三分的初始 \(l=\min\{s_i\}\;r=\max\{s_i\}\) 发现还是有这种情况。

于是搞了一下离散化，不知道为啥 lower_bound() 炸了，调了半天，然后发现离散化还是不能处理。

然后考虑了一下 \(O(n^2)\) 的 DP，\(f(i,j)\) 表示到第 \(i\) 个集合，最小值是 \(j\) 最小的最大值，转移很简单。

然后看见有一个 \(n\le 2\) 的点，特判了一下。

然后去写 B 题，找到了 \(n=1\)、\(m=1\) 的通解，然后看到有 \(n,m\le4\) 的点，手玩了一年玩出来了 \(n,m\in\{2,3,4\}\) 的答案，放 checker 里也都对了，感觉答案也是最优解，发现后边答案都是 \(nm-1\)，输出了一下骗分。

然后去写 D，发现像是个树形 DP，但是只有半多个小时了，就先写了个暴力，令 \(f(m)\) 表示选择 \(m\) 的点作为一次的价值，初值直接 DFS 就可以，然后发现转移需要有一个 \(f(m)\xleftarrow{\max}f(m\oplus s)+f(s)\) 的子集枚举，复杂度 \(O(3^n)\) 到了 \(3\times10^9\) 的复杂度，本地跑 \(7000^{+}\text{ms}\)，然后开始卡常，卡到了 \(5000^{+}\text{ms}\)，发现还是过不了。

然后把 freopen() 加了文件名，然后看了一眼 B，发现没有 \(m=1\) 的点就把特判 \(m=1\) 然后输出答案的部分删了，就交了。

赛后

因为在 OJ 上，直接就有分了。

A 就是写的 \(60\) 分。

B 发现 \(n,m\le4\) 的点寄了，然后看 SPJ 的反馈好像是输出有问题，发现是没有写 \(n\in\{2,3,4\},m=1\) 的点，因为 check 的时候有 \(m=1\) 的特判就过了，删了直接 GG。

C 题挂没了，点开看发现交的是打表。啊啊啊啊啊啊啊啊啊。

D 题也挂没了，点开看发现是 CE，？，然后发现是卡常没用 bits/stdc++.h，但是有 sort() 没加 algorithm 库，啊啊啊啊啊啊啊啊啊。

于是出现了 ./rank11。

讲评

A 是个双指针，感觉赛后听把所有元素放在一个序列上马上就会了，赛时还是太唐了，一直在像二 / 三分。

B 是个推性质，然后递归就好了，赛时也玩了一点感觉，感觉比较对。赛时感觉还是没时间细细推了。

C 是个容斥，感觉比较好理解，但是赛时感觉真是想不到。

D 部分分很多，正解是线段树合并优化 DP，感觉还是时间问题没写暴力 / 性质 DP 而且暴力也太唐了。

总结

  • 时间分配太重要了，感觉今天在 A 题浪费时间太长了，后边好多能写的都没写。
  • 容斥 和 线段树合并优化 DP 还是要多练，太不熟练了。
  • 赛后一定要测试版本，跑一下大样例（checker），挂了 \(45 \text{pts}\) 太失误了。
  • A 题，感觉还是在一个思路里想太久了，赛时想到了枚举最小的集合那种思路，但是一直在想三分，就没有仔细想。
  • 乐：正义了一些不当行为后，得到了 rank 9 的 好 不好成绩。（bushi

NOIP 模拟赛 #11

题目链接（内） 题目链接（外）

《信心场》

赛时

\(7:40\sim 8:00\) 先看了 A，欸发现中位数可以套个二分，二分后发现是区间翻面求全局最大，这个套路之前见过，可以让 \(x_i=[b_i>=p]-[a_i>=p]\) 然后对 \(x\) 跑最大子段和就好了。

\(8:00\sim 9:20\) 看了 B，因为数据范围寄了以为是 \(n,m\le3000\)，感觉不太会，看到 C 第一眼感觉把剩下的边跑 Tarjan 缩点，然后倒序对于加入一条边分在一个边双、在一个树、不在一个树三类，然后开始写，发现合并两个树需要启发式合并重构树，然后又要维护一堆边双和树的并查集，感觉很寄，感觉用了太长时间了，也知道 B 的范围了，于是回去写 B。

\(9:20\sim 10:00\) 开始写 B，发现肯定有一位是可以状压枚举，另一位还是只会暴力，然后发现是要求最后值恰好等于 \(s\)，可以双向搜索。遂写，发现能过样例，然后跑了 \(12\times 12,\texttt{YES}\) 的大样例，用了三秒多，发现搜索的时候可以剪枝，于是加了一个发现可以跑进一百毫米，手造了一个 \(15\times 15,\texttt{NO}\) 的样例，发现还是要跑两秒多。这次学精了不卡常了，写了个卡时输出无解。

\(10:00\sim 11:00\) 还有一个小时，感觉可以冲一冲 C，发现直接从全是单点开始当作森林开始做就不用 Tarjan 了，打了亿会中间变量，调过了小样例，跑大样例发现直接 GG，就剩一个小时了，决定写暴力。

\(11:00\sim 11:25\) 写了个每段连续询问前跑 Tarjan，然后求答案，过了大样例。

\(11:25\sim 12:00\) 写了 D 的树形 DP，发现样例没有树的，手造一个发现 WA 了，于是写了个 \(O(n^k)\) 的暴力，然后考虑跑 \(O(n^n)\) 暴力乘上系数，算了半天发现系数不是 \(k\choose n\)，直接 GG，最后两分钟暴力测了一下树形 DP，发现对了，缝合了一下树形 DP 交了。

赛后

期望得分：\(100+100+30+40=270\)

实际得分：\(100+100+30+0=230\)。

咋会事呢？看了一下提交记录发现 D 前边的暴力都是能过暴力点的，然后加上树形 DP 之后多读入了一次 \(n,m,k\) RE 了，啊啊啊啊啊。

然后发现 B 不用双向直接暴力 + 剪枝就能过，啊……

讲评

  • A、B 就是写了正解，没啥说的。
  • C 正解是跑一个以删除时间为关键字的最大生成树，这样就不用每次重构了，直接暴力合并就可以了，赛时写的重构子树，太麻烦了，没调出来。
  • D 发现暴力的复杂度其实是 \(O(k^n)\)，\(n=2\) 的 \(k=100\) 可以过，\(k=1\times 10^9\) 是要特判的，然后树形 DP 的转移也一样，赛时寄了有点可惜。

总结

  • 感觉这一场在 C 上用时太多了，而且直接就是冲着正解写的，没从一定部分分优化。而且一直在调代码，没有想优化减少代码难度。而且最后没时间写部分分了，最后有点着急就把暴力挂掉了……

NOIP 模拟赛 #12

题目链接（内） 题目链接（外）

\(\large 天^{-1}\in R\)

赛时

\(7:40\sim 8:10\) 先看了 A，感觉比较可做，想了很长时间，还是不太会，就先把后边的题看了看，感觉都很难，考虑先写一下 A 的暴力。

\(8:00\sim 8:40\) 写了一下 A 的状压暴力，发现挂了，调了一会发现是没有判断一列有没有填到上界。过了样例，发现这个感觉是从大往小插入每个数字，考虑分开计算每个数的贡献。手玩了一下发现有算重，先不想了，去写 B。

\(8:40\sim 9:40\) 发现 B 的数据很奇怪，先写了一下 \(k=1\) 的 \(\text{Subtask 3}\)，然后以为 \(\text{Subtask 7 & 8}\) 能 hash 读入，然后发现没给 .out 文件 <。本来想写状压 唐完了。本来想写状压 DP，发现时间是 \(O(T\cdot 2^nn^3)\) 的，跑步过去，于是只写了 std::next_permutation() 的枚举全排列暴力。看到 \(\text{Subtask 5}\) 图是一条链，感觉能在序列上做 DP，写了一个 \(f_i=f{i-1}+f_{i-3}\) 之后发现起点不一定是链的端点，考虑枚举起点，然后一定是左右横跳模拟到可以使用 DP 数组，但是没调出来，回去看 A。

\(9:40\sim 10:00\) 有玩了几个样例发现没重，一看上边演草过程把 \(12\times 12\) 算成 \(244\) 了，然后手玩了暴力拍了一下发现对了，于是开始写，过了所以样例，喜。

\(10:00\sim 10:30\) 去写 B 的链上 DP 了，但是调了半天发现还有很多情况没写，感觉先把后边 C、D 的暴力写了再说。

\(10:30\sim 11:00\) 写了 C \(O(nm\log\sum|s|)\) 的暴力，顺便加了一个判断连续询问之间不再排序，过了小样例和性质分样例。

\(11:00\sim 11:20\) 去看了 D，感觉不会，也不想写 \(2^{n^2}\) 大暴力了，回去改了改 B 的链性质，但是还是过不了。

\(11:20\sim 11:55\) 跑了一下 C 的 \(n=3\times10^4\) 的样例，发现 WA 了，有点慌，开始调，发现调不出来。于是写了更暴力的，发现没变化。慌了，越调越急。

\(11:55\sim 12:00\) 发现测大样例的时候的 freopen() 写寄了：

1
2
3
freopen("C:\\Users\\Lenovo\\Downloads\\down (6)\\down\luminous\\ex_luminous2.in", "r", stdin);
//                  和 .in 不在一个文件夹 ↓             ↑ 少一个反斜杠
freopen("C:\\Users\\Lenovo\\Downloads\\.out", "w", stdout);

啊啊啊啊啊啊啊，一直是在 C:\\Users\Lenovo\Downloads\down (6)\down\luminous 路径下启动 CMD 跑的 fc ex_luminous2.out .out，发现虚空调试了半天，无语了……

赛后

得分 \(100+13+0+0=113\)，但是 \(\mathrm{rnk} = 3\)（?）。

B 没挂，但是 C 的无修改性质因为直接 std:sort() 没上 Trie，T 了，D 因为数据范围单元格合并没居中，扔了个 puts("NO"); 没分。

讲评

  • A 就差不多，发现因为每行 / 每列只有一个限制，就是在计算贡献时填进去的，所以没有重复。
  • B 正解是把 \(O(2^nn^3)\) 的状压 DP 改记忆化搜索，由于题目限制 \(k=2\) 所以状态数量是 \(O(2^7n^2)\) 的。然后说如果是 DFS 加剪枝有 \(25\text{ pts}\)，感觉亏啊。
  • C 是上个 Trie 然后把询问扔 Trie 上跑，把操作保留叠加一下直接拿原串跑，然后字符合并再维护一下，感觉比较困难。
  • D 是取 \(1/4\) 的矩形看作邻接矩阵，然后发现构造是欧拉回路。对于输出方案再观察一下输出是 \(2^k\)，于是发现把 ? 建立生成树，非树边随意，树边调控度数。感觉比较智慧。

总结

  • 写暴力要细致一点。 比如这种状态少的 DP 要上记忆化，枚举全排列后 Check 分在 DFS 的过程中剪枝，这些套路不是很熟。可能打 ABC 正解就是暴力的那种数据很小的题打上头了……
  • 一定注意调试过程。 比如这次 freopen() 位置错了一直没输出到 fc 的文件里导致调半天发现没变化就很寄。
  • 注意心态。 这场难度有点离谱，赛时有点慌，还是要注意心态管理。《难了大家都难》。赛时就在想 @Sorato @PineappleSummer @Hthntd @... 是不是已经都 200+ 了啊啊啊。

NOIP 模拟赛 #13

题目链接（内） 题目链接（外）

又唐了。

赛时

先看了 A，感觉串串不太会，先胡了个 \(n=1\)、\(S_i=\texttt A\) 的性质。然后想想，发现他要求是回文串，那么一定有长度至少是 \(n(m-1)\)，然后剩下的是一个 Border，但是手玩一下发现有点假，但是发现如果把 \(S\) 复制一遍，对这个长度为 \(2n\) 的字符串跑 Border 就对了，所以答案就是 \(n(m-2)+|\mathrm{Border}|\)。然后不会烤馍片，考虑 hash 但是又怕卡又怕 TLE，于是胡了一个烤馍片，发现假了，改了改，过了大样例。

然后看 B，发现是个大数学题，写了个暴力，看见有一个 \(k=1\) 的性质，感觉这档答案是关于 \(k\) 的一个三次项式，于是暴力跑一下前 \(10\) 项答案，然后枚举系数算一下，扔后台跑了。

去看 C 了，感觉可以写个 \(O(n^2)\) 的 DP，但是不会。发现这个答案一定是满足继承上一次的，感觉 \(O(n^2)\) 去写 DP 很蠢，每次模拟找到当前连通块内那个关键点的路径上的最短边，断开并加上贡献就可以了，也是 \(O(n^2)\)。

然后看了一眼 D，第一眼想了一个 \(O(n^3)\) 的暴力，但是没有给那个点，于是回去看 C。

发现 C 的断边操作不好维护，于是考虑加边，每次相当于选当前连通块的最大的边加上，然后启发式合并 + std::set 维护连通块出边就好了。发现没过大样例，用暴力拍了一下发现会在运行时 RE，查了一下发现又是后 e[x].size() 是 \(0\) 但是查了 .rbegin()，发现是因为算 \(y\) 时异或的那个 \(x\) 因为又并查集操作不知道是谁了，想了一下发现边 \((u,v)\) 中 \(u,v\) 一定有一个在当前连通块，另一个就是 \(y\) 了，过了大样例。然后发现因为启发式合并插入到 std::set 里了，时空复杂度是 \(O(n\log^2n)\) 的，看了一眼数据范围是 \(5\times 10^5\)，算了一下 \(n\log^2n\approx 1.8\times 10^8\)，感觉不太能过。

然后写了一下 D 的暴力，发现大样例会 WA，然后换种写法还是会 WA，不管了。看见 B 的式子还没跑出来，发现可能和 \(n\) 的奇偶性有关系，于是又加了四个参数跑，感觉不太能跑出来。

最后半个小时测了一下 C 的极限数据，发现本地跑不知道啥原因会 RE，怕是空间炸了，STL 大容器都改了 std::vector<> 方法开。

赛后

预计得分：\(100+40+70+0=210\)；

实际得分：\(90+40+100+20=250\)。

注意到 A 挂了，看一下发现是特殊性质写挂了，啊啊啊啊啊啊。

然后 C 过了，分析一下复杂度发现根本跑不满，一个 \(\log\) 是启发式合并的比较小，然后第二个 \(\log\) 是对 std::set<>::size() 做的，过程中也不会太大。

D 混了 \(20\) 分，不太理解。

讲评

  • A 差不多。
  • B 还是在推式子，对于 \(k\neq 1\) 的把贡献拆开算，最后得到还是关于 \(n,k\) 的多项式。
  • C 正解是跑 Kruskal 重构树，每个边节点的贡献时间可以对两个子树的点的加入时间做 \(\max\ \&\ \min\) 得到。
  • D 是建成树。每次修改 \(p\) 颜色对答案的影响只和 \(p-1\ \&\ p+1\) 有关，写暴力和性质这个很有用，也挺显然的，赛时没想到。

总结

  • A 部分分写挂了导致挂分出现很多次了，以后要注意。这场跑了两个性质各跑了个一组样例和正解拍了一下就走了，感觉这样很危险。
  • B 这种大推式子感觉 NOIP 应该不会考吧…………
  • C 赛时写的有点太麻烦了，导致调了很长时间。调出来了还好，调不出来就比较寄，感觉赛时还是应该再想一小会有没有更简单的做法。
  • D 唐了，赛时没想到【每次修改 \(p\) 颜色对答案的影响只和 \(p-1\ \&\ p+1\) 有关】，暴力写的就不太好，也就没想 \(r=m\) 的性质了。

NOIP 模拟赛 #14

题目链接（内） 题目链接（外）

啊啊啊啊菜死了。

赛时

先看了 A，考虑到他有个 \(A_i \neq A_j\) 的性质，发现 \(B\) 有的因子 \(A\) 中一定不选，感觉很对。对着小样例玩了玩发现，然后发现再剩下的序列上判断 \(\sum\limits_{i=1}^{n'}\dfrac{\prod_{j=1}^{n'}A}{A_i}=\prod\limits_{i=1}^{m'}B\) 就行了，尝试通过大样例证明结论，给两个序列跑了一下排序，手玩了一下相互消除，发现最后完全不对，于是放弃。埋下伏笔

然后去看 B，看到 \(n\le 5000\) 感觉正解是个树背包。但是这个限制感觉太多了，不太会暴力 DP，先跳过了。

看了一眼 C，是数据结构题，于是先写了个暴力。然后发现 a 性质可以做个差分求平方次数，单个位置答案就能欧拉定理算，然后跑个前缀和。考虑 b 性质，发现不会。

然后看了一下 D，会 \(O(nk)\)，发现 \(k=10^5\) 可以线段树随便搞一搞，先放着去再看看 A。

A 写了个暴力，然后推推式子。看见他 \(n,m\le 3000\)，感觉像是枚举 \(A\) 选多少，但是感觉问题没转化出来，于是写 \(O(2^n)\) 暴力，发现要高精，但是没让输出，于是对着仨质数直接跑。又写了 \(O(nB)\) 的 DP，然后发现非常蠢因为 \(B\le 10^5\) 时 \(n\le 16\)。

写 D 的线段树。 没过样例，发现 seg_col.Build(1, 1, m); 写成了 seg_col.Build(1, 1, n);。 没过样例，发现 seg_col.Query(1, 1, m); 写成了 seg_col.Query(1, 1, n);。 没过样例，发现 Bulid(p << 1, l, mid); 写成了 Bulid(1, l, mid);。 没过样例，发现 Query(p << 1, l, mid); 写成了 Query(1, l, mid);。 过样例了，发现已经十一多点了 /kel。

去写 B，\(t_i\) 不太好处理，于是尝试先做 \(t_1=10^9\) 的点，然后再嫁接到 \(n\le 16\) 上。开始推式子。然后发现有排除法确定的方案，于是开始增加维度。过了样例（样例好像就没有选 \(t_i\) 的），手玩了俩 hack，调了一会过了，感觉很对。然后发现排除法好像能做好多次，于是假了。

赛后

LJH 大佬太强了，%%%%%%。

看了 @yxans 大佬 A 的注释，发现赛时最开始猜的结论是对的，但是不知道为啥过不了大样例。

然后去吃饭，发现手玩 \(A\)、\(B\) 互相消除的时候把 \(\{1,2,4,5\},\{1,2,3,5\}\) 这样的判了相同。（因为这个不同出现的位置没有单调性，不能二分 /kel）啊啊啊为啥赛时不老老实实写代码去重啊啊啊啊。

然后发现 D 不用上线段树，用 std::set<> 维护一下区间有的操作，每次取 .rbegin() ，类似差分打标记就能维护了，感觉太唐了。

讲评

  • A 有一个证明，感觉很对。
  • B 正解的确是树背包，感觉树背包还是不熟。
  • C 是根据 \(2^k\bmod \varphi(P)\)（\(\varphi(998244353) = 998244352 = 2^{23} \times 7 \times 17\)） 的循环上数据结构，这个思路实在没想到。

总结

  • 猜的结论不要乱否定，可以从正确性上推一推，跑一下大样例，不要瞎手玩，容易玩脱。
  • 不是哥们，你咋天天不管啥题都想上线段树呢。

NOIP 模拟赛 #15

题目链接（内） 题目链接（外）

做题不看题，_ _ _ _ _。

赛时

先看了 A，感觉很有智慧，感觉答案一定是连续的七个，然后过了所有样例。然后意识到了这场样例可能会比较水。然后手玩了一组，发现后六个一定是连续的，然后可以直接二分找第一个。然后考虑第二个第三个可能会不连续，但是手玩不出来，感觉很难卡。

之后 Laru 给了俩 hack，发现有这样的情况，然后，发扬人类智慧，发现第二个和第三个相邻不会太远，于是枚举这个间距，加个卡时。

看 B，感觉就是每次删去最短 Border，写了个自然溢出 hash，发现过了所有样例。然后意识到了这场样例可能会特别水。但是简单证明了一下感觉很对，考虑去写 C。

看 C 发现 \(1\sim 4\) 的 \(O(n^2)\) 和 \(5\sim 12\) 没有删除的很好写，第二个可以上并查集，但是写寄了，发现可以上线段树，然后发现又寄了，然后再线段树上模拟路径压缩。糖丸了。然后发现额外边 \(\le 10\) 的可以胡搞，已经 \(80\) 分了，去写 D 了。

交互，发现每次问俩 if (ASK(i, i, j) == 2) res[i][j] = res[j][i] = 1; 只需要 \(4950\) 次就问出来了，有了 \(30\) 分，感觉优化前途很大，发现每次先把 \((i,i+1)\) 问出来，在 ASK(i,i+1,j); 可能一次问出 \((i,j)\) 和 \((i+1,j)\)，感觉太对了。就改了，本地测试，发现次数在 \(3700\) 左右，能有 \(80\)。

感觉这场可能人均 \(350^{+}\) 了，感觉 A 没把握，于是开始想 A，推了推式子，发现中间的确不会太多，于是走了。

顺手写了 B 的双哈希。

然后又看了看 D，能不能再优化优化，然后加了若干随机防止卡，但是感觉没太大用处，欸不对啊你本地生成不是随机的吗…… 这时看了一眼题，发现 需要保证 \(u,b,w\) 两两不同。啊啊啊，完蛋了，寄。

赛后

期望得分：\(100+100+80+0=280\)，

实际得分：\(100+100+70+0=270\)。

C 的 \(n,q\le 10^4\) 被卡常了，#pragma GCC optimize(3, "Ofast", "inline") 就过了。

讲评

  • A 有一车智慧做法，感觉这题……
  • B 对了，但是没卡 hash……
  • C 可以改为边覆盖，求最左边的 0 边，线段树维护之，这种套路之前见过。
  • D 先随三个点知道相互情况，然后把其他点求出来 / 合并成一个只有两种情况的整体。NOIP 不考交互吧……。

总结

  • 不是哥们，你咋天天不管啥题都想上线段树呢。
  • 不是哥们，你咋看不出来线段树的题啊。感觉 C 这种向已知树上加边的都可以用边覆盖。
  • D 感觉最后还能挣扎一下把最开始三个随出来，但是最后太慌了，感觉还能拯救一下，感觉还是没时间了。啊啊啊你不要在眼瞎了啊啊啊！！！

NOIP 模拟赛 #16

赛时

A 题面是依托，观察样例 & 样例解释猜了一个性质，然后发现没有大样例，有点慌，想了一下感觉式子挺对的。

B 看了一下发现好像可以直接，每次根据询问走其余四个方向，但是感觉时间不太对，然后发现要求最短路，于是边算边维护了一下最短路，然后就到 \(O(nm)\) 了，样例一遍过，但是没有大样例。

去看 C，发现不太会，如果没有逆序对的化就是康托展开，但是有逆序对就不会了。打了个暴力。

这时候发 A & B (& C) 的大样例了，发现 A 对，B 出现了在 .empty() 的时候取 .front() 的情况，然后感觉不应该出现这样的情况啊，但是 fc 出来发现没问题，Ctrl + F 一下发现答案里没 !，感觉样例水了。此时还没有发现问题的严重性。

然后去写 D，发现部分分送了一车，一个一个写了写，发现有 \(70\)，然后暴力性质拍了一下发现对了，然后发现没 D 的大样例，有点怕暴力寄了。

回去看 C，打了个表想找一下 \(n\) 下不同逆序对数量的序列的个数，发现有一点前缀和的感觉，但是不对。然后把 D 的大样例测了一下，过了。

想在看看 D，感觉是把询问挂 \(T\) 上跑换根，但是不太清楚，感觉不如去想 C。

感觉可以从小到大插入这些数字，但是不会保证字典序最小，于是寄了，感觉还是要推那个式子。

赛后

期望：\(100+100+15+70=285\)。

实际：\(100+50+0+70=220\)。

B 要求的是在没有指令的情况下最短，添加指令到了少了最短路长了，所以寄了、

D 写的是 \(O(N!N^2)\) 的，但是好像 \(O(N!N\log N)\) 也过不了，好像不卡常正常是要 DFS 每次加入时计算逆序对。

讲评

  • A & B 不管了。
  • C 是吧那个函数的递推式找到，把它当成正常排列排序里的阶乘替换成这个函数。
  • D 每次换根只会影响两个点的归属，开桶维护就好，细节好多 QWQ。

总结

  • 认真读题，注意细节。
  • 推式子还要练练。
  • 《题目难度不一定升序排序》，感觉 D 赛时可做，但是没细想。

NOIP 模拟赛 #17

题目链接（内） 题目链接（外）

边睡觉边打比赛

赛时

先看 A，由于代价是 \((r-l+1)^2\)，感觉每次一定选取最长一段做，然后不会了。想了十几分钟反应过了代价最小是要每次选最短区间，即单个数字，这下会了。然后考虑用 Exgcd 跑出来，然后发现最有时候 \(x\) 或者 \(y\) 是接近 \(0\) 的，然后写了一会求最小的 \(x\gt 0\)，发细节太多，不会。发现最终答案是关于通式里 \(k\) 的一个单谷函数，于是大胆三分。但是过不了大样例，扩大三分范围错更多，考虑是三分时候爆 long long 了，于是把界改到了 \(10^{16}\)，过了。

看 B，先写了 \(1\sim 5\) 的特判分，用了一会时间。然后发现 \(9\sim 15\) 可以 std::bitset<M> 压一下，然后想一下 \(n=4\)，发现不会。

看 C 感觉像是容斥，暴力是 \(Bell\) 数，写了，然后去看 D，写了个 \(O(nq\log n)\) 暴力，看数据范围感觉正解是莫二离，但是不会。

然后感觉 A 不太放心，想了半天 A 单谷性质能不能证明，感性理解了一下感觉挺对。然后开始瞌睡，yizheng 过来发现已将十一点多了。

然后发现 C 有 \(k\in\{2,3\}\) 的分，写了一下，交了题。然后开始推 \(k=4\) 的暴力 DP，但是没推出。

然后 Laru 说我 T2 CE 了，跑了一下发现没问题。然后扔 Dev5.11 里发现 using 中用 , 和 if(int d=(); d!=1) 寄了，改了交了。又说是 CE，说是生成器的 uint64_t 寄了，发现没加 <cstdint>。

赛后

期望得分：\(100+48+20+25=193\)，

实际得分：\(80+48+20+25=173\)。

发现 A 边界给的 \(10^{16}\) 还是小了，改 \(10^{18}\) 过了。

@Sorato 过了 D，ZZZ,JQK。

讲评

  • A Skipped。
  • B 跑同余最短路，随机生成数据保证 \(\min a=\dfrac {m}{n + 1}\)，感觉挺对的，赛时没有注意到数据随机的性质。
  • C 是容斥 / DP，发现状态数比较少，然后跑 DP，感觉不会……
  • D 是莫二离板子，但是赛时不想 / 敢写。

总结

  • 边界控制好，别炸也别少。
  • 注意题面的性质，数据随机有用。
  • 容斥还是不会，练吧……
  • 赛时应该至少写了 D 的暴力莫队的，暴力还是没写满。
  • 赛后发现编译用 Profiling 就可以避免这个 CE 了，一定要注意 CE 啊 qwq。

NOIP 模拟赛 #18

题目链接（内） 题目链接（外）

IOI 赛制，但是（几乎）没部分分。

\(7\) 道题 \(7\text h\) ，题目按照字典序排列。

赛时

先睡觉，等带榜。

\(7:50\) 醒了，发现没过题，于是开始看。发现 A 感觉一个连通块可以随便互换，于是写了个维护 \(siz\ \&\ cnt\) 的并查集，过了。

然后去看 B，感觉像是原题，但是不会。然后看了一下 C & D，发现 D 说“题目名叫这个是为了凑字典序”，于是怀疑难度还是递增的，于是回去看 B，看了一会发现不会。

这时候看了一眼榜，发现 F 有很多尝试，于是开始写，发现是个诈骗，跑个 Topsort 即可，交了过了。

然后看到 G 尝试比较多，开始写，突然发现这个数据范围是 \(N\le 200,M\le 5\times 10^4\)，欸这个数据范围就非常暧昧啊，感觉 \(MN^2\) 卡卡能过，先写了个堆的 Dijkstra 和随机删边卡时，但是只有暴力分，于是开始 憋尿 卡常。卡了 \(80\min\) 卡到了 \(80\text{pts}\)。

然后又卡了半小时，没有，看榜发现 D & E 有人过了，于是开始看 D，感觉这个构造是个完全图，然后发现不会了，然后又想了一会，发现是欧拉路，于是开始写，写了快一个小时过了样例，交上去 WA on test 2……去吃饭。

回来又调了调 D，调了一个多小时到两点，发现这个是欧拉路径，不一定要从回路上截取，于是 GG。

赛后 & 讲评

  • A & D & F : Skipped.
  • C 是跑 Boruvka，一会好好学学。
  • E 是个 2-SAT，但是赛时想的是独立集什么的就不会了。
  • G 正解是改边的时候讨论一下是否是树边，赛时想到了，但是一直在卡常。

总结

  • 啊啊啊啊啊啊啊不要再卡常了。
  • 调试代码时间太长了，D 赛时回路的写法也是一个多小时才过 Checker，太浪费时间了。
  • 建模，赛时看 E 是二分，但是没往 2-SAT 上想。

NOIP 模拟赛 #19

题目链接（内） 题目链接（外）

咋又寄了呢。

赛时

先看了 A，感觉有点难。然后发现这个三角形经过若干操作后的状态应该是很少的。猜测是最多做三五次，于是考虑 BFS。然后开始写三角形类，写了个读入、旋转、对称、差值，然后开始 BFS。发现没输出，调了半天发现一车 non-void 函数没写返回值，调完已经八点半了，感觉有点寄。

看 B，发现是这个玩意，首先发现贪心选原串作为一个运算数一定不劣，然后就变成了找一个字符串，和原串的反串匹配，高位优先最多的匹配，发现不会，于是考虑好像可以直接把一个 1 填在第一个 0 上，所以一定是把之前出现过的一个 1 做为开头的一个后缀，于是发现还是不会。考虑 KMP，发现完全不一样，于是考虑 KMP 的思想，每次从移动左指针时继承一下上一位的一些信息，发现还是不会，所以写了个 \(O(n^2)\) 暴力，走了看 C。

发现看起来很难，于是先跳过写 D 的暴力。发现 D 前边 \(25\text{ pts}\) 随便写，后边满二叉树和链的性质不会。于是回去写 C。

先写了个 \(O(c^n)\) 暴搜，发现不会 Check，然后考虑一会发现可以贪心，开始写，过了小样例，然后发现这个 \(n\le 10^{18}\)，但是 \(X\le 1000\)，并且贪心的 Checker 感觉 DP 的状态数就不会很多，于是感觉是矩阵乘法加速 DP。于是考虑先先暴力 DP，开始推式子，发现推不出来。

然后感觉很寄，回去想 B，但是还是不会使用之前的信息，GG。

赛后

\(100+50+20+25=195\)，没挂分。

又被 LJH 大佬虐了，orz。

发现 B 过了一车，问了一下发现选第二个串还是贪心，去填满紧跟着第一段 1 后边的 0，感觉一下确实很对。赛时脑残了 aaaaaa，这和 KMP 有个毛的关系啊……

讲评

  • A: traingle & clac.
  • B: Skipped.
  • C 的确是赛时我的思路，状态也一样。赛时被卡在转移系数上了，没想到通过上下界去卡区间算系数。
  • D 是 \(\text{SQRT DATASTRUCURE}\)，QWQ。

总结

  • 别把简单题写复杂，注意代码最好别出现一堆笔误，太难调了。
  • 感觉 B 题这种比较富有智慧 （?）的题每次都是很长时间写出来……有点寄。
  • C 赛时就差一步，但是感觉赛时没有好好想，感觉还是没有好好利用（顺子 \(\lt 3\)）性质。
  • D 这种题感觉赛场上也写不动正解，但是部分分赛时确实拿少了。

NOIP 模拟赛 #20

题目链接（内） 题目链接（外）

糖丸。

赛时

先看了 A，感觉可以贪心每次能选最小值就选，感觉是 \(O(N\log N)\) 的，然后看见 \(N\le 5000\) 有点不敢写，想了一会感觉没啥问题，写了发现假了。有点慌，观察输出发现没有考虑选完 \(i\) 去选 \(j(j<i)\) 的方案，于是改成双重循环就过了，感觉这题好唐。

然后看 B，发现是原，于是跳了先写 C。发现是个大模拟，感觉细节也不多，开始写。中间看了一眼新 B，发现不会，于是继续写，然后对着 TC 1 和 TC2 调了一会，直接过了 TC 3~8。

然后开始看 B，感觉是找循环节，开始写，发现不会处理，开始调，没调出来，发现现在的写法是能拿 \(50\text{ pts}\) 的，加个 \(S_i=\texttt a, T_i=\texttt a\) 的特判就 \(70\text{ pts}\) 了，不是很想写了。

然后看 D，第一眼感觉是「线段树分治 + 动态开点线段树」，于是先写了个「线段树分治 + 暴力」，发现由于操作时有顺序的，他的顺序和分治后插入顺序不一样，就寄了。然后感觉是个「线段树分治 + 动态开点线段树套动态开点线段树」，看一下表发现十一点半了，感觉应该写不了了，于是写暴力，然后循环变量冲突了调了好久，GG。

赛后

期望得分：\(100+70+100+10=280\)。

实际得分：\(100+50+100+10=260\)。

B 的 \(x\) 用 int 存、用 %d 读写，糖丸了。

然后 @Sorato 说了 D 的 \(50\)，说是从后往前做，赛时想到了「从后往前做」，但是没细想。

总结

  • 感觉贪心题的还是要多考虑一下细节，然后考虑一下有没有这种把向外转移的选择给少了的情况。
  • B 题推循环节这种套路能看出来，但是细节赛时不太能处理。
  • C 题大模拟 NOIP 应该不考吧……。听说 fc 不忽略行末空格？
  • D 题就是要回溯一下思路，正解是线段树二分，赛时卡在对「修改」建树，考虑「操作」顺序的处理上了，正解直接在「操作」上建树就绕过了这个问题。

NOIP 模拟赛 #21

题目链接（内） 题目链接（外）

全真模拟赛，但是人品场。

赛时

\(7:40\sim 7:55\) 配编译指令 & 缺省源，不是哥们你四楼五机房咋保存个文件都要卡一下。

\(7:55\sim 8:40\) 先看了 A，感觉是通过算个斜率存存起来，最开始以为要实数下标，然后发现要求 \(h_i'\in \mathbf{R}\)，然后直接判，发现因为不一定经过 \((0,0)\) 就寄了。然后考虑枚举截距，发现不太可行，注意到 \(m\le 10^6\)，要求 \(f(n)\le m\) 的话斜率的取值只有 \(O(\dfrac mn)\) 种，于是有了 \(O(\dfrac mn \times n \times\text{umap})\) 的做法，过了样例。然后测了一下极限数据，发现本地跑了 \(2\text{ s}\)，于是开始卡常，考虑能不能把 umap 删了，发现不会，然后发现在四楼五机房，相信本地时间除以 \(2\) 没啥问题。

\(8:30\sim 9:00\) 感觉 B 不带修可以写个 \(O(n^2)\) 的 DP，设 \(f(i,j)\) 表示最大代价，发现转移不动，否则就是单次 \(O(n^3)\) 的了，于是跳了，先看后边的。

\(9:00\sim 9:30\) 写了 C & D 的暴力，同时发现后边两道题很容易胡搞做，先回去写 B 了。

\(9:00\sim 10:00\) B 写了个【二分答案 + DP Check】，是 \(O(n^3\log^2 n)\) 的，然后离线出来一个 \(\log\)，是 \(O(n^3\log n)\) 的。\(n=297\) 的样例跑了 \(3\text{ s}\)，感觉不太能过，然后发现答案和最初答案不会差超过 \(1\)，把二分界改到了 \(3\)，本地跑了一秒多。

\(10:00\sim 10:30\) 然后发现这个好像可以在 DP 转移的图上跑一些东西，讨论一下【决定答案点】和【经过点】，然后开始写，发现得写一车东西，遂放弃。

\(10:30\sim 11:30\) 开始写后边的胡搞。感觉 C 的平方性质决定他不会一步跨太长，于是每次只让往前选很少个，然后转移，调调参数过了所有样例。感觉 D 如果 \(k\) 比较大，那么最大数很可能在全局最大值相互组合中，所以写了个选取最大若干个数的，然后加个单(mul)调(ti)队(se)列(t)，再补个对 \(k\) 比较小的写法，调调参数过了所有样例。

\(11:30\sim 12:00\) 开始回去写 B 的脑残做法，发现要建图跑 Tarjan 然后 adlis bcaoisubfeq pwufya kjcbndasbc，然后再 jasdl aiufluibcl wygecly gflas，最后 askjdh sdlkf shafailu hfawye。

\(12:00\) 发现假了，开始摆烂，GG。

赛后

期望得分：\(100+50+[20,100]+[20,100]=[190,350]\)

发现 A 可以直接开数组然后咋加咋删避免 umap，唐了。又发现算的截距是 \(f(0)\)，但是题目要求是 \(\forall 1\le i \le n\) 有 \(f(i)\in [1,m]\cap \mathbf N\)，所以下界判错上界没判。

然后想了 C 的 hack。

实际得分：\(25+50+35+60=170\)，挂了 \(75\) 分，NOIP 补回来。

讲评

  • A 把直线理解成等差数列的话会更好想。
  • B 在固定 \((i,j)\) 时当前大小是固定的，然后就是在一个网格图上求 \((1,1)\to (n,n)\) 最大值的最小值，每次改变一行，重新计算即可。
  • C 是把一步拆成两跬（?），然后维护 \(2n\) 个李超树。
  • D 是按 \(k\) 分块，然后发现性质，把答案扔堆里，每次取合法的堆顶。

总结

  • A 炸了，赛时应该手玩玩，最好在拍拍，挂没了 TvT……
  • B 赛时想到了当前大小固定，但是没想到直接拿这个 \(a(i,j)\) 跑 DP；赛时想到了网格图，但是没想到把转移当作边权。
  • C 赛时也想到了刘畅树，但是没想到拆成两跬所以是个 \(O(n^3\log)\) 的就没想写。赛时没有发现两步是没有太大影响的。
  • D 这种题还是要多推推性质，按 \(k\) 分块赛时真没想到。
  • 赛时还是要拍一下，A 和 D 的 \(k\le10\) 都挂了。

Updata

订题 B 写的刘畅树，被卡常了，调死了还是 \(\color{red}\texttt{Time Exceeded}\)。

我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了我错了

NOIP 模拟赛 #22

题目链接（内） 题目链接（外）

喜欢贺板子的小朋友你们好哇。

赛时

\(7:40\sim 8:10\) 先看了 A，感觉是从大到小填，填入哪一个串是按某个东西贪心，然后玩了一下，发现是现有 \(a,b\) 的时候，按照 \((10a+i)*b\) 和 \((10b+i)*a\) 决定很对。先写了个 Python，过了大样例。然后开始写高精。

\(8:10\sim 9:20\) 调高精，过了俩样例。

\(9:20\sim 9:50\) 造了一组样例，拿 C++ 和 Python 拍了一下，发现除了第一组都寄了，怀疑是多测没清空，开始调。

\(9:50\) 发现错了是因为我每组第二行输入了 \(10\) 个数字，Python input() 直接读了一行没影响，但是 C++ 的 read() 寄了。一看表，咋十点了，我直接慌了啊……

\(9:50\sim 10:30\) 看 B，先写了个 Tarjan，然后想了一会发现会 \(O(n^3\log n)\) 了，然后又想了一会发现会 \(O(n^2\log n)\)，然后感觉不对劲，一看数据范围 \(n=1000\)，然后看题发现题看假了，于是跳了。

\(10:30\sim 11:30\) 看了一眼 C 感觉是魔法题，于是开始看 D，感觉像是淀粉质，但是不会，写了暴力，然后发现这个暴力很蠢，发现这个链可以拆成两个链，然后发现每次向上合并一定要选子树内最小是最小的那个链，于是开始写 std::set，发现这样没法快速求 \(\text{Mex}\)，于是开始写值域线段树，写的挺顺，过了样例。

\(11:30\sim 12:00\) 回去看 B，发现之前看错题的做法也是假的，然后开始想这个题，发现不会。

\(12:00\sim 12:10\) 不会 B 暴力，写了 \(10\) 性质分。

赛后

期望得分：\(100+10+0+40=150\)；

实际得分：\(100+0+0+40=140\)。

B 因为宇宙射线没拿分。

然后吃饭的时候大佬说直接按 \(a,b\) 当前大小决策就行，然后我发现赛时为了避免高精乘高精超时把 \(b(10a+i) < a(10b+i)\) 改成了\(bi < ai\)，但是没把 \(i\) 约去（???），然后发现这样写过程中就不用高精了，写个高精乘就好了。

讲评

  • A: Skipped.
  • B 大概思路感觉和最开始看错的那个差不多（?），感觉还是又一些细节赛时没考虑到。
  • C 是状压，然后发现在后边添加操作不好维护，于是往前添加。我能不能说赛时最后几分钟没看见数据范围。
  • D 有一个每次选取最小点的贪心，然后发现改变的时候是删去一个点，然后就做完了。

总结

  • A 高精写的太唐了，NOIP 应该不会考高精吧……
  • 看题一定要先看明白在写啊啊，看错题浪费时间太长了……

  • 不是哥们你咋天天想写线段树呢 ???

NOIP 模拟赛 #23

题目链接（内） 题目链接（外）

对拍保平安！！

最后一场模拟赛。

赛时

\(7:40\sim 8:00\) 开始写缺省源，发现不能编译，发现是开栈空间开太大了。

\(8:00\sim 8:40\) 看了 A，感觉是对 \(ax-b\) 整除处理，然后还得考虑一下能买到，调了一会过了样例，然后和暴力拍了 \(20\) 组小数据没问题，先过了。

\(8:40\sim 9:20\) 先写了个 BFS，写一半被叫回去打扫卫生，写完了发现没过样例，手玩一下也是 NO，然后看了一下样例解释发现看题看假了，然后不会了。

\(9:20\sim 9:40\) 看了 C，好像做过，秒了。

\(9:40\sim 10:20\) 发现 B 每次转移交点就是求个当前最长一段空区间内，上（下）一行长度最大的一段空区间的长度，欸感觉很对啊，写了个 \(O(n^3)\) 的暴力，过了样例，然后感觉可以预处理很多东西，开始写，然后发现还需要处理一个【区间内最大连续子序列长度】，欸这个我会这不是线段树板子吗。然后想到昨天说：「不是哥们你咋天天想写线段树呢 ???」于是不敢写了，然后看了一眼数据范围，发现 \(n,m\le 1500\)，欸这不一眼给 \(O(n^2\log n)\) 的吗，爽了，开始写。

\(10:20\sim 11:00\) 写 B，然后出了若干弱智错误：

  • 建树的时候没让每个 SegTree 有一个 n 的变量，导致线段树每次调用的 n 都是全局的行数。
  • 输入格式有点反人类，改了半天发现忘了输入格式，回去看题发现最开始的一点问题没有。

\(11:00\sim 11:15\) 调过了，不是很想开 D，去写拍子了。先拍的 A，然后拍了一千组都挺对，但是因为 bf.cpp 的判无解是胡搞，感觉全对不太可能，然后去看 data.cpp 发现 mt19937 gen(1); 没有 time(0)，唐飞。改了之后拍了两千组，没啥问题，比较放心了。

\(11:15\sim 11:50\) 开始拍 B，然后发现 WA 了，看了看发现是数据错了。然后发现 WA 了，看了看发现是数据错了。数据修好了（导致很弱），然后在

上，bf.out是 YES，但是 sol.out 是 NO，然后手玩发现就是 YES，可能是因为线段树的某些优良性质对了，但是发现这显然是错的，改了。

\(11:50\sim 12:00\) 慌了，去写 D 的 \(O(m^n)\) 暴力，发现样例本地跑了四秒，不管了交了。

\(12:00\sim 12:10\) 发现还有十分钟，于是开始卡常，无果，GG。

赛后

期望得分：\(100+100+100+0=300\)，

期望得分：\(100+100+100+0=300\)。

然后发现 B 可以什么着预处理一下，然后 C 跑 \(1,s_1,s_2\) 的单源最短路直接就 \(O(n)\) 了，唐。

总结

  • 不是哥们你咋天天想写线段树呢 /KEL
  • 对拍，真的有用 QWQ