今天又是挂分的一天（哪天我才能不写检讨了啊!）

得分情况：100 + 10 + 100 + 0

时间分配： $80 + 60 + 60$(包括暴力和对拍) $+ 50 + 10$(读题) $= 270 min$

不得不说，今天我的时间分配相比昨天和前天有了大进步，在相对较难的 $T2 、 T4$ 也是花了相当的时间去想（可能也是 $T3$ 太水了，被一眼莫队给秒了）。尽管得分上并不理想，但是这好歹是有了些许进步了。

$T4$ 的失分是意料之外，情理之中的。我在不清楚贪心的正确性的情况下仅仅因为通过样例就盲目相信，更因为时间不够就没有完成对拍，所以虽然意外，但也不算惊讶。

挂分的情理之中不能作为因此失分的理由，我在长达 $20 min$ 的思考中竟然没有相出最暴力的 $dp$ 解法，这又证明了我的 $dp$ 在相对其他方面的劣势，应当加强关于 $dp$ 的相关训练

11.19 检讨

Background

• 常sir：题目难度可能非正序排列。
• （（不是很聪明的）我：T1与T2肯定放反了，故意的。）

赛时经历：

于是先看了T1,30min后也没什么思路，打了暴力就开T2去了。以为是贪心与是在想出第一个结论后开贪，贪完发现过不了大样例，看了半天大样例，在约10:00时才发现贪错了lol，于是又开始想其他的贪心方法。20min没思路，又开始才结论。在冥思苦想了10min后，终于放弃了，尝试打暴力但是一直爆掉。想到即使是错误的贪心也可以过性质A（10分），于是才T3，看上去像是数据结构题，以为又没学过。直接打了暴力。T4想到DP，开始认为可以O(n)写，但一直设计不出来，再加上时间问题，于是匆忙想出了一个O(n^2)的，看到过了样例以为没问题就交了。

正解：

• 先看T1实则是裸的贪心，应先切去大的点，所以除最大点外，其他点作为次大点的情况有且仅有一次，而最大值则是一边两点中的最大值，所以结论也是十分简单。
• T2实际是与T3放反了（万万没想到）。是贪心+DP（好像）。
• T3其实十分简单，是用莫队离线处理区间的数，发现每次指针的移动之多改变一篇有效题解，所以判断一下即可（也可以用树状数组带个log，也能过）。
• T4DP但不会。

总结：

站在赛后的上帝视角看本场比赛，以为T1是T2所以半小时没想出来就打算暂时放弃，以为T2是T1，就觉得T1都写不出来就废了，死磕了约2h，结果暴力都没打出来，唉。这导致没时间想T3了。T3一眼数据结构的以往经验都是一些十分hard的，代码量堪比大模拟，学都没学过的大数据结构。所以打个暴力理所应当，但这次被阴了QAQ，T4DP好像是循环应从前往后而非从后往前（更好求最值），所以爆了。

改进：

总之，T2与T3放反了是预料之外的坑，自认为T1与T2放反了是自己给自己挖的坑。在做题时，不应该抱有过强的心理作用。不应这是T2,T3或是数据结构就认为十分的hard（但铭记day2T2惨案（把T2看成水题）），更不能死磕T1（但铭记-sT1惨案（误以为很难，实则是水题））。

T1

初始往树形dp想，后面由于树的无根性退不出来转移失败。于是考虑贪心，手模样例有了个基本思路，就是每次优先考虑找到还和人家相连的边权最大的点，把它周围的边全部删除，以免留到后面祸害他人。代入其他样例发现是正确的所以开始考虑实现。隐隐约约感觉这个东西很特殊，可以推出一个式子来算，但是算了半天想不明白，所以就去考虑硬模拟。结果令人绷不住的是想了一个多小时都拘泥于怎么在删边的情况下维护子树最大值，甚至在那想可回退并查集（可我显然不会写），硬是没有想到反过来用建边做。赛后听人家讨论一下懂了。想起来之前还专门看过一篇题解着重强调正难则反的思路的，然后这么久了还是想不到。由于没发现这个性质导致暴力都没写出来，写了对拍代码用都没用。

T2

这个暴力会写先写了。写完过后考虑了下那个相对复杂的或起来再向下整除2的操作，也想到了相当就是右移一位。然后就开始考虑怎么选数字。然后思路走偏了，花了很久写了一份完全错解的贪心，然后过不了大样例。用暴力推出来大样例的操作方法后发现和我的思路大相径庭，感觉没有希望就跳了。

T3

加一篇帖子的操作挺像区间加，首先想到了线段树。但是后面每次问的东西又不好用线段树搞。发现每次问的都是个连续区间，且不要求强制在线，于是就想到了莫队。然后实现又出了问题，统计答案没想到可以在莫队的过程中直接算导致我每次询问都有个$nlog$的查询。时间复杂度爆炸了就只有$20pts$。

T4

这个题想的最久。还是区间加想上线段树。结果又是一个很简单的性质没有注意到：划分的区间一定单增，所以写出来的dp式子很怪，得从前面的一大段取$max$来转移，$qn^2$的式子肯定只能拿第一档的分（我脑残加了个log上去导致第一档的分都没有）。感觉不甘心，况且这个式子看起来也很有心动的感觉，不是很复杂，后面就花了大量的时间来想这个怎么优化成$qn$（因为前面的题目由于没发现性质属于暂时完全没招，这个至少我还能有思路方向）。然后用这个时间好像是写了四五个还是五六个不同的优化方法，结果全部失败。红温了。

今天是差三个档的一天

T1：

• 依旧20min+没出思路写了个dfs暴力匆忙逃离 可能with常老说的（没想出来觉得想难了 先写后面的去了）
• 后来回头看 绞尽脑汁 想出来个贪心方法: 考虑从没有边 慢慢建成题目所给树 每次连边 连两端点所在子树最大值之和最小的边 但是只能$O(n^2)$做 就一直在优化这个办法 一直没想到怎么优化 寄了

T2：

• 首先20min+看题没什么想法 写了个乱积极贪的贪心 样例都没过 直接放弃 去看T3了（所以前1h只有10分）
• 写完T3和T4后再回来看 依然没什么想法 但其实想到了题解的把$\left \lfloor \frac{a|b}{2} \right \rfloor$ 转化成$\left \lfloor \frac{a}{2} \right \rfloor | \left \lfloor \frac{b}{2} \right \rfloor$ 然而并没有继续往后想了（其实应该也想不到 所以也只有打个暴力 最后还打错了x_x;

才发现这里写了这么多字了 要是全部放在这里就亏了

把T3和T4的放在总结里面就比较划算了！

但是突然出去一看觉得字又有点少了 所以我将吟诗一首：

• T1 正解想不通
• T2 暴力没成功
• T3 爽写非常猛
• 不开龙龙见祖宗

11.19 NOIP Day3

主要检讨 T1 和 T2 爆 0 的问题。

首先说时间分配问题，T3 和 T4 一共大概写了 1h 30 min，确定了 T3 和 T4 不会挂分。然后其余时间基本都是花在 T2 上。

T1 对自己过于自信，检查了思路没有问题后就，用手捏样例试探了几下后就没有管了。然而出现了令人悲痛的事情，我的实现写挫了，我的代码并没有严格按照我的思路去写，同时我在写的时候没有感觉到丝毫不对，然后我就没有丝毫意外的保龄，没有丝毫意外的要写这个神秘检讨。而且我没有写对拍，这也是我最终宝玲的原因之一。所以我认为我需要加强写暴力的能力。

T2 则是一直在坐牢，推出了一些性质，但是不知道这些性质该怎么用。比如说我推出了每一次的 1 操作是独立的，然后不知道该怎么用。然后在电脑前脑洞大开，想到了各种稀奇古怪的做法，比如说 01Trie 之类的。还想到了一些根本没有用的结论，比如 $a | b = a \bigoplus b + a \& b$。而且还试图打表找规律，但是显然没有任何规律。最终 T2 交了一份错误的暴力代码。(或许应该用错误的贪心代码，或许拿的分还可能更多)。

T4 我或许也应该反思一下，其实我看的出来是一个 ddp，但是我的 dp 转移式子有点奇怪，所以我不知道该怎么写，而且 ddp 写的经验也少，知道矩阵乘法可以表示 max,但是最终还是没有继续去写。

综上所诉，本次模拟赛主要的失误就在于 T1 和 T2 完全保灵，所以我的分数就十分的低，让不知道的人还以为 T1 和 T2 与 T3 和 T4 放反了。我觉得或许我可以从增强自己的思维能力入手，要多想和多挖掘性质，并且要对 T1 写对拍，（因为这次我只对 T3 和 T4 写了对拍，所以这两道题符合预期分数）。总而言之要加强对 T1 和 T2 的警惕。

11.19检讨

比赛历程

上来就开始看T3，一看就想到写个二分，十分的愉快。但被不知道怎么快速求出一段区间大于一个值的数的数量。想过写个权值线段树，但有发现写不了。赛后看题解是可持久化线段树，就其实没网这方面想。听别人说可以用莫队写，但分块这个专题就没学好。------可持久化线段树王完啦。

又去看T4，其实一下就看出来是DP了，但写不来，没办法，只有跑了。

再去看T1一开始的想法就是每次断掉最大点的边。自我感觉这样不好写。自作聪明想着，从小到大连边是一样的，然后就美美的四掉了。

接下来是T2，T2写的就是比较艰辛。赛后才知道这道题有多难。赛上以为自己聪明惨了。开始写T2的时候还剩2h。第一眼看到T2就给人一种有特殊的性质的感觉，二来又感觉T2暴力实在是写的莽。就索性直接分析。苦思冥想给自己干得睡了30分钟。醒来之后大彻大悟。发现了介个。

仅此而已，也不知道怎么用，然后写了个唐人贪心代码比赛就结束了。

有时候就是知道该怎么做，但不会做。还有些题暴力打不来。对T1也不重视乱球写一托就跑了。

DAY3 检讨

分数：T3 100其他都 0。

时间分配：T1零零散散花了1.5h，T2 0.5h，T3 1.0h，T4 1.0h。

自我评价：还是太彩了。如果不挂分看着就还一般，可是T1 T4挂完了就打的很烂。

赛上经历 & 反思：T1贪心策略看出来了，先选大的。再选小的。然后不知道正解怎么写。只会暴力找当前最大的对应的点所在另一个块的最大值。也就是$o(n^2)$ 的，想了很久啊。正这想了反着想。就是没想到可以根据单个点贡献延后计算。还是对题目的性质挖的不够深。这一直是我的一个问题。然后开T2，由于我深知位运算能力更差，于是还是明智地跳题了。T3 还是先写了个暴力，然后看到 5e4 直接敲莫队了。最开始写出来还是错的，输出调试了一会儿还是调对了。然后开始对拍，和暴力拍了几组都是对的。由于我计算和用了树状数组，所以继续想优化未遂，开 T4。区间和嘛，但是可以用线段树。那答案怎么算呢。开始想到它是又若干个上升下降线段拼起来的，以为是从拐点贪心。但是感觉不太对只能 dp，想 dp 时就没怎么想拐点的事了，因此写了个 $O(n^2)$ dp,但是还有 q 次询问就不能再用n次遍历找最大最小值。就写了颗线段树骗 15分。两个样例都过了就没管了。然后就去检查 T3 和 想 T2了。接下来讲讲我是怎么挂分的。

挂分：T1 本来就写的暴力，所以就没捏样例。没想到 dfs 函数里没递归，只写了一层....

int get(int u,int fa){
    int res=a[u];
    for(auto x:g[u]){
        if(x==fa||mp[x][u]) continue;
        res=max(res,a[x]);//应该是get(x,u)
    }
    return res;
}

T4 也是，我想 $O(n^2 \log n)$的暴力骗15分的也能挂？然后也没捏样例。

void down(int o){
    if(tr[o].tag){
        tr[ls].tag+=tr[o].tag,tr[rs].tag+=tr[o].tag;
        tr[ls].mx+=tr[o].tag,tr[rs].mx+=tr[o].tag;
        tr[ls].mn+=tr[o].tag,tr[rs].mn+=tr[o].tag;//o写成rs了
    }
    tr[o].tag=0;
}

改进：无论什么题都要捏样例，今晚重点练习 codeforces div2 C 和 状压 dp。

其他：检讨有点多啊，字数不够于是发了篇较为详细的 T1 题解赎罪。

11.19 反思

赛时历程

T1、T2 没思路，跳了

T3 一眼二分 + 主席树，半小时写出线段树外二分的版本，测试极限数据 600 ms，开始对拍

T4 注意到了划分出的区间一定单调，写了 $qn^2$ DP

T2 注意到无需枚举删除操作，搜索合并哪些数，取最小值即可（其他更大的数删了就行），感觉是贪心，写出生成数据的代码，试图观察规律，眼睛看瞎了都没看出来

T1 感觉是贪心，每次选两端权值和最小的点，写出 $n^2$ 暴力

感觉 T3 时间复杂度不对，一测发现 900 ms，于是重写了一份线段树上二分的代码，300 ms 拿下

T1 写了一份每次删边后更新两端点所连边的代码，对拍后不对一直改，一直错，最后发现时间复杂度还有问题，放弃

注意到 T1 每次一定删权值最大的点的边，写完又错，拼尽全力找不出 bug

赛后总结

• 进入状态的时间太长，每次都是后期才找出性质，但是没有足够时间写

• 有时得出性质不知道怎么用

DAY3检讨

今日分数：

40+10+0+0

今日反思：

T1 OI团伙：

赛事想题时用了比较少的时间，用的比较暴力的思路写的。但是我本以为只能过第一部分的数据点，但是出乎意料的过了第三个数据点。本体的思路是先排序再把结果加起来，复杂度是 $O(nlog^2n)$ 另外一个$logn$的复杂度是来自并查集的合并。但是排序可以在并查集合并中一起完成。所以可以直接$O(nlogn)$的复杂度完成。 但是还有其他更简单的方法完成。思路参考题解。再推出式子后可以直接 $O(n)$ 的复杂度完成。 但是没推出式子，而且没有时间来思考如何优化复杂度。

T2 合成

这道题我的想法是暴力贪心找结果，但是贪心思路不太对，用了1h~2h的时间来调试，但是还是没调出来。于是只完成了特殊数据点的分数，找到规律--直接找到最小的那个数就可以得到答案。 最后总结下，这道题我没有想出贪心思路并用了过多的时间来调试，没足够的时间来完成后面的题。

T3 Y幸运

最开始时我想用线段树来暴力$O(n^2logn)$ 的复杂度来完成。但是突然想出正解思路--二位数点。但是由于不太熟悉，没有写出来，并且暴力分也没有拿到。 总结：由于专心想正解的思路，所以没有拿到暴力分。

T4 模仿树

这道题的正解思路是一个DP+线段树，但是我想的是一个贪心的思路，所以总思路是错的。（现在还是不太理解，所以还是不太行，暴力也没写出来）。

总结

本次比赛挂分严重，但主要问题出现在调试题目的时间过多了，而且因为想到正解的原因所以没写暴力。以后的写题需要注意这个问题。

总分为100+0+20+15，

时间为2h+30min+1.5h+30min

T1 提看了半个小时才认为我看懂，发现别人都写完了，十分的慌张，观察样例，随便写了个贪心，发现样例没过，又看了一眼题发现题好像读错了，由于不知到题在干什么，随便猜了几种意思，发现应该是段完边后再找两边最大的加起来，写了个贪心，过了样例，认为正确性很显然，就没管了.

T2 想到了如果二进制第一位相同就肯定可以操作，但不知道该怎么操做，把A性质写了但A性质写挂了，就先去看T3了，发现似乎可以用主席树直接维护，但不会写，想了半天离线，发现不会，发现莫队可以做但之前没写过，但感觉很好写就开始写了，但调试很长1h没调出来就先写T4暴力力了，拿到了15分，又开始条T3,还以为莫队做不了但还是一直在调，最后10分钟样例只有一个地方不对了，但去保存文件了，就没调了，赛后发改一个地放就过了

主要原因是在T1花了很长时间读题，并且T3之前没写过莫队，赛时要自己研究花了很长时间，T2,T4几乎没时间研究了，T2十分的暴力也没打！

DAY 3

MD，得把体量压下去， 这么多字我都懒得看， 还很浪费时间。

7:30~8:18

A B C 初思考，D 没什么想法。

结果今天没怎么给样例，昨天的经验没用上...

A 一开始只在以最大值为划分思考。
B 又把题读错了，没看到可以删除，但没什么影响。
C 想了一个前缀和强行维护每一个数的数量来 $O(1)$ 查询，发现跟暴力拿分一模一样，就没多想。

8:18~8:40

A 想到排列组合的思路之一 正难则反 ，很快就想出了逆连的思路，遵循前两天的总结把样例推干净了再写，挺好的。
写完决定对拍。

8:40~9:14

对拍，考虑到赛上 Windows 可能没有 g++ 的环境，小熊猫这个版本编译出来的 exe 又有问题，于是决定去 NOI 看一看比赛环境的小熊猫，然后就被逮了。

结论

UPD DAY 3 下午:考场上的小熊猫版本编译 exe 是无法直接双击运行的，但是在对拍程序里面用 system 是可以运行的！
换言之，考场上如果没有 g++ 的环境 (即无法在 Windows 使用命令编译) ，用小熊猫跑对拍唯一需要注意的问题就是 要手动编译程序 ！！！

确保了生成器的数据强度总共跑了 1500 个，一切顺利。

不过生成器，暴力和正解用的是一套并查集，难免有点担心一错全错...

9:18~10:13

全力写 C ，莫队用的少所以搞忘分块了。
感觉时间不够来不及对拍了，切 B 。

直到最后

B 瞎推性质，挂了好几次好不容易写出来结果还是错的，暴力也有问题...
D 也没想法，确实想不出来。

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

我非常检讨T3基本挂完这件事。

我在赛上刚拿到题非常有思路，直接说这不是主席树上二分水题吗，于是在PDF上自信地写下：

然后去先去看T4了，写了一会没推出啥东西，只好写了一个最基础的暴力。

之后好像又穿插了少量写T2的时间，不过还是回来看T3了。此时突然发现有一点遗忘主席树的板子了，于是开始边敲边推，居然比较顺利地写完了，再稍微Debug后过了样例。然后就顺便搓了一份暴力和对拍，看着对拍挂着跑了1h+，感觉万事俱备，甚至没考虑过把主席树外二分改成主席树上二分。

然后，如你所见，我TLE了：原来是线段树空间没开够 $n\times 30 \rarr n \times 4$，于是$100pts \rarr 20pts$。

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

看出来T2比T3难了。

刚开始看题，就发现其实$\lfloor{\frac{a\space |\space b}{2}}\rfloor$就是$(a\space |\space b) >> 1$，于是直接枚举合并到第$i$轮，然后从$n$个数中选出$2^i$的数并在一起来计算答案。然而过不了大样例。

过了很久我再次挑战T2。认为是实现上的问题，于是重构了代码，按每一位轮流排序来求并起来的最小值。然而还是错，甚至错得一模一样。我于是重写了一版暴力，仍然过不了大样例。在绝望中我终于看清了假算的真面目，只好交了个最低档的暴力。