联合省选2022Day1游记

· · 个人记录

菜死了菜死了，没可能进队的。

希望 \text{T}_1 不要炸>_<

8:30

开 \text{T}_1，哟，是道造编译器题。 理解好题意后直接模拟即可，标识符查找可以直接用 map，也可以用 \text{AC} 自动机。

我用的是 \text{AC} 自动机，每插入一个标识符字符串就重新建一次。

考虑到字典树的大小是 O(n^2) 的，define 指令的总时间复杂度为 O(n^3)，可以过。

undef 时不需要重建，用 bool 数组特判一下就行。

因为题目保证了输出不超过 1000 个字符，所以直接 dfs 展开的复杂度没问题，当然把 dfs 改成记忆化搜索常数更小。

**10:10** 敲完代码，开始查错。 **10:20** 过了 $\text{T}_1$ 的所有样例，$\text{T}_1$ 不好造数据，就不打算写对拍了。 开 $\text{T}_2$，这是一道计数题。 考试中只想出了前 $40pts$，但因为种种原因最后只打了 $20pts$ 的暴力，这里记录一下我 $40pts$ 的做法。 题目中有两问，但第二问的做法跟第一问的作法大同小异，下面只记录第一问的做法。 首先 $O(n^2)$ 枚举树上的每一条链，然后计算这条链上的答案。 于是问题转化为给定一个长度为 $n$ 的序列，在序列上填上若干值，第 $i$ 个位置有值域限制 $[l_i,r_i]$，求满足极差 $\le K$ 的合法序列有多少种。 最暴力的做法就是直接枚举序列的最小值 $a$，然后限制每个位置上填的数值域满足 $[\max(l_i,a),\min(r_i,a+K)]$。 于是答案就是 $$ \sum_{a=0}^{limit}\prod_{i=1}^n (\min(r_i,a+K)-\max(l_i,a)+1) $$ 但这样稍微有一点点问题，因为无法保证序列中有某个位置上为 $a$，还需要容斥一下，真正的答案是 $$ \sum_{a=0}^{limit}\prod_{i=1}^n (\min(r_i,a+K)-\max(l_i,a)+1)-\sum_{a=0}^{limit}\prod_{i=1}^n (\min(r_i,a+K)-\max(l_i,a+1)+1) $$ 直接计算这个式子需要 $O(nK)$，总时间复杂度就是 $O(n^3K)$，这个暴力很容易写，可以拿到 $20pts$。 考场中想到这里时才 **10:40**。 上面这个做法复杂度的瓶颈在于枚举 $a$，当 $K$ 的规模达到 $10^9$ 时就失败了。 以计算 $$ \sum_{a=0}^{limit}\prod_{i=1}^n (\min(r_i,a+K)-\max(l_i,a)+1) $$ 为例。 考虑到式子中的 $\min(r_i,a+K)-\max(l_i,a)+1$ 是一个关于 $a$ 的分段一次函数，非负段至多 $3$ 段。 所以 $$ \prod_{i=1}^n(\min(r_i,a+K)-\max(l_i,a)+1) $$ 是一个关于 $a$ 不超过 $n$ 次方的多项式，记为 $\displaystyle P(a)=\sum_{j=0}^{n}p_ja^j$。 于是题目等价于计算 $$ \sum_{a=0}^{limit}P(a) $$ 总共不超过 $3n$ 段，每一段的 $P(a)$ 都不同。 直接用暴力的多项式乘法计算对每一段计算 $P(a)$，每段花 $O(n^2)$。 在同一段中 $P(a)$ 是不变的，用拉格朗日插值求自然数幂和可以 $O(n^2)$ 计算这一段的贡献。 所以计算完所有段贡献的时间复杂度为 $O(n^3)$。 总时间复杂度为 $O(n^2\cdot n^3)=O(n^5)$，可以拿 $40pts$。 **11:00** 这时候开始思考代码该怎么写。 我思考了拉格朗日插值怎么写，多项式乘法怎么封装，想如何以 $O(n^2)$ 计算 $n$ 个一次多项式的乘积，如何枚举段。 （现在发现自己石乐志，既然我都拉插了，干嘛还要知道具体的多项式是什么） 这是回答第一问的，还需要思考怎么把第一问做法改成第二问做法。 然后重新确认了一次时间复杂度为 $O(n^5)$。 **11:25** 我发现之前想代码细节时没思考如何求出 $\min(r_i,a+K)-\max(l_i,a)+1$ 关于 $a$ 的分段一次函数。 然后震惊的发现这里充满了复杂的细节。 以前遇到这种求分段一次函数的时，我用合并凸包的方法求，但是这样的代码细节也多，考场上我没法写出来。 想了好一会也没有想到好的实现方法。 **11:50** 这着实让我绝望了，近一个小时的细节思考全作废了。 放弃 $O(n^5)$ 的做法，去敲 $O(n^3K)$ 的暴力。 **12:10** 调完了 $\text{T}_2$ 的暴力代码，过了 $3$ 个样例。 开 $\text{T}_3$，点开题面后想骂出题人，题面巨长。 花了 $10$ 分钟读完题目，思考了一会决定放弃，剩下不到一个小时肯定写不完 $\text{T}_3$。 **12:30** 今天省选后面两道题都谅透了，必须得保证 $\text{T1}$ 不出问题，决定回去检查 $\text{T}_1$。 重新静态排错一遍后手动构造了几个小数据。 ```define``` 指令内容 ```<content>``` 为空的情况下没有错误。 输入的代码出现空行的情况特判了，没错误。 多构造了几个反复展开和递归展开的数据，没发现错误。 **12:50** 检查文件输入输出，等待考试结束。