20230220小比赛の反思、总结与升华（发牢骚）

痛定思痛，复前行

T1：一道思维构造题

题目大意：

框架扫雷，构造一种地图不超过25*25的扫雷局面，使地图上所有数字和为s

正解：

找规律
将他们化为8个每组
再用“边角料”处理划完组后的的余数

得分：

95pts，在细节处理上欠考虑了

评：

需更加认真，得分勉强能看

experience，通用の小技巧：

1.对于验证较简单，范围较小的构造性spj题目，完全可以自编spj代码测试每一个数据范围内的点保证正确。
2.对于构造题的较简通法：（代码量比正解大，所以才叫较简，所以才能是通法

1. 首先考虑将最大限制全部用尽，用不尽适当缩水
2. 将构造出来的最大限制均匀拆分成一块一块一块，尽量往小分，当然需保证拆分后的每一块不会互相影响
3. 让每一个拆分后的块贪心的领权值
4. 权值领完后把后面的贡献置为0即可

T2：一道数论背景的思维题，又叫根号分治

大意：

质因数分解n(1<=1e18)
求n分解后的每个质因数的指数取最小值

正解：

筛出1e5-的所有质数，每个n对这些质数处理后，再特判答案为2,3的情况（一个平方数/立方数）
infact,只比暴力多了平方和立方的判断，但是时空复杂度骤降，优秀的想法

得分：0pts

做法：线性筛到sqrt(maxn)，然后暴力，原因：MLE!!!!!!!

如果我当时不贪那根本贪不到一点分的空间，就能拿中规中矩的60pts了，再靠前面95的一点优势……

这是后话，又叫梦话

考试的时候两眼一飘，1个G的空间！我当场表演1e9的bool数组！万一老师小手一滑…线性筛就过了，超时只会扣超时的点，只要不MLE就万事大吉（

（考完才发现那是C题的空间
（事实上考试的时候后来也发现了1GB是C题，但是我也不知道当时在想啥，大抵是自我劝说：bool比int小多了，好一阵自以为是，坚信这就是正解肯定会因为标程改空间的（当然了下次每次写完一道题都要算空间），考场上的自己总是捉摸不透呢，鬼知道我在想啥。
然后嘛……那送白的60pts就无了。无了。无了。
MLE毕竟一分都不给。

experience，通用技巧、教训：

1.真的食雪的教训。一定要好好的审题，同时要注意算空间，如果想不到正解，非正解方法能拿多少就拿多少。
2.方法get：根号分治
3.复习一下算空间：

1MB=1024KB,1KB=1024B
char/bool:1B
int/float:4B
double/longlong:8B

T3：一道优雅的dp

题目大意：

把正方体摆成酱紫

（就NKOJ那张图（
然后沿着格点从A走到B，求最短路径数量

正解：

dp[i][j]表示走到i行j列的点有多少数量，滚动层数
然后狂推，一圈一圈向内”L”收缩，单独讨论外部/底面

得分：跳了

原因：实现总是有各种各样的细节等着你调，实现有一定难度，这道题调了我一个下午+半个晚上，主要还是代码力和大脑不太同步了，考场上想了好一阵子不知道该从哪里开始写就只能含着满头问号跳了

experience

1.在考场上实际开题时误以为C是一道“简单的”搜索题，便选择从C开始，然后由于代码实现有一定难度，在0.25h~0.75h这三十分钟就被砸进了无底洞，下次通读后一定要选择思路最明晰，至少方向能保证正确的题目开始，不然是对精神上和时间上的双重打击。

T4：思维+码力题

题目大意略

正解：

O(n)推公式得出初始答案，然后对于每一个障碍物进行讨论：
1.只被他自己阻挡的
2.因为它和它的上几层一起才被阻挡的（维护单调性）
每一条被阻挡的线都需要+2次，对于每次枚举使用乘法原理

心路历程：

停留在了推公式的那一步，也就是连k==0的分都拿不到。
当时已经想出来那两种分类了与“每次+2”了，但是没能推出k==0的情况，自然后面的也都是瞎想。

experience：

这道题，本来爆搜是可以拿30pts的，但是由于没把k==0推出来；且做到D时，时间已经非常紧张，就放弃了暴力。归根结底还是C的错误开题（也许开在D就改写结局了（不是

大总结：

C投入了太多的时间，思路不对还是首开题应该马上跳的，B的不算空间不审题，下次考试一定一定一定要care。