DAY 10

得去看一看强者是怎么分配时间的。

35min 7:30~8:05

A B C D 读题初思考，还是没有把暴力想清楚，前面读题的时候就应该想好暴力。

57min 8:05~9:02

A 写完暴力，对拍，感觉比较顺利。

25min 9:04~9:29

B 写完暴力，只能说入门题确实是卡人的。

1H42min 9:29~11:11

B 写正解，数学不好是这样的写的特别慢，不过调错还是很快的，调完大样例通过。

使用 fc /? 看了下说明，对着英文看了半天，为什么我看的是英语呢？前情提要。

[Only Available on Full Edition]

总之有一个赛上 Trick :

'fc /w' 可以忽略额外的空格回车比对文件。

挂上 B 对拍，代码一帆风顺 (真)。

32min 11:11~11:43

执行了一次分析，显然应该先写 C 的暴力，因为：

1. C 的暴力更好写；

2. D 的暴力拿分潜力更大；

3. C 我一直没什么想法。

然而并没有想到状压，所以说硬搜复杂度惊人，又挂了 10 PTS。

专门检查了内存也没有问题。

直到最后

试着攻破 D 尽可能多拿分， 树形DP 当然是想到了的，不过这状态我这辈子都想不出来的。
最后也只写了朴素的暴力，遗憾了。

11.26 NOIP Day8 检讨

这一次感觉时间分配有问题。首先是在 T1 花了过多的时间，居然花了 1h 30min，然后当时写的还很错，随便一个随机数据就能把我卡 T 了。（然后没想到的是最后居然过了）。

然后 T2 瞬间就写完了，但是出了一些细节问题。所以最后出现了神秘奇观，前面的点 WA 了，然后后面的点全都过了。但凡开一个子任务依赖我就直接趋势。也就是说细节上出现了一些神秘问题。当时我直接过了大样例，然后就没管了，因为我相信自己的代码，相信计数题的大样例强度，（然后没写对拍）。

然后去写 T3，想到了可以状压 dp，但是我觉得 $m \leq 6$ 非常的诡异，我觉得可以推出 $m$ 的每一种情况下的转移。然后对着表看了一万个小时没看出来。最终在 T3 给击败了。

在写 T3 的过程中看了一眼 T4，然后把 T4 的暴力写了，但是因为 T4 的暴力超时了，最后获得了 0 分的好成绩。

同时我在梭哈 T3 还是 T4 是选择了 T3。最后也因为这样的战略失误使得后面的题挂的一败涂地。或许去研究 T4 可能有更高的分。并且还有一个问题就是我这一次有点过于偏激了，想到状压 dp 后没写，去想了另一个更加神秘的东西。这也是一个失误的地方。

赛后查到了 T3 的神秘序列，叫做 $number\ of\ domino\ tilings\ of\ the\ m \times n\ grid (m \geq 0, n \geq 0)$

对于 $m$ 在 1 ~ 6 的数列规律如下:

1. $m = 1 : a_n = a_{n-2}$
2. $m = 2 : a_n = a_{n-1} + a_{n-2}$
3. $m = 3 : a_n = 4a_{n-2} - a_{n-4}$
4. $m = 4 : a_n = a_{n-1} + 5a_{n-2} + a_{n-3} - a_{n-4}$
5. $m = 5 : a_n = 15a_{n-2} - 32a_{n-4} + 15a_{n-6} - a_{n-8}$
6. $m = 6 : a_n = 40a_{n-2} - 416a_{n-4} + 1224a_{n-6} - 1224a_{n-8} + 416a_{n-10} - 40a_{n-12} + a_{n-14}$

检讨：T1不会，T2不会，T3不会，T4不会，T1 0分，T2 30分，T3 0分，T4 0分，一共0+0+30+0=30分，时间为2.5h+1h+30min+30min,T1名字叫GCD可达性，场上在想如何求dag的连通性，发现不会，由于图论不是很好，一直在想targan,甚至没写暴力，交了错解，以为可以得很都分，但是是0分,，给定 n 个点以及它们的权值 a1..an。如果 i<j 且 gcd(a[i],a[j])>1 ，那么从点 i 可以到达点 j。点 i 能到达自身； 现在给出 q个询问 (x, y)，需要判断从 a[x] 是否可以到达 a[y]。输出 q行。每行输出"Shi"或者"Fou"，代表询问的答案. 记录: f[i][p]=a[i],a[i]能走到的第一个 p 类元素的位置 回答询问 (x, y) 时，枚举 y 的所有质因子 pp ，检查是否满足: f[x][p]≤y 预处理 1000 内的质数（168个），以及每个 a[i]的质因子，递推 f[i][p] 时只在自己的质因子里枚举， 小于 1000 的数最多有 4 个不同质因子，复杂度是 O(n800+q4) ; T2题意是，有一个螺旋方阵，白浅要操作，第一列所有数字变成一个新数字，第二列所有数字变成一个新数字，以此类推。变成的新数字是之前数字的和。白浅请你输出每一列的和。输入格式是 输入包含两个数字 n,k 表示卷的宽度和数字个数。

输出格式是一行 n 个正整数，依次表示每列上的数字和。正解是将贡献分段，分成左边和右边的等差数列，中间上面和下面何为定值差分即可。T3不会，用 1 2和21 两种地砖（每种地砖都无限量供应）填充 m 行 n 列的网格，要求不重叠且铺满，计算l-r的和。由于 mm 很小，可以状压每一列的状态 (1表示要伸到后一列)，状态数为 642 ，列和列之间的转移 可以用矩阵快速幂进行优化。还要写高精度！。T4是给一棵 n 个点、带边权的树，刚开始每个点都是白色。现在需要在选择一些点染黑、使得如下限制得到满足:

对于每个点 u ，至少有一个黑点距离 u 不超过 d[u] 现在给出在每个点的约束 d[u] ，以及把每个点染黑的花费 c[u]，请你选择一些点染黑，使得每个点的约束得到满足，并且总花费最小。用属性dp,dpu,j表示表搞定 u子树、且 u 和 j 配对的最小花费

赛时历程：

今天是个清醒人 （昨晚睡了3天的量） ，但还不如不清醒，只拿了30分。赛前听说今天题很简单，于是死磕T1，而且写之前都没怎么想。1h时写完T1第一版，发现样例过不完，仔细看发现思路错了，有点红温，出去上了个厕所，还是舍不得第一版，于是开始加补丁，2h终于过完最小的样例，一测大样例，发现有1/5都是错的 （T=1000，错了200+） ，好在第五个就错了，且l到r区间长度只有10左右，很快调出，满心欢喜再测一遍 （差不多只多对了第五个） 。好在错的比较好找，又调了一下，也没花多久，再测一次只错1/10了 （还是有100+） ，这次不太好找错哪了，不过经过努力还是在100个左右找到了，依旧快速加上补丁，再测一次，一眼望去以为A了，放进fc，结果还有8个不死鸟 （这次不太好找错哪了，还专门又写了3份附属代码，找到具体错了哪） 。虽然没A，但好在依旧有l到r区间大小只有10左右的，依旧快速看出错哪 （这时候时间已经来到3h，代码长度120+） 。于是万恶的调代码开始了，这次的错就是我没想清楚就写埋下的最大的伏笔，一直调到4h，才写出了最后一版代码，但是，发现大样例T了，于是用编译面板在本地慢慢跑。好消息没超时多少，坏消息错到30+了 （代码总长来到160+） 。这时候，前方传来噩耗，小鸡儿已经交了，没办法，只能交倒数第二版，本来觉得只错8/1000，说不定运气好A了，结果 （万恶的多测导致0分） 。然后，10min急速写出T2暴力，得了整场比赛唯一的30分。

反思及改正：

1.死磕一道题，写不出来就红了。应该给每道题分配时间，时间到了就跳，不要感觉快调出来了 （这种感觉一般是错的） 。

2.写之前没有想清楚，应该想清楚再写（磨刀不误砍柴工）。

检讨

今天的策略还行

唯一的不足是$T3$的暴力写挂了，我好想忘记怎么挂的了，似乎是没删调试？

我似乎发现解决比赛上半场精神状态不好的办法了

先写暴力，管他$T1T2$，写了暴力再说

反正还要也要写对拍，先写暴力总没错

但还是要好好睡觉

11月26日检讨

赛上用时：2h + 1h + 0.75h + 0.75h

赛时得分：80 + 40 + 5 + 15

$T1$ ：直接被单杀，明明自己已经拿了 $80\%$ 的分数，但是仍然不甘心，继续死磕，于是折戟沉沙于 $T1$ 大魔王。

$T2$ ：（点击此处添加文本）明明一道很简单的题目，但是（我明明都已经想明白了解决方法）却没写出来，简直就是我的耻辱，赛后却发现最后一步是暴力填充最后不满的一圈，差点脑溢血当场气晕了。

$T3$ ：一道看上去非常难的问题，让我开始产生了畏难心理，加上想了一会没有思路就燃尽了，时间不够，快速跳题（又是没写状态压缩 $dp$ ）。

$T4$ ：没有详细思路，直接大法师了，时间不够，属于是自讨苦吃了。

总之，比赛还是有不少时间被浪费在 $T1$ 了，简直不知道写 $T1$ 和 $T2$ 的时候脑子在想什么。T2没切出来确实可惜，虽然是不难但是我脑子抽了，直接燃尽了。

11.26 检讨

T1

现在回想比赛时写T1简直是太笨了。其实晚上补完题发现，其实丝路并不难，但是代码男鞋。又由于比赛一开始写T1就奔着满分写，于是浪费2h什么都没写出来。狂泻2h的我很红温。丝路越来越模糊，目标越来越明确。然后美美那0分。以后再也不一开始就奔着满分写了。

T2

就是脑子太笨了。据hyx所言他写T4我在看T2，他把T2调对了，我还在看T2.单纯的我，一直认为有规律可言。发现了一些性质，但认为写起来太复杂了，就没写。但更优的写法（一圈，一圈的算），又想不到。无语了。。。。。。。。。

T3

T3写的更是笨，想着用dp，但不知道怎么状态转移。看着大如神牛的数据，简直是绝望至极。

T4

T4写了个最暴力的暴力，可是认为本来卡一卡时间可以过得，但是未能如愿，在加上没有更多的时间去写其他部分分，只有遗憾离场。

关于T1补题的经历

一开始，duck评奖的时候由于刚刚起床没睡醒，就没听。于是补题的时候只有一片文字检讨。苦思冥想之后写了一份7788的代码。但是那时候是正着写go数组的，写的就很复杂。在xhx发了题解之后大彻大悟，对代码进行了优化，最后，在cs的提醒下，知道了数组爆了的错误。最后终于是对了。

今天瓜分的优美检讨

T1 其实不是瓜分 就是太笨了想不出来 但是我现在也没有A

• 其实当时想了大概20~30min左右 没想出来 然后写了一个80pts的暴力 直接逃跑
• 然后写后面 写了好一会 T2没过大样例 烦 然后看了看 旁边刘xy什么进度 结果还在写T1
• 于是又回去看看T1 依然没有思路
• 就这样 很多次轮回 还是没想到。。。。。。

T2 爽挂70分 其实这个瓜分也是理所应当

• 我打模拟赛的时候想法就是分成2*n条链，然后差分和直接等差数列算
• 但是呢，看到那个特殊点 $k=n*n$ 时，我又想到了先把外面 $n*n$ 的方阵算完 再算里面的 最后暴力跑一圈
• 然后就融合了 前面那个那个码量大的缺点和后面那个难写的缺点
• 所以大概就是想法太多 夹杂起来了 写的代码就跟石山一样
• 以后决策： 要么先想好所有方案再写，要么就冲着那一个写到底

11.26 检讨

背景：

NOIP赛前3天竟然还把模拟赛打爆了QAQ。

赛时经历：

想了5min的T1以为是水题（没看见i必须小于等于j），写完才发现过不了样例，成功浪费30min。细下心来想，好像没什么思路（于是上了个厕所），果真灵光一闪过一些思路。但发现始终只能n^2写。于是在9:00写完，过不了大样例，于是又调了30min（特判时把a[x]=a[y]写成x=y了），看了一下后面三题，em………应该是xjh最喜欢的插头DP，果断先打T4暴力（想了5个档,后来发现看出了一个树形DP（但没写），看出了一个线性DP（但没细想），想爆了一个点，没想出菊花图的情况（想到了贪心的分类讨论，但太懒不想写，没错就是懒得写），写了个指数级的暴力过了（不过就说不过去了））。还有约1h，开T2暴力，竟然还被卡了，写完了不知是大脑被外星人拐走还是把脑子忘一遍了，直接过了第二个样例就走了，直接只算一个完全环！！！然后就以为写完了——走了！！！赛后发现WA on 1。T3没想出暴力就想打表但不会。

总结：

• 写题带点脑子！
• 注意下标与数组的值的区别！

DAY8 检讨

分数；80 + 40 + 0 + 15

评价：如果写出了 T2 就还好，但是没写出来就比较垃。

赛时：T1 开始以为很简单直接判断两个数gcd>0或者中间有没有0等一系列分类讨论，直接写了。写了30分钟测大样例不过。才发现自己忽略了情况。然后思考了半天，改了一些，还是不对。发现又忽略了情况。好像自己完成100的档，就只能写了80的n^2建边。说实话这题应该在第一次发现它不简单之后就先写个暴力。T2 计数题一眼挺麻烦的，先写暴力。结果暴力好像还不会写，最开始用 for 循环给自己绕晕了。然后用while记录方向才把暴力$艰难$写完。T3 我赌定这是我不会的 dp，暴力分太少了就跳了。 开 T4，这暴力简答和部分分还多，然后就写。写完时间还有一个小时搓T2,20分钟写出k^2档，然后在减最后一层的时候一直调，没调出来。

总结：比赛还是有不少垃圾时间被浪费了，大脑空闲时可以花点时间规划接下来要写哪些题。T2没切出来确实可惜，主要是它不难但是我把它写成了大模拟。 计数题可以多输出一些调错。

DAY8 检讨

比赛感受：

感觉题目很难，但是老师说不难，实际上好像确实不难。但是，在讲完题目后还是觉得没太听懂。今天比赛感觉写了跟没写一样，就是“如写”。

检讨与反思：

第一题: 比赛时第一个看这道题，想了二十分钟，写了个代码，测样例时发现有问题。然后回去又看了下题，发现少看了个条件--“能到达”，所以可以知道他是个DAG图。然后我又想了30分钟左右，发现想不出来，于是就跳了这道题，最后20分钟左右回来写了个最暴力的暴力DFS连O(n^2)的时间复杂度都过不了，所以就用了原来的代码。但是，原来的代码没开freopen，所以挂零了，虽然本来就过不了。

第二题： 这道题是我在写第三题期间来写的，只微微的看了下题面和数据没有多去思考如何写正解，就写了个O（n^2）的暴力就没看这道题了。

第三题： 在写完第一题后，我就过来写这道第三题了，开始看到这道题的题面后，就想到了DP和推递推式子。然后就一直在推这道题的式子。推了一个半小时左右，之推出了m==2的时候的式子，其他的式子还在想如何去重（已经想出是那些东西加过来的）。然后就红温了。就感觉十分的暴躁，导致了freopen的没开。

第四题: 这道题是再写第三题的时候来看的，当时在写第三题时突然想到第四题暴力还没打，然后就过来看了下题面和数据。然后想到了暴力和特殊数据的做法，但是看到题面后发现其他要求，就不知道怎么维护暴力算法。然后就跳过了这道题。

关于freopen: 这个问题是出现在第一题上，当时只剩20分钟左右，我就想着写一份暴力代码，但是因为太暴力了所以就没用，但是我只开了暴力的freopen，没开我原来代码的freopen。所以挂了。虽然我在交题后发现了这个问题，（但是我发现的太晚了，已经开始测了）。所以就挂了。

为什么会有这总情况？ 按照老师的说法，我的性格太浮躁、太急了，所以在遇到特别难的比赛时，我会很急，有很大概率会不注意细节，这次发现这个问题后，我会努力去修改这个习惯。让我以后不发生这种情况。

总结

这次问题出在没开freopen，对于知识点的不熟悉，以及性格的问题。日后要尽量去改正。

关于NOIP模拟赛D8T1少拿1档分惨案的检讨。

考场上想了非常久，但是没有好思路，感觉DAG不能直接bitset维护，会炸空间，应该和值域以及gcd的性质有关，不过还是没啥想法，最后只能交开局写的暴力。

关于NOIP模拟赛D8T4少拿1档分惨案的检讨。

这场比赛由于第一题酶切出来比较红温，时间分配上略出问题。

第一个问题是比赛开始时没有写完四道题的暴力，基本上就是想了T1去写T2，写了T2之后又回去想T1，最后发现T3状压DP+矩阵快速幂非常可写，然后写了T4暴力输出样例没问题就走了，全然未察觉T4暴力时间复杂度在乘上T后就爆炸了，导致T4没有分。

之后遇到这种情况得算一下，并且写一些尽可能优化后的代码。