5.30 模拟赛赛后总结

赛时历程

AM7:00似乎是拿到题目了，今天比较清醒，有耐心看部分分，看到T1有点可做，于是并没有浏览全部题目，而是仔细看了看T1

结果40分钟构思好了前50分的各种暴力加性质分，也还行吧，计划8:30完成这50分。

先打\(n^2\)暴力，答案明明是对的(1000行粗略的看)，可是diff提示我\(WA\) ，害我看了半天，最后输出答案的和，感觉和ans的和都是一样的，出错的概率不大。

结果是打完\(n^2\) 暴力就已经快\(8:40\) 了，然后快速的实现性质分，对拍结束之后大概也是九点四十。

看T2，发现仍然有性质+暴力分的50，然后快速的打完，这个相对顺利，大概十点二十就结束了。

再看T3，感觉这个应该是最难的，中档分虽然到达了60，但是基础的性质+暴力缩紧成了30分。胡乱一搞就已经快11点了，11点二十就收卷了，感觉没什么可以做的了，大概检查检查吧。

看这个题的难度大概是提高组的，预期得分130，感觉水平进步也不是那么大。。要说的话就是打的比以前快了，旁边jyh，zzm，zyz三人都是要AK的势头。

技术总结

1 挂分。T1的50->25 ，T3的30->15,原因分别是询问的w和边权d看反，所以对这个性质的考虑有差别；数组开小。最终只有90，倒数第三。

2 发现我的能力水平(思考+代码实现能力)相较于打省选时或者说打省选前提升并不大，即这几个月来能力提升太少，原因大概有两点:独立思考与独立代码实现的题目较少；还有就是经典的效率低。

3 虽然打部分分的速度快了(毕竟也比较简单)，但是像这种NOIP水平的题目，对于正解竟没有一点思路，还是基础差了，像T1的整除分块以及树上差分(虽然部分分里也有类似的差分)，T2的建立并求解同余方程组（好久没做过数论已经呆了），T3的结论性 trie树优化DP(并不是我直觉思考的方向)，并不是很难的知识点，都是有人现场就有完整思路的，题做得太少了，思考的太少了,都不会。

5.31 UPD-今天起总结一下题目知识:

T1 整除分块计算贡献,将每个边能够贡献到答案的所有w做成一个区间，然后每次针对整除答案相同的区间更新这些w(出了子树之后回退)，将询问分成3个，挂在每个子树上，每次针对单点查询，在\(u，v\) 上的系数放1，\(lca\) 的系数是\(-2\) ，然后每次针对询问的w在当前的数据结构里单点查询乘上系数放到对应id的ans中，相当于做了树上差分。主要的两点,一个是整除分块，一个是树上差分。

T3 首先是一个结论性的东西:一个序列排序之后，最小的\(a_i \ xor \ a_j\) 一定是相邻的两个数。证明大概是考虑\(a<b<c\) 在trie树上的异或，首先\(dep[lca(a,b)]>=dep[lca(a,c)]\&\&dep[lca(b,c)]>=dep[lca(a,c)]\),其中\(lca(a,b)\)表示a,b之间第一个分歧点的父亲，所以说异或起来,由于\(a,c\)之间的lca比较浅，也就是最高位分歧点较大，因此没有相邻的优秀，即 a xor c>=a xor b && a xor c>= b xor c ​ 。得到这个结论之后，设\(f[i]\)是最后一个选i的序列的个数

，那么最终答案就是\(\sum f[i]\) 而\(f[i]=1+\sum\limits_{X\le a_i\ xor\ a_j}f[j]\) 。考虑对于一个\(a_i\)直接找到所有与它异或值大于等于X的点，在查询的时候，寻找一个路径a使得\(a_i\ xor\ a=x\),在这个过程中，对于这一位X是1的，要走向\(a_i\) 这一位的相反方向，如果X这一位是0，那么走向相同方向，走到相同方向之前，统计一下走相反方向(即异或等于1)的这个子树的答案(因为这一位如果它们异或起来一定是大于X的)，到达终点的时候再加上选择a这个值的答案，之后插入\(a_i\)到trie中，每个点上的值就是\(f[i]\)，供给后边统计用。这样异或的过程保证了从高到低，对于某一位上能够异或大于\(X\) 的值会直接被全部统计到，然后不会再管它们，继续考虑更低位，最后再考虑等于X的情况。 这道题给我复习了一波trie树(所以说字符串相关学的是真烂啊！！！(虽然trie属于数据结构的范畴))，也让我体会了一番trie树异或统计的操作（提高组知识点QwQ）。

T2 应该才是最难的。搞了一晚上最后是数组开小调了一个多小时 。首先T2容易发现每次变换中，得到的结果和位置编号有关系，发现可以在原序列中找到若干循环节，考虑初始状态到最终状态一定是位置编号在轮换，那么可以认为问题变成了针对若干轮换，求\(a_i≡x(mod\ loop_i)\),其中\(a_i\)表示从初态到末态的操作次数，而\(loop_i\) 则代表一个轮换的最小循环节，那么求出来\(a_i\)和\(loop_i\) 之后就可以用扩展中国剩余定理解决问题了。然后难的地方又在怎么求\(a_i\) 和\(loop_i\), 求\(loop_i\) 可以采用KMP的算法，预处理出来轮换之后，针对每个轮换的环当成一个串，求出末尾的nxt数组，有一个结论是如果\(len\%(len-nxt[len])==0\),那么最小循环节的长度就是\(len-nxt[len]\),蓝书在字符串讲KMP的例题【period】的时候证明过这个结论，这样就解决了\(loop_i\)的问题；接着考虑操作次数\(a_i\),有一个办法是找出最小循环元的最小表示，然后察看两个状态的偏移量，偏移量的差就是初态到达末态的操作次数(次数位负数要加\(loop_i\))，然后我就学了一波最小表示法。这道题难的倒不是思想，而是实现的细节，尤其对于我这字符串学的烂的，求\(loop_i\)和\(a_i\)都是困难重重(都现学)。

题目总结完毕！！

以下似乎和今天的模拟赛没有直接关系。

4 以上算是指出问题，指出问题也得有解决问题的办法，这样才是有用的，虽然先前也类似的指出过问题，也大概有一些解决问题的想法，但是往往付出的行动是不够的，想来还是因为懒惰和在真正要实践的时候有些逃避，导致时间就浪费掉了，现在距离NOI只剩下55天(5/30~7/24)，考虑到时间的紧迫，该面对的问题，该解决的知识点缺陷不能总是放着。

5 讲讲细节，做题方面，避免在看题目/思考题目时间歇性放弃走神胡思乱想；避免不会做没思路硬照题解代码写，决定做这道题就一定要想明白，无法明白就果断放掉，硬写就是浪费时间；比赛时能拿的分一定要努力拿，实现的速度要快(今天T1太慢了)。心态/日常方面，避免无端自闭浪费时间(有端也不大行)；避免胡言乱语互吹互膜打断思路；少看无关网页分散注意力，占用脑容量；回寝，如果不看书迅速睡；回家之后老想熬夜娱乐，大概是比较珍惜当日的原因，不想到第二天，想来对于明天有一个前瞻性的规划，有一份期待的话应该能增长自己睡觉的欲望(赶快到明天吧(类似期待明天旅游这样的心情))，也能让明天起床的时候有动力，回忆起昨晚想好的目标就会多些干劲，比如明天我要打CF争取A掉4道题，计算几何要再看一个视频然后写完相应的题目；放松是需要的，否则脑袋会短路，目前来看打球是个好选择。

6 要说到做到。

更无关的内容

回家的时候在知乎上看到一个这样的问题“上清北真的可以改变一生吗？”，有一个前北大学生回答中，这段的这种表达(褒义)让我笑了出来，感觉有些心态上的启发。

有的知友问，如何保持乐呵的心态？我想说的是，良好的心态来自对自己的正确的认知。这种认知受到原生家庭的影响，也受到后天学习调整的改造，这两种力量一直在抗衡。这就是我们受教育的意义，即：让自己的人格更独立，成为一个完整的人，接纳自己的优点缺点。大白话就是，别把自己太当回事儿，增强钝感能力，太敏感会消耗很多能量，牵扯太多时间和精力，影响自己的健康发展。他强任他强，清风拂山岗；他横由他横，明月照大江。保持冷静，搞清楚自己想要的是什么，自然容易乐呵。自己掌握自己的节奏，一旦被别人带节奏，人没法乐呵，因为你缺失掌控感。