[整理]CSP-S2019第一轮试题解析

答案什么的自己上网搜吧……
一些没啥意义的（如常识题、简单计算题）就略过不讲了。

单选

8.注意是非连通，所以在完全图的基础上加一个游离的点。
9.与普及组的区别只有整除3。注意到中间的三种选择正好构成模3的完全剩余系，于是第三位可1根据前两位确定。答案：\(5\times 5\times 1\times 1\times 1\)。
11.想一下归并排序的代码就好了。
14.486除以2之后是\(243=3^5\)。

阅读

1.找每个数后第一个大于这个数的数。简单模拟略。
2.简单的并查集操作。
4)一个\(cnt\)可以合并很多次。
5)既然\(x\ne y\)，那我们可以一个一个点加进去，最终\(ans=\prod_{i=1}^{4}91\times i=1225\)。
6)这个并查集没写路径压缩！！！不是\(n\log n\)是\(n^2\)！！！
3.前后夹击求出至多删去几个连续元素使得\(t\)是\(s\)的子序列。
5)\(t\)不是\(s\)的子序列，但是至少要输入一个字符。
6)\(10+2=12\)。

完形

1.爆搜。顺便吐槽出题人的英语
1)2)都是题目中学习技能的条件。
3)学完了有收获。
4)当前点删掉后儿子的入度当然要-1。
5)有\(m\)个前置技能。
2.奇妙的恶心的状压。
设\(f[i]\)为\(i\)个石子时先手是否为必胜态。则可列出方程（其中\(\oplus\)为按位或）：\(f[i]=\bigoplus_{i\ge a[j]} !f[i-b[j]]\)。
由于\(b[i]\)不超过64，所以把\(f\)数组压进一个ull里。（以下车速加快，请坐稳扶好。）
1)一开始有0个石子时先手是必败态，初始化为~0ull。
2)排序之后可用规则只增加不减少，所以只要a[j]==i就可以加进转移。
3)添加进转移，状态压缩基本操作。
4)按照方程转移。
5)将当前状态加入status，相当于把数组整个左移。

总结

这套题难度严重不均：
选择：★☆☆☆☆（原题太多了）
阅读：★★★☆☆（有一些坑点）
完形：★★★★☆（状压太毒瘤）
\(\Huge{完结撒花}\)