[已修改]

DAY 6 ~ DAY 7

摆烂的周末！几乎什么正事都没干除了玩。
而且周日由于不务正业晚上睡的也晚 (埋下伏笔) 。

DAY 8

最妙趣横生的一集。

44min 7:30~8:14

A B C D 读题初思考，明显慢了，而且感觉没想出来什么， 毕竟昨晚睡的太晚了 zzz...。

26min 8:14~8:40

先开 B ，然而写了半天发现自己复杂度出问题了，$70PTS \rightarrow 30PTS$ ，无奈回到 A 。

1H50min 8:40~10:30

A 想了半天好不容易写完，和暴力对拍了半天，修了一堆 虫子 ，对拍一帆风顺 (真)。

难以置信的是，此时此刻 B 居然没把优化实现 (没错我写到这的时候都绷不住了) ，直接前往 C 。

37min 10:30~11:07

C 虽然说早早发现有十秒的惊人时限但并没有什么思路，写完暴力去 D 。

20min 11:07~11:27

B 终于有 $70PTS$ 了，(感冻，开始吟唱)

希望のはな　繋いだ絆を~

(打断) 然而首先我没有意识到那个愚蠢的 vector 完全可以用数组代替，然后我也搞忘了今天的空间只有 128MB ，虽然说就多了 6MB 但是它还是炸掉了。

...今僕らの胸の中にあるから...

事实上 DAY 4 写 P1053 的时候我就被卡过，然而我并没有引以为戒少用 vector 。

对拍完感觉自己太棒了，而且想了半天各种乱七八糟的 Trick 也没有出路，没有具体题目具体分析想过模数的问题，遗憾了。

直到最后

D 垂死挣扎暴力，很遗憾没改对。

11.24 NOIP Day6 检讨

这场比赛总体打下来感觉偏简单，T1 略难，T2 偏简单，T3 有点板（就是卡空间的常数），T4 感觉有点难，不会写。

关于挂分情况：T3 因为出题人卡常直接挂成 $0$ 分（所以是出题人的错）。T4 敲了 50 分的暴力，但是因为有一个地方取模不太对，然后就安详的似了。

时间分配上较为合理，T1 正解 + 对拍 写了大概 1h，T2 秒了 70pts 的暴力，然后没看出什么性质，大概看了 40 mins 就跳到 T3，然后 T3 一眼秒，T4 状压写完了，最后空余了几十分钟把 T2 std 写了，然后一直想 T4。

挂分主要出现在 T3 上，因为没想到 vector 有超大常数，最后安详的 100 -> 0。

其次这一次 T4 有没有检查取模有没有去干净，该开 long long 的地方有没有开，最后造成了总计挂 140 pts 的惨案。

赛时历程：

今天的精神状态不太好，有时候写题写一半就疲倦了，然后就思路丢失，写一半写不出来了。T1先写了一个最大值，然后就疲倦了，导致思路丢失写不出来最小值了。后面想回忆一下，结果越回忆越疲倦，进入无效思考时间。于是就放弃了，最后输出都不够，爆0了。然后去上了个厕所，清醒一下，就开始写T2，T2开始都写得好好的，预处理都写完了，只差计算输出，结果又疲倦了，导致思路丢失又爆0了。T3、T4没时间写了，随便写了个“不可以总司令”，最后全都爆0了。感觉整场比赛都有点疲倦，真正有效的写题时间就1h左右。

题目过失：

T1：只解决了最大值，没有将思路记录下来，后来疲倦了，导致思路丢失，写不出最小值，最后爆0了。

T2：先进行预处理，处理完，又疲倦了，导致思路丢失，输出那一点忘了，最后爆0了。

T3，T4：前面无效思考太多，浪费了时间，只能写个“不可以总司令”，最后一分没拿，全部爆0了。

经验总结：

1.比赛时遇到像T1这种题目要求输出两个答案的题，宁愿写个暴力，也不要写一个问题的正解，另一个不写。写个暴力至少能拿部分分，解决一个问题，另一个不写可没有部分分。

2.比赛时有了思路可以先将思路记录在一个地方，这样可以防止遗忘，避免因遗忘思路而重新想，浪费时间的情况。

3.赛事状态不佳应及时调整，如上厕所，喝水等。而不是继续傻坐着，进行无效思考。

4.晚上早一点睡觉，保持良好的精神状态，防止赛事出现精神萎靡的情况。

5.如果已经有了过失，时间不够了，应该适当取舍，比如用看T4题面的时间来写T3暴力，而不是看完T3、T4然后没时间，写两个“不可以总司令”，最后爆完。

罪魁祸首——>放小长假。导致：体力⬇，精神⬇，反应⬇，思维⬇，而且放多了还会变成美妆博主，早点睡觉才是正确的√

11月24日的检讨

赛时分配：1h + 1.5h + 1h + 1h 得分：100 + 40 + 40 + 50

得分评估：没有挂分，写的分都拿到了

赛时思路

$T1$ ：比较快速就想到了 $0、1$ 和奇偶之间的关系，大概花了 $40min$ 就写出了正解，但是读题 + 对拍花了将近 $20min$ ，所以总体上就花了一个小时。

$T2$ ：想到了预处理，但是没想到递推关系的预处理时间复杂度会爆炸，加上没有分析出题目的特殊性质，所以燃尽了，只能写一个暴力。

$T3$ ：这道题则更是重量级，容斥的思路明明非常好想，但是就是没想出来，数据结构维护查询也对二维无计可施，于是又是 $O(nq)$ 的时间复杂度的暴力。

$T4$ ： 暴力 $dfs$ 正确性显然，但是 $n \le 40$ 还是成功让我以为是折半搜索，但是奇偶性的关系并未让我想到扩展域并查集，再加上时间并不充裕，所以写了暴力去想前面的题了。

（为什么 $T1$ 正解加上其他几题暴力就是 $rk3$ 了，本以为今天会掉 $rk$ 呢...）

今天的题让我想起了前两天看到的一句话：“ $3$ 是一个神奇的数字，很多问题在对 $3$ 取余的意义下会具有神奇的特性”，果然有其的道理。

真是一个令人悲伤的故事

T1

• 被3整除这个条件令人恶心，没想到在二进制的条件下有什么作用
• 考虑到这个题有个这么庞大的数字（2 ^ 200000）,所以肯定不希望我们算出来，而是寻找某种规律
• 先写了一份爆搜的暴力，开始打表
• 发现对于特殊奇偶性的 $n$ 和 $m$ 输出来的答案很有规律性（梦开始的地方）。
• 根据打表的规律，写了份分讨。对拍了整个赛程都没出错。完结撒花！！！

事实并非如此

• 无解的情况需要输出 2 个 -1，而我的正解和暴力都只输出了一个。
• 输样例时也是手动复制，肉眼看对不对，根本没注意

深刻检讨

• 以后测试样例一定使用文件输入输出并使用 $fc$ （今天这个坏习惯似乎也送葬了另一位朋友的 $20pts$）

T2

• $1e9$ 非常的吓人，但是 $1e6$ 有 $nln$ 的做法，先写一份
• 想测试下代码在极限数据（$1e6$）的输出，发现输出0
• 梦开始的地方：模数很小，导致阶乘计算很有操作空间
• 梦破碎的地方：第一觉得应该不会个数大到有 $5e4$ （实际上怎么会不可能）。第二也没足够的时间来打表验证了。

T3

• 先是写了个 $qn$ 有点不甘心 $20pts$，想下优化
• 考虑三维数点
• 不会，失败
• 注意到限制条件非常的特殊，很有操作空间
• 梦开始的地方：把条件分成三类就可以分别计数
• 梦破碎的地方：不能把三个因素完全分开计算，而是根据对应的关系考虑容斥

T4

• 奇偶性相关，数据很小
• 考虑二进制枚举
• 没想到把区间的限制转化为前缀和中 2 个点的关系
• 全剧终

严重瓜分

今天的挂分都非常低脂

心路历程：

• 先看T1，以为是一个极难的dp+输出方案，然后写了一个$O(n^2)$的dp（下方有后续），果断逃离☹
• 然后到T2，一看题就有一个$O(n\log{n})$的调和级数求因子个数再暴力求答案做法，然后……（下方有后续）
• 接着写T3，冥思苦想半天没想出来有什么优化的方法（死活没想到容斥），写了一个$O(qn)$，爽跑……
• T4，想到可以对每个数先枚举奇偶性，然后check，再根据$[x_{i},y_{i}]$来计算方案数和找字典序最小的方案，鼠鼠偷吃50pts。
• （诧异的）我T3怎么会一点优化都想不到？ 于是后来花了大约40~60min 写了一个 分块+动态开点树状数组的东西 $O(n\sqrt n \log^2{n})$ 乍一看以为跑的飞快 但其实常数多多+本来复杂度也不好，导致比$O(qn)$跑的还慢（简直是偷鸡不成蚀把米）
• 这时候想起来T1了，想着他不应该那么难啊，就果断想到了一个枚举在在奇数位和偶数位的1的数量，然后贪心往前放和往后放的做法，想到这个感觉很对啊，就开开心心的写，结果（下方有彩蛋）。
• 比赛结束，自我感觉良好。

关于T1挂完

开局写一个困难dp的郁闷

开局就写一个特别困难的dp+维护方案，调了十万八千年（40min）调过样例，以为对完了，直到打完比赛之后，开始检查这份代码错误的时候，才发现样例其实都没过

样例： 1110101000 1000101011

我的： 1111010000 1000010111

简直也是人老了眼睛不太行了。

最后十分钟调出题的喜悦

最后十分钟，终于把T1正解写出，调过了样例，此时十分高兴，结果没有发现一件特别日龙的事情，如下

    for(int i=0;i<=n;i++){
        if((i*2+(n-i))%3==3-sum){
            if(minn>abs(i-n)/*就是这里写错了 应为abs(i-(n-i))*/&& i<=(n+m)/2 && n-i<=(n+m+1)/2){
                minn=abs(i-(n-i));/*下面居然在前面调过样例的时候改过了*/
                //也是十分懊恼
                _2=i;
                _1=n-i;
            }
        }
    }

关于T2挂完

排完序直接输出的魔龙以为自己非常聪明

自作聪明以为排完序，就只用扫一遍输出方案，最完蛋的是

• 只有一组样例
• 样例的询问按从大到小排列 导致我过了样例就以为自己对完叻。。。。。

    sort(qu.begin(),qu.end());
    for(int i=1;i<N;i++){
        cnt_cnt[cnt[i]]++;
        ans=ans*cnt_cnt[cnt[i]]%mod;
        // cout<<i<<" : "<<ans<<'\n';
        if(ans==0)break;
        while(tot<=q&&i==qu[tot]){//直接输出真男人
            cout<<ans<<'\n';
            tot++;
        }
    }

11.24 检讨

昨天晚上睡得早状态好一点

$T1$ $WA$ 完了... 我不知道暴力怎么写所以没对拍，少考虑了$n=1$,即$1$的个数为$0$这一个情况，导致$WA$完了 这应该给点分吧

且没有注意数据数据范围，写了一个递归快速幂，最后两个点还$T$了。先 预处理/记忆化 一下就过了

$T2$ 容易写出$70pts$的$nlogn$ 做法，实在想不出如何快速回答$1e9$的询问，甚至认为这是一道不可做题。

后知当询问大于一定值时，答案一定为$0$

我打表找规律的时候没打到那么打，没发现

$T3$ 代码写的很短，常数小且加了一些剪枝，用$nq$的复杂度在$4s$内过了$n,q\le 5e4$ 的点，拿了$40pts$

$T4$ 写了一个$2^n \times (n^2+m)$ 的二进制枚举暴力 拿了$50pts$

赛后觉得用$dfs$可能更优，$dfs$更容易剪枝，优化，对于小数据范围的题，可能可以拿到更高分

由于题目较为简单，写的也很顺，时间分配很合理

如果时间充裕可以给$T1$也写个对拍，$T1$挂完挺难受的

检讨

赛后感受：

这次比赛感觉良好，除了第一题稍微没判断完和第四题暴力太暴力了，少了些许分数。

今日检讨：

第一题:

在赛时，我没注意判断字符‘1’的个数为奇数时，‘0’的个数对结果有误关系。如果‘0’的个数为1的话，这个2进制的数无法满足和是3的倍数。

第二题：

思路是正确的，但是没有注意到题目中的可疑之处。它的模数只有500007，但是它的询问的区间是[1,1e9]。 因为模数太小了，所以很容易得到0，一旦结果变为0后值就不会改变了，只能为0。所以可以发现当n的值在2250000以内的话，结果就不为0 。但是一旦大于2250000的话值就为0 。

第四题：

这道题一共有2可以降低时间复杂度的地方。 第一，是可以在遍历DFS的时候，枚举判断此结果合不合法。 第二，是不用每次把所有结果都遍历一遍。提前记录所有相同情况的数量。最后计算在一起。

总结

本场比赛我的写题思路十分的良好，但是没有仔细的检查，导致没有将自己能写的所有分数全部拿到。日后需要努力。

T1全挂这一块

其实这次T1丝路挺明确的。就是答案为-1的情况没讨论干净。因为写T1之前休眠了一会，感觉时间不太充裕去写对拍了。于是就跑了，然后就挂完了。TwT。没什么好说的，以后就是对于任何把不准的题，没有大样例的题都最后写个对拍。

T2死脑筋这一块

一下就想到了70分的做法，写的也挺顺利的，然后就卡住了。死活想不到1e9的怎么做。什么方法都想了一下，但就是没想到奇怪的模数。写的时候还吐槽了一下这是什么模数，简直是阴间。

T3被信息差这一块

T3写完暴力之后想着怎么优化，想着想着这一定可以用二维数点去优化，然后呢，然后就没有然后。考试时就一直觉得那斜着到底怎么数。考完后，原来要结合一下数学的知识点，还是我太愚笨了。

T4交给对手这一块

写T4的时候没时间了，写个-1跑了。

DAY6 检讨

分数组成：0+20+50+50

评价：T1，T2写的啥啊，T3 T4还可以。

赛时：T1 花了 1h 找到结论，然后写了半天样例不过。调了一会就过了，但是代码写的过于烂导致自己也不想调了。捏了两组样例过了就直接开 T2。T2显然根据分解定理和阶乘算答案。然后直接写了个欧拉筛觉得它快。直接自断预处理这条路而且计算因数又是根号的。赛时没算清楚复杂度认为还可以 70。T3 乱搞二分比别人多了10分运气好。T4 写了状压。

问题：T1 写了大芬代码让自己都不想调了，应该简单化实现。比如写了一堆看看能不能合并一些之类的。T2 应该惯性思维一些，比如就用埃筛其实是可以直接找到因数个数的。且数学较差需要练习。关于时间分配：T1，T3 花了较长时间，但大多数时候都在想同一个东西，思维可以发散一点或者换个思路。

改进：先写暴力，比如今天 T1 拿不稳就先写暴力，至少有个分。数学应练习，只要是数论。

11.24严重挂分的检讨

赛时历程

T1 注意到只有两个 1 的位置可变，且 1 之间的距离不大于 1，所以没有推结论，而是直接枚举，写出了 115 行代码，好在一次通过，对拍拍了 $2 \times 10^5$ 组

T2、T3 第一眼没思路，跳了

T4 首先写了一份暴力，由于 $n \le 40$ 实在太像折半搜索，所以花了 inf min 往这方面想，思路：将限制分为在第一个块内、在第二个块内和跨越两个块三种，前两种可以在枚举时就排除不符合的部分，对于第三种，考虑如果知道第二个块的前缀，则第一个块的后缀可以被求出，然后枚举未确定的部分，计算答案。虽然时间复杂度不是很对，但是比直接暴力快一些，于是写写写，写出了 170 行超简单代码，最后五分钟 de 出 bug，大样例肉眼比对过了，交

T2 一眼注意到神秘模数，于是打表，发现在大约 $n \ge 2 \times 10^6$ 时答案会突变为 $0$，于是只用 10 min 就切了这道题，对拍拍了 $2000$ 组没有问题

T3 想成树套树了，但是当时 T4 还没写完，于是只写了暴力

挂分详情

T2

思路正确，使用埃氏筛预处理每个数的因子个数，但是由于没有注意到 T \le 10^5，所以答案是每次查询时才求出的，于是写出了 $O(n \log n + T(n + \sqrt n))$ 的代码，由于清空是 $T \sqrt n$ 的，所以导致所有点都 TLE 了，痛失一百分

对拍时，由于数据过大时暴力跑不出来，所以想到数据重复性的问题，所以选择了 $T = 10,N = 10^5$，只关注了答案的正确性，而没有注意多测时可能出现的问题

改成预处理答案后代码时间复杂度是 $O(T + n \log n)$，可以通过本题

T3

由于过于聪明，没有想到每次查询时枚举点判断是否在范围内，而是通过类似前缀和的方法计算，于是对横纵坐标分别离散化，但是在查询时，$y$ 坐标范围的计算有误，样例的坐标又恰好是连续的，同时对暴力的分数不太重视，导致没有检查出来，痛失二十分

T4

最后输出部分

cout << a[i] + (s >> (i - 1) & 1) << " "[i == n];

由于写漏了 \n，且没有用 fc 测试大样例，而是肉眼观察，导致输出了不可见字符却没有被找出，痛失二十分

赛后反思

• 对于需要多测的题目，如果 $T$ 较大，应当考虑清楚 $T$ 是乘在时间复杂度上（每次单独计算）还是加在时间复杂度上（预处理或离线）的，选择更好实现、时间复杂度更优的做法

• 对于多测的题目，对拍时应当分别构造 $T$ 极大和 $N$ 极大时的情况，防止出现多测不清空、空间爆炸之类的情况

• 重视能拿到的每一分，在写出的暴力过了小样例，大样例超时的时候，不妨再多看两眼代码，或者输出中间变量，看看是否符合手模的过程

• 坚决不交没用 fc 测试过的代码，肉眼观察可能出错，只有用 fc 这种标准的比较方式，才能彻底杜绝格式出错、输出不可见字符等导致挂分的问题