ICPC2019签到复盘
条评论南京站
做出来三道签到题可以稳$Cu$尾，分别为$A,H,K$；
其中，$A,H$考的是简单的数学推理，$K$题是计算几何板子。
第一次调计算几何还是有点难顶，什么点在线段上点在直线上等等绕的也是有一点点晕的，不过如果有板子而且能熟练对着敲其实做的还是很快的（吧）。
题目复盘
A Hard Problem
$AC$人数最多的一题，可以打表来做。但是如果打表打的不够多，可能会认为答案是素数个数+1（看到不少队都踩这个坑了我开心了$bushi$）。打表到$n=9$的时候，就能推翻前面那个结论了。
如果不打表去想的话，距离新加入的数$n$
代码如下：
1 |
|
Prince and Princess
也是一道结论题。
假设要确定最终的答案，则应该满足$a > b + c$（理论上问完所有人后，得到的确切消息，要比假的消息和不确定的消息多）。
然后考虑最小询问次数，应满足b + c == 0 ? 1 : min(a + b + c, 2 * (b + c) + 1)。取min是考虑到最坏情况，问了b+c个说假话或者不确定的人，此时只需要再问b+c+1个人，由于这些人都是说真话的，因此就可以确定最终答案。
记得，有一个特殊情况1 0 0，只有公主一个人，因此一次都不需要询问，直接把公主拉走就可以了。
代码如下：
1 |
|
Triangle
我的第一道计算几何题。
确定下来另一端结束点在哪条边上然后二分就可以了。
这题主要是熟悉模板就好，没有太多思考难度。
代码如下：
1 |
|
Digital Path
不难想到记忆化搜索。
设置状态为dp[当前x坐标][当前y坐标][当前长度]（一定以(x, y)结尾），就可以进行转移了。
然后考虑细节，不仅是路径的尾部不能够再拓展，头部也不能再拓展，所以在边界情况的时候要写两个check函数帮助我们判断现在这个边界是否代表一种合法解。
需要注意的是，大于4的长度不需要再多考虑，统一按照len=4即可，节省空间，这个处理思想比较重要（开头想着这样空间不够去想别的方程了，后面才想起来长度大于4特判掉就好了）。
代码如下：
1 |
|
徐州站
三道签到题，需要手快才能Cu，后面的题目几乎没啥思路。
感觉有点像打表场？
A题可以打表找规律，F题就是交个表上去，C题嘛，我本来想打表的后面发现没什么必要了…
题目复盘
Cat
一道很不错的思维题，主要考虑到对连续四个数有这个规律：__00 ^ __01 ^ __10 ^ __11 = 0
于是，就可以分成三部分来做，一部分是开头零散的猫，一部分是中间可以整块整块买的猫（异或后价格为0的），一部分是末尾零散的猫。
也就是说，只需要快速处理掉中间那部分，然后暴力枚举开头和结尾的猫就可以了。
开头怎么样才有零散的猫？
打表得，若左区间端点为偶数，则容易分成整块整块的猫（异或后价格为0）。也就是说，若左端点为奇数，只需要将这个端点作为零散的猫处理，再向右移一位作为新的左端点就好。
结尾怎么样才有零散的猫？
计算出整块整块的猫什么时候会停下来（剩下部分不再能组成异或值为0的块），此时就可以开始枚举。
如何枚举？
异或运算，若是两段相同则值为0。也就是说，我们可以把左右两边零散的猫都装到数组里面处理，数组含义为第$1$只零散的猫到第$i$只零散的猫这一段的异或值，这样就不需要枚举左右端点。然后，$O(n^2)$枚举即可。
代码如下：
1 |
|
<3 numbers
读题意，满足条件的数字其实就是素数和1的并集。
然后，题目是要求判断某个区间内的素数密度是否小于$\frac{1}{3}$。
本来试着用素数个数的估算法来做，发现效果非常不理想。
然后试着分块打表乱搞了一波，打完表之后再区间筛法，理论上是可以过的。
不过我TLE掉了，应该是那个表分的块数太少了，五十万一块或许可能大概能过吧…
代码如下：
1 |
|
然后考虑正解。实际上素数分布是会越来越稀疏的，何况素数密度本来就不是很大。因此我们可以考虑分类讨论。
保险一些，当$n \leq 10^4$的时候区间素数筛，其他情况直接返回$Yes$。
后面看了看网上的，好像我的范围太保险了…
代码如下：
1 |
|
The Answer to the Ultimate Question of Life, The Universe, and Everything.
开始的时候想着移项然后降低复杂度找正解。
后面发现，好像这就是个打表题吧…
这里有个要注意的地方，这题里面，如果要判断某个数开三次方后能不能被整除，不要搞个$pow(x,1/3)$，会出奇怪的BUG。只需要用$map$预处理一下就好了。
其他的就没太多要注意的了。
代码鸽鸽鸽了（关于我挂机打了个WA的表的悲伤的故事）
上海站
上海站理论上的签到好像很多？
换句话来说选手实力都好强看起来他们怎么什么都会做…
然后就是牛客的打印题目真的不友好，计蒜客那边按一下就好了，牛客这边老是缺一半，最后发现手机截图再打印最清晰。
题目复盘
Prefix Code
题面巨长，只有最后一段有点用。一道字典树板子题。然后可以用map快速搞定，不用写真的字典树。
就是判断给出的若干字符串是否存在字符串是其他字符串的前缀。
代码如下：
1 |
|
Cave Escape
刚拿到这题的时候，看了一下，每个点的权值都是大于0的，贪心可得每个点都要走过才能获得最大权值。起点和终点在哪里不重要。
立马口胡了个$DP$，然后看了一下好像只过了$30\%$的数据点。后面冷静想了一下，好像这个不满足最优子结构性质，也不能乱转移？
然后就借鉴了一下网络，发现这是一颗最大生成树。
由于需要建的边有点多，然后跑Kruskal可能会$TLE$掉，因此正解是利用权值并不大的特点，开辟了若干个桶进行桶排序。
这个桶的思想在很多题都能够见到，需要格外留意。上次的$gcd$统计（HDU5656）就是个很好的例子。
把问题转化为从权值去考虑也是很重要的，比如某场牛客枚举mex值的一个计数问题。
当然Kruskal是可以卡过去的。
代码如下：
1 |
|
Color Graph
如果能够发现这是个二分图的题目，那么这就是道很裸的签到题。
如果没能发现的话还是比较难做的。
前置知识如下：
然后发现$n$很小，直接进行二进制枚举即可。
代码如下：
1 |
|
银川站
第一次做到签到题是”HelloWorld”这种的…总感觉怪怪的…
然后队友帮忙敲了大数的Python代码，敲了个签到（取模比我分类讨论快多了），我敲了颗线段树，就欢快打出GG了。
大概是Cu尾巴。有点难顶。
题目复盘
Pot!!
队友和我说是道线段树，就套上了以前的线段树板子直接莽了一波（写得好丑）。
题目要求求出在经过若干次区间乘之后，区间内素数因子的幂次最大数。
只要观察到，初始时序列内数字都是$1$，以及每次区间相乘的数都在$[2,10]$内，这道题就很好做了。因为$[2,10]$的区间乘，只需要考虑$2,3,5,7$四个素数因子就可以了，而区间乘问题也转为了区间加问题，维护四颗线段树对应四个因子即可。
代码如下：
1 |
|
南昌站
疯狂演队友的一盘。
签到题符号写反$WA$了两发。
最大生成树使用的$Kruskal$，排序后标记【已使用的边】的方法失效了，又$WA$了两发。
我开$G$的时候，$C$题队友推了个奇妙的计数方法，然后迅速切换到$C$题去码，中间和队友沟通的不是很顺利，写炸了一次。沟通完成之后和暴力一对比，$OK$，交。
然后因为我忘了取模又演了队友，$WA$了两发。
现在已经炸到铁首了，必须要再开一题才有牌牌。
然后我接着写$G$，两个队友也暂时找不到能开的题，就一起来看。发现模数不是素数之后，搞了个set来维护最大值对应的最小盘子。
但是并不是很顺利，一直炸到结束都没能跳出来。
”是真的，铁牌已经寄到家了。“
题目复盘
And and Pair
队友想出来的一个奇妙计数方法。
由于目前他自己也忘了怎么想的。
决定以后要是读懂了就再补充这份题解。
代码如下：
1 |
|