前几次: NOIP2022游寄 CSP-S 2023 复赛

开考

早上起来睡得不错，不怎么困 8:00 多到考场，在七宝中学，他们在修路 进考场以后就是调机器等密码，拿到密码后开始干题目

T1 一眼大水题，半小时之后完成，过了大样例

T2 先写了一个暴力，然后开始考虑正解。发现经过所有的操作之后每个变量要么等于一个常量，要么和另外一个变量相等，要么和另外一个变量的逆相等，有点像 2-SAT。忘记 2-SAT 是用并查集做的了，于是给每个变量一个点，每个变量逆一个点，每个常量一个点，如果有 $A=B$ 就建一条 $A$ 到 $B$ 的单向边，然后 $\neg x$ 到 $x$ 也有边。发现这是个基环森林，外加每个常量是没有出边的。于是如果 $x$ 能走到 $\neg x$，那么这个分量就必须全是 $U$ 了，再加上直接是常量 $U$ 的就是答案。开心地写好一个程序，第2个样例就假了，于是就开始疯狂修改（碰到地情况包括但不限于输出错误答案，程序卡住等。中途手画了不少图，不过还是有缓慢的进展的。卡在某个样例上（具体哪个忘了，经过大量研究后发现 $x$ 能走到 $\neg x$ 这个条件不对，因为可能中间反转了奇数次，所以一致性还是能满足的。目前为止知道了如果 $x$ 能走到 $\neg x$，则 $x$ 必定在某个环上，以及找出分量遍历环的时候也需要记录走形如 $\neg x$ 到 $x$ 的边的数量。经过2小时的苦干后，过了所有样例。（后来知道了并查集做多简单

T3 一眼不会做，T4 看最后时间不多了，且暴力感觉不好写，就直接输出了一个样例。

后记

看其他人游记，开始担心自己做的 T1 T2 是不是有问题，感觉这次又要寄了

后来出成绩了，100+100+0+0=200，还算不错，算是一个好结局吧。

总结

T2 调代码时间用得太多了，T4 其实也不是很难，如果多花点时间，应该还是能干不少分的。

Tags: