下午才拿到的题，本以为考后半个小时就能拿到，结果裂开。

Day 1

开题看到三个传统题。前两题只有 /(10/) 个测试点，看样子很没区分度的样子（

看第一题，woc 手写编译器是什么离谱的模拟题。

仔细看一下大概是让你自己实现 define 语句。指令数和长度都很小，并且保证答案长度 /(/le 1000/)，这不直接模拟就行，大概是把每个标识符段和非标识符段抠出来，前者放到栈里，每次取栈顶看能否用 define 展开，后者直接输出即可。

然后看第二题，大概是树上路径计数，分别求合法路径数和合法路径权值和。/(n/) 很小 /(r/) 很大。

想了一下，感觉是枚举路径上的最小值然后统计，如果最小值为 /(x/)，相当于每个点的 /([l,r]/) 向 /([x,x+k]/) 取交然后统计答案。还要删去没有取到 /(x/) 的方案，也就是对于 /([x+1,x+k]/) 要再算一次。

那么问题就转化为没有差值限制的方案。直接跑树形 DP，/(f,g,u,v/) 分别表示经过点 /(x/) 的合法路径数，从 /(x/) 开始合法路径数，以及 /(u,v/) 表示对应合法路径权值和。

/(x/) 的范围会很大显然不能每个都算一遍，但是 /(n/) 很小，直接拉格朗日插值即可。每个 /([l,r]/) 最多拆出 /(5/) 个区间，大概是 /(5n^3/) 貌似可以过。

看了下才过一个小时，开始看 T3。题面令人大受震撼（怕不是某个 luogu 管理出的题目

很明显的图论特征，消息 /(x/) 向 /(y/) 连边，边权为 /(y/) 在 /(x/) 后面产生的贡献，那么我们要求的就是最长简单路径，直接状压就能过前两个点。

分析一下，等价于每个点只有一条入边一条出边，那么我们跑费用流，对于每个点，从源点连一条边再向汇点连边，然后再连 /(x/to y/) 的边，边权只有 /(1/2/) 两种可能。

接着回去肝前两题代码，第一题写了 /(50/) 分钟，字符串处理有点恶心，很担心数据里可能会有多余空格和行末空格，content 可能为空，也可能有空格，空格段的长度可能不为 /(1/)。

然后写 T2，虽然插值和 DP 代码不长，但是细节不少，写起来极度折磨，调完已经过去三个小时了。

然后开始写 T3，写到一半才意识到不对劲，这 tm 不是有负环的费用流吗，并且定义和负环流不一样，不能够走带负环的增广路。

然后就开始各种奇思妙想，后来发现再把每个点拆点 /(x/to x’/)，可以保证每个点只在路径中出现一次，虽然图会有负权环，但是这张图如果走了负权环就一定流不到汇点。然后再跑带负权环的费用流？好像是强制选所有负边权然后退流，想不太清楚，感觉要翻。

回去翻看下前两题代码。猛的意识到求前缀和多项式的次数要 /(+1/)，如果 /(f/) 是 /(n/) 次多项式，/(u/) 是 /(n + 1/) 次多项式，前缀和是 /(n+2/) 次，所以要插 /(n+3/) 个点，自己少插了一个点（以后写插值不管怎么先多插几个点肯定没事

大概还有 /(30/) 分钟，不大敢莽第 /(3/) 题，主要是只看过没写过带负权环的流，细节也没搞清楚。干脆写 /(8/) 分的状压算了。

写完还有一刻钟，看 T3 哪还能拿点分，很快昂，这性质 B 不是告诉你第一问答案。离大谱直接输出非学术消息总数有 /(20/) 分比状压分还多（笑哭

希望不会挂分。

Day2

开题发现题目都不长。

开 T1，发现值域很小，那么 /(n/) 必然没用，直接开桶。

要求方案使得每个质数都存在一个倍数，根据套路显然是容斥，考虑枚举哪些质数没有倍数，剩下的数产生 /(2^{cnt}/) 的贡献。

值域 /(2000/)，筛一下有 /(300/) 个质数，必不可能直接容斥，还是套路，我们容斥 /(/le /sqrt{2000}/) 的质数，剩下的质数两两之间互不干扰，可以线性递推过去，那么我们只用预处理 /(f_{S}/) 表示集合 /(S/) 里的质数的倍数集合的大小，再预处理 /(g_{S,x}/) 表示删去集合 /(S/) 里倍数后，/(x/) 的倍数有多少个。这部分预处理的复杂度是 /(14/times 2^{14}/times 305 + 2^{14}/times 2000 /ln/)。感觉卡不满，递推的复杂度就是 /(2^{/min/{c_i,14/}}/times /max/{0,c_i – 14/}/)。

感觉能卡过去，就去看 T2。非常令人智熄，居然又是一个括号变化，和 WC2022 怕不是同一个出题人（当为民除害）

必然先建树，操作 /(2/) 就是将一个点的儿子随意排列，且花费代价，操作 /(1/) 就是合并相邻两个儿子，再将右儿子的权值接到合并后的点下面。

合并的总数必然不变，所以必然是从上往下合并，这样层的决策集更大，决策不劣。感觉想到这里不难，难道今年题目比较简单？

貌似有个 /(x=0,y=1/) 的部分分，手算一下就是每层把最大值留下，其余下放，直接用堆模拟一下即可。

感觉有戏，模拟一下 /(x=1,y=0/) 就是把最小值留下，其它下放。然后是 /(x=y=1/)，大概是每次用最小值做 /(A/)，其余做 /(B/)，但是最后会把最小值留下来肯定亏了。但是可以交换顺序，所以最后一次下放交换最小值和最大值的位置，那么就能把最大值留下，代价不变。

感觉挺对的，就去看 T3。树上问题，按顺序删边，答案最优，/(N^2/) 算法，woc 树上的数既视感，这怕不是和树上的数一个出题人（当为民除害）

再一看毒瘤出题人就给了一个小样例，太离谱了。不过直接枚举全排列不难写可以直接对拍。

非常没有思路，就先回去写 T1，没给大样例，自己造几个，大概 0.4s 不慌。

然后写 T2，特别好写代码就 20 行，并且一次过了 3 个样例，让人大受震撼。

然后想 T3，一点思路都没有非常折磨，愣是瞪了一个小时。

后来偶然翻到这题的空间限制是 /(2G/)，woc 这怕不是 NOI 史上空间最大的题。那 T3 比要开大数组，大概是 /(kN^2/) 的空间？那必然是 DP 跑不掉了，看来前面想那么久的贪心可能性不大。

又推了半个小时得到一个 /(N^3/) 算法，大概是 /(f[x][y][z]/) 表示已 /(x/) 为根的子树，删除 /(x/) 的父边，边的两端分别是 /(y,z/)。由于每个点的度数 /(/le 3/)，讨论 /(6/) 种可能的先后顺序就行。

看下时间还有 90 分钟，还是回去测 T1，T2。

造了几个能卡满的大数据发现居然要跑 /(1.8s/)，没想到居然还是个毒瘤卡常题。然后就开始了及其折磨的卡常环节，现实优化取模，循环展开的常用技巧，大概卡到 /(1.1s/)，一直卡不进一秒，并且本地配置大于 CCF 机子，那岂不是当场暴毙。

后来把数组顺序换了一下，/(g_{S,x}/) 变成 /(g_{x,S}/) 居然快了接近一倍，只用 /(0.6s/) 就能跑完，震撼我一整年。

然后看 T2，突然发现贪心有致命漏洞。/(x = 1, y=0/) 的时候保留最小值不一定是最优的，因为如果后面某层突然加了很多括号，并且权值很大，那么可能保留次大值，然后把最小值传下去。

太折磨了，最折磨的事莫过于最后 /(30/) 分钟发现自己思路错了，就跟进了教室发现没带书包，到了火车站发现没带身份证一样（

没办法，临时写暴搜，每次搜是传最小值还是次小值，大概是 /(2^n/log/) 复杂度，实际跑不满，然后就实在没时间了，希望 /(x=y=1/) 或 /(x=0,y=1/) 的贪心不挂。

这次模拟还是能发现了一些问题的，比如有些基础确实是不过关，拉差写起来和挤牙膏一样写了两个小时，还不算调的时间。过于自信没有严谨的推导和验证思路的问题，导致出现结束前半小时发现思路挂了的问题。

真的省选还没开始，希望这次模拟能有启发和警醒的意义。

Updata：根据各个 OJ 的民间数据没有挂分 /(100+100+28+100+48+44/) ，希望 D2T2 能多点 /(x=y=1/) 的数据这样又可以骗几个点（