Day2

有的时候真的很想报警，把那些出神秘贪心题目的出题人给抓起来浸猪笼：）

T1

贪心虽然再次失败，但是对比昨天至少写出来了，拿了一半的分。

赛后就着赛时的代码写，感觉越讨论越复杂还死活过不了。所以果断考虑了重构思路和代码，然后就比较顺畅的写出来了。所以在写贪心的时候最开始的思路确定和看待角度非常重要，感觉思路有点问题的时候就不要硬想，东补西填能把自己绕死。保证一个清晰明了，且能明确这个做法能处理所有情况（至少大部分）是非常重要的。

所以总结，贪心应该思考和手玩样例居多，不要着急先写代码。

T2

承蒙出题人的大发慈悲让我暴力过了。赛后学到了两个很有意思的思路：倍增DSU处理连续区间的合并，以及反拓扑 + bitset维护有向无环图的可达性（虽然都没时间实现，哈哈）

T3

李超树忘光了。当时看着这个该死的随询问改变的K值束手无策，结束了也没想到线段维护也真的令人揪心。然后补这个题也花费了今天大部分时间太菜了，同时也警示了自己一下写代码注意常数，感觉总是写出一些常数和理解难度惊人的伪人代码。

T4

上来想了一个不能再暴力的暴力，所以就考虑了一下优化，开始往选边和组合数的方向想。

拆贡献想的很顺利，考虑可能成环的情况。这个时候错误的以为n - 1个点和n - 1条边就是环。可输出来第三个样例不对，手模拟一遍才发现还有n个点n - 1条边也可以成环的情况。然后我就被这个恶毒的情况卡了很久。因为前面已经花了一部分时间，所以有点不甘心。但是后来看看时间，然后这个时候T1还没写，想起来老师说的“沉默成本”。最重要的，老师说这是个偏难的紫题，多半是我不可能僭越的。所以恢复了理智写了暴力，然后溜了。

后来想到其实一开始就不应该往正解想，写了暴力没准还能多想会部分分。并且注意到这两天的暴力分都可以拿状压dp写，而我感觉写的并不好，应该多练练这块

over

今天感觉写得很顺畅（至少前3h是这样的），顺畅归顺畅，但是没有对，写是写爽了，可是挂一堆分。仔细一想，造成这种情况主要是因为没想清楚，拿到题就写，其实思路是错的，还沾沾自喜，觉得一下就想出来了，还能把代码写出来很厉害，其实是掉进了思维的陷阱，运气好的一部分分，运气不好就只能爆零。所以写题之前一定要先想清楚，想想思路对不对，代码怎么实现简单，这样不仅能预防写半天写个错解挂分的情况，还能防止写一半感觉越写越难，最后发现实现有问题而红温放弃的情况。就像老话说的，磨刀不误砍柴工，用一部分时间想明白远比不明不白直接写要快，也更容易对。这种百利而无一害的方式是应该多使用的。具体的，拿今天来举例子，像T1我就应该仔细想一想，看我的思路有没有对，这样我就会发现需要并查集来维护不一样的人，而不是随便排个序就觉得对了。想明白了自然也就不会出现感觉写的很顺畅却挂和多分的情况。最后说一下每道题的问题吧。T1：没想清楚就写，以为很对，结果挂一半。T2：时间复杂度没算对，以为是60分的代码，实则15分，感觉dfs的时间不太好算，容易算错，是在算不明白可以跑一下对应的暴力，看跑多久，就能知道大概的时间复杂度。T3：福利机，按题目模拟就有40分，没什么难度。T4：码力有待提升，一会就写出了暴力，结果RE了一直调不出来，最后爆零了。

纯享版：

有时真的不理解赛时在干什么

$T1$一来就想到了用并查集维护一定不同和一定不同的的集合

当时感觉自己看两眼就想到正解了也是高兴惨了

可能是$csp-s$集训的时候练了拓展域并查集吧，想到维护相同与不同就想到了拓展域并查集，也没怎么检查正确性，就去写了，写了$2h$,实在是调不出来，又不知道哪写错了，就跑了

由于写了$2h$一点分没拿，就开始慌了（也该慌了吧 $T2$也没怎么认真看题，粗略的看了两眼就去写了（没看到有出口和入口之分。$10mins$急速敲完。写的时候我就觉得不对，这可是$NOIP$模拟赛啊，常再好心也不能放个黄题吧。我本打算写完再去细细读题，但大样例都过了，就直接跑了。

$T3$打完暴力跑路了

写$T4$的时候已经有点不正常了（指我人，暴力一个小时没调出来，思路很对啊，就是调不出来（赛后$4min$调好，红了）

最后$40mins$与$T1$搏斗，终没能战胜。都是赛后才知道不能用拓展域并查集

——————————————————————————

看似问题很多（确实很多,但归根是从$T1$开始，节奏,心态就乱了。$T1$为什么会写不出来啊，状态有一定影响，但确实该去练一练$黄-绿$难度的简单算法应用题了。顺便提升一下代码能力，代码能力太差了，调个什么都调好久

11.18 检讨

总分135=40+20+50+25

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

T1

看起来要建图，认为o(n)就可以做

写了个并查级发现大样例挂了

发现答案可能>2,就建了图，维护不等的关系

，用了一个并查集，维护相同的，就可以维护出不等关系了，在从前向后贪心，从不等的集合中得出MEX值，在把他输出就可以了，但赛时维护错了，但过了打样例不会运行vscode

所以没写对拍，就只有40分了.

T2 把题读错了，以为是单向的，就直接用并查集维护就只有20分了，其实由于k<100,所以只用维护每个联通快可以到的点，最多只有100个这样的连通块

T3 写了50分的暴力，维护出ai-k*bi的总和，由于答案是减去一段前缀和后缀，所以只用维护前缀min,后缀min就可以了o(n)就可以维护，正解是用李超线段树维护。复杂度o（qlogn).

T4 枚举了每个节点的父亲节点，并检查是否有环，统计相同的边数就可以了。复杂度是o(n!),得到了25分，正解是要枚举prufer序列，用WC数树优化。

~~~~~ 检讨 ~~~~~

比赛状态

今天有一点小困，因为昨天12:00才睡。前面1h是昏昏沉沉，迷迷茫茫，困困倦倦，苦苦恼恼，烦烦躁躁。

T1

今日梦魇 比赛时看到这题就有种不好的预感。因为这道题不会打暴力。于是这道题就只有正解与10分（送的点）。于是乎开始苦思冥想，思冥苦想。其中也发现了一些性质，就是差一点。很明显，到比赛结束，到下午补题都~~~~没写出来。

也不知道为什么，可能从做法上就错了。QAQ

T2

常规60分暴力，T1花太多时间了，没时间细想。

T3

依旧一上来写个暴力就跑了，深一点的做法没有去想。

T4

感觉暴力打起来都很困难，要去练习打暴力了。其实赛后听完暴力之后，直乎这也太暴力了吧，仔细一想不就这么暴力吗？小丑

总结

差不都第一题写不出来就炸完了。真的就炸完了。有点想法总感觉能写出来。直到下午才发现大错特错。遇到像这种暴力也不太会打，正解写不太会写的真的很无奈。还有一些题目的高分做法也太高深了。就算学过也不太能写出来。鼠鼠得吃失败了。。。。。

DAY 2

总述

今天状态还是一一般般，但是受某篇高考复健指南那句话的鞭策，或是激励:

不要觉得高考的时候你的状态会有多好，平时应该多提高自己表现的下限。

A 又是今天的背锅王了。
今天时间线写的挺严谨的。

7:30~7:45 A 预思考

非常容易想到并查集和对立关系，但是非常不幸想的太简单了，注意到 $n,m$ 小的离谱，觉得二元并查集就可以解决。

其实当时应该意识到这个规模乱搞也能水过去的。
还是犯了个问题:没看下发样例，但凡看了我也不可能觉得这道题能用二元并查集做。

7:45~7:52 B 预思考

注意到 $k$ 小的可怜想到并查集缩点建 DAG 跑 bfs，发现是算法杂糅水题。

7:52~7:58 C 预思考

没什么想法，只有暴力。

7:58~8:00 D 预思考

毫无想法。

8:00~8:36

于是他错误的并查集开始了。 更蠢的是什么呢，赛上二元并查集我想了半天怎么实现，merge 和 deliver (设为敌人的函数) 瞎写了半天愣是没想到一个点拆成两个的方法。
然后好不容易写完看样例随即发现一个惊喜:

怎么这个样例输出有 $2$ 啊？

感觉 A 寄了，跳 B 。

8:40~9:17

四十分钟怒写 B ，感觉良好上个厕所回来静态查错。

9:17~9:38

结果 B 第二个样例就过不去，小调一会发现是二维地图映射到一维点的函数写错了，改完满怀希望结果大样例又错了，感觉非常难受啊——

9:38~9:41

按照一名奥林匹克信息学竞赛选手的基本直觉改了 DAG 上 bfs 的实现方式，然后就莫名其妙地对了？一分钟之后想到是当时初始化一下子想不到优化方案于是写了个错误的实现，改完删完代码就清爽了，果然算法都是简单高效的。

还是得想清楚实现方式，力求简单高效的实现。讲真我强迫症挺严重的，但是受窘于赛上的时间和空间限制有的时候也不讲究那么多了，看来特别是对于数据结构大题想好实现还是很重要的。

9:43~9:59

思考维护这种问题，脑子里面迷迷糊糊想到一个什么 李超线段树 ，想到之后就果断放弃了。 糊弄掉 C 。

10:00~10:30

因为 D 毫无想法回到 A ，想到了四色定理，很离谱是不是但是我觉得非常合理，然后继续乱想，创造新名词: 四元并查集 。
不过想了一会，很快就证伪了。

这里为什么卡住呢？继续挖掘问题是很明显的：想到并查集互斥操作之后就认定它是对的，卡住也不去想其它思路。
这个问题说小则小，说大则大。应该要去有多元发展以至于是乱搞的"后备能源"才能不被吊死。

10:30~10:53

又上了个厕所，想到 D 可以拿组合数乱写，当然我没想到那是树！
看样子自己后期对计算题想的思路都挺蠢的，特别是想到之后会质疑一开始为什么没想到的那种。

于是 D 就毫不意外地伪了。

10:53~11:40

回到 A 就开始颓废了，基本上完全没进展。

11:40~12:00

最后想到可以拿一个并查集建图(MD绝对是从 B 剽窃过来的思路)的乱搞做法，愣是卡着点极限把样例过了，但是我搞忘判 -1 了......

11.18 NOIP Day2 检讨

从总体上来说，时间分配其实问题不算特别大，但是在个别细节上有很大问题。

首先是 T1，我一开始就拍了一个拓展域并查集上去，然后发现过不了大样例，开始思考，发现问题很大，考虑开很多个并查集，觉得有点难写，然后放弃了这道题，因为此时已经过了50 mins。

然后我就写 T2, T2 没注意看题目中的传送门，然后啪的一下又写了一个并查集，然后一测大样例，过了，思考了一会，发现没有什么可以写挂的地方（并非没有），就跳了。

写 T3，首先把式子给拆出来，一开始思考了一个错误的方向，我们给 $pre_a,pre_b,suf_a,suf_b$ 建线段树，然后每次用线段树合并给合上去，然后写完就发现失败了，又分析了一下时间复杂度，也是错的，然后考虑换一个思路，发现有一个神秘凸包，先假定我会 李超线段树，然后我就会写了，（但是假定的前提是我会李超线段树）。然后我就去思考 T4 了，然后把 T1 代码也给写完。此时大概还剩余 2h 30min。

我在敲完 T4 代码后又回来写 T3，大约还剩余 2h。然后靠着记忆，思考了一会李超线段树大概怎么写，但是一直有十分大的问题，最后回头看了一眼 T1 和 T2，但终究还是没发现什么问题。

最后 T1 和 T2 挂大分，T3 long long 没开全直接见了祖宗，T4 是唯一符合预期分数的题。

见到如此分数，不得不让我反思，我是在什么地方失误导致挂了大量分数。首先是 T1 ，由于一些细节导致了失误，然后是 T2，由于读题问题，导致了我痛失大量分数，然后是 T3，因为对于一些数据结构的遗忘导致了我痛失 AC 机会，然后又因为 long long 没开全，再次失败，所以看起来我就少了十分多的分。但是这样的失分真的无法避免吗？答案显然是否定的。或许再多看几次题目，多拍几组样例就能发现问题了。

11.18 检讨

T1挂了50分错误点有两个：

1. 在比较绝对不同对时要把信息传给根，再通过根的比较得到答案。
2. 再并查集的合并时要把编号大的合到编号小的。

T2竟然把题读错了，传送门只能单向传送所以不能用并查集合并(大样例是真的水！！这都能过样例！)，正解是先用并查集判断连通块，再将传送门看做有向边，用BFS判断是否到达。赛时写了T1后已过去1h，看了T2后以为是道水题，只需要判断连通性即可，但写了1h才调过样例。于是看了眼T3想到并写了O(n^2)的做法，估分50（正解是李超线段树）。T4开始没看懂样例，于是就认为写不动了（正解是啥没听懂，十分难）。隔了几十分钟后又看了一次才看懂，但没什么思路。

总结：首先写并查集时应注意，是否将原点赋值成了根了，是否需用注意合并的顺序。千万不要把题读错了，不然神来了对拍都没用QAQ，应该多手搓几个样例（大样例是真的水！！），写暴力时应放平心态（近两场暴力都没打满，主要是后期心烦意乱根本写不动代码，加上上午本就没怎么睡醒）。下次应努力写出暴力。

检讨

赛后分数：

50+45+50+0

赛后反思：

本场比赛从策略上来说是比较完美的，每道题的分数控制得当。但是本次比赛出现了极大的挂分情况（悲）。首先是第一题，赛时样例过了，但是总的贪心思路错了，可能会出现字典序不对和前后权值矛盾的情况。其次是T2，再写T2的时候，我粗心大意，在最后枚举询问的时候，直接判断能不能到，没有考虑间接到达的情况。从而导致题目错误。最后是T4，再写T4的时候，我先是没有读懂题，后面读懂题后开始想，感觉是有规律的，但是死活退推不出来，于是就去想暴力。 又想了20~30分钟的暴力，在最后20分钟想出来了一个。但是还是报错了（悲）。最后直接挂零了。

最后总结：

本次比赛主要出现的错误是粗心导致的挂分，所以在后面的比赛中应该更注重代码和思路的正确性。完善自己的考试写题思路和对拍能力。

DAY2 检讨

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

时间分配：1.5h多一点写完T1，T2。然后很快写完 T3 50分档，后写了接近1h T4的暴力未遂。最后1h检查T2发现看错题然后调。

自我评价：一般。比昨天好。不够。

赛上经历：T1 由于昨天的教训先把特殊性质写了，然后根据特殊性质延申把大样例过了。然后自己造了个小的也过了就跑了。没写暴力因为感觉 dfs 的话不好延申到正解。然后就开 T2 了，一眼并查集直接秒了。大样例也过了。此时还没知道自己把题看错了。2h不到写完T1,T2。然后 T3 50分也到手了。感觉和昨天完全不一样。后面就感觉效率就降低了。T4暴力一直写不对，最后1h我觉得不能写 T4 了，应该去检查前面的。感觉 T2 有点过于简单了，然后就去检查 T2，果然发现题读错了。此时我脑海立马闪现一个做法：tarjan 缩点。但由于太久没写过且时间感觉不够求稳去写了个暴力 bfs。然后大样例一直不过。由于没有人对 T2 大样例有疑问我也就以为是自己的问题。那为什么 T2 还会有 100 的呢。 然后一直调试。其实我当时已经并查集预处理出来每个点属于的块。但是由于没看数据范围认定这就是暴力。最后时刻只能根据数据范围把小的数据用我以为错的暴力 bfs 大的数据直接用看错题的直接并查集。然后比赛就结束了。

赛后反思：T1 遇到无法证明的贪心应该对拍或者至少造多随机造几组数据。看题需仔细，对于 NOIP 的题来说，自己认为太简单的题更需要注意细节。题意和数据范围都需要看。数据结构题要加强练习。两天考的都没上出来。

非常好检讨 使我警惕

T1并查集写挂了更是神人

T1心路历程：

• 首先20min没看出做法 写了个50分暴力果断逃离
• 在经历了后面三题磨练后 回来看 发现有思路 在写了T2 T4都使用了并查集的时候 对并查集简直是超级敏感 想出来了并查集祖先节点维护不同值的做法 直接20min爽写 爽过大样例 然后就不管了 结果并查集merge 里的fa写成a fb写成b 直接$WA$掉（大样例是真水）

T2这次$MLE$简直是没想象到

T2心路历程

• 一眼看出 每次询问后硬跑一遍bfs的做法 直接花了20min写了个小暴力 然后过完样例 稍微思考了一下
• 然后就看到了$k$的范围和$q$的范围 一想就是$O(k\times q)$的做法 就想到用并查集缩点 然后每次询问都最多跑k次 直接爽写 然而没有想到$5e3 \times5e3 MLE$了

为啥今天明明挺清醒的 还没昨天打得好?

关于NOIP模拟赛Day2 $T1$、$T2$ 严重失分的检讨

在今天的noip模拟赛中，我的 $T1$、$T2$ 失分严重，累计失分达到一百，导致我没有达到预期分数线，这是巨大失误，虽然时间管理上有了些许进步，但是正确性却降低了。

$T1$ 思考了好一会，想出了并查集来维护连通块并且去求 mex ，但是在实际操作中我的排序顺序出现了巨大问题，导致了 $T1$ 的 30 分失分（由于错误的排序贪心，没有考虑到应该是小的操作排在前面，大的操作排在后面，反而用长度排的序）

$T2$ 在以为 $T1$ 成功的前提下去写，但是一会没想出来就开始红温，后面写了一个时间复杂度飞起的暴力，通过不断优化成功过了大样例（我不知道大样例又水又错），以为自己过了，所以去写 T3、T4 去了

$T3$ 一眼就看出左右无关，所以写了一个 $q \times n$ 的暴力所以完成得比较快，但是没有正解思路

$T4$ 一开始毫无思路可言，只能去写暴力，结果暴力一开始都不会写，被卡了十几分钟，最后还是写了dfs暴力，结果因为文件读写的名称错误直接零分！

今后我将以更高的标准要求自己，严格遵守训练赛和比赛的规则，把每一次训练当作提高能力的机会，力求通过真实的努力取得进步。

跟一张也表现了我心情的图

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

我非常检讨T1挂分非常多这件事。

我在赛上刚拿到题没啥思路，直到看到数据范围$n\le10^3$，于是在大概开赛30min内想到T1的并查集 + mex做法，开始写。很快写出来一份带权并查集的代码（正确性未知），然后不知道咋用，于是就去看T2。

T2直接把并查集复制过去用，再写了一个bfs，非常愉快地拿下！

回来写T1。想了一下不需要带权并查集，于是写了一个假的拓展域并查集，但是跑大样例完全在说梦话，于是气笑了，改了一版又一版，最后 $\color{cyan}优化掉了并查集$ ，然后开心地 $\color{cyan}过掉了大样例$，本来想对拍一下，结果 $\color{cyan}不会写暴力$，然后就去写后面的题了。

现在看来太瓜了，写了并查集没用，如果写了暴力应该一下就拍出来问题了。