十连测寄

· · 个人记录

Day 1

T1，考场没细想，直接上的暴力线段树。考后才知道维护单调性就过了，十分好写就过了。但我加了点卡常也过了。有人写线段树卡成 80pts，不好评价。

T2，见过处理方式类似的题。注意到 d_u+d_v-d_{lca}\times2。奇偶性之和 d_u,d_v 有关。乱搞一下，并查集维护一下正反集。

T3，想不出来 dp，写得记搜，但不知道为啥挂了。同过维护 A,B 两台机器的时间差来优化状态。注意如果要在晚的机器上继续加任务，时间差不是 j+t，是 t。因为要等加的任务上去了，另一台机器才能开始工作。考试就卡在这了，菜！

T4，结论猜假了，循环节实际是 lcm(n,m)。k 很大，倍增解决。

Day 2

T1，计算出前缀和，排序一下。答案一定是临近值，取 \min 就行了。然后来计算区间最大长度，用一个 map 来存前缀等于 s 最先出现的位置。用 s_i+ans/s_i-ans 来更新即可。但不知道为啥最后一个点 f_error 了，重测又过了。

T2，一眼可以看出怎么做的题，但处理起来还有点费事。讨论二叉树左右子树确定编号，大小递归即可。

T3，连续两场比赛 dp 拿不了分，我冒号问号。实际通过转换可以转化为一类线段覆盖问题，wtcl。

T4，赞。套了个链表跑路了。实际上，考虑用树状数组来维护每个桶还能否被吃。然后先淘汰的一定是次数较小的。所以可以将桶排序。如果不能进行一轮了，就考虑可以进行到哪里。这个可以用树状数组上二分来维护。注意细节，我们二分到的位置是最大的小于 aim 的位置，然后加 1 即为 end。而不是最大的小于等于 aim 的位置。

这场 T2 写得比较慢，还是基础不太扎实。没有为后面的题留够时间。

Day 2.5

今天没有比赛，打得 COCI。前三道没什么说的，后面两道还算有趣。

Maja，初看以为是矩阵，复杂度也对得上，但死活推不出来。正解是 dp + 贪心。因为 k 远大于点数，所以一定会走重复路径。其次一定会在两个点形成周期往返。可以用调整法证明。这样 k->\min(k,n \times m)。

Sunčanje 。一个好写一些的写法是 cdq。考虑矩形 i 能覆盖 j 的充要条件。{i>j ,x2[i]>=x1[j]\ x1[i]<=x2[j],y2[i]>=y1[j]\ y1[i]<=y2[j]}。即后出现且横竖有交。有点类似偏序问题。我们先将每个矩形倒叙排序来满足 i>j。然后进行分治。对于 [l,mid] 我们将他以 x1 排序，[mid+1,r] 以 x2 排序。然后通过双指针来满足 x1[i]<=x2[j]。接着考虑剩下三个。因为 y 之间有交，可以线段树来维护。我们只关心这个区间有没有点的 x2 大于 x1 维护区间最大值 over。

Day 3

话说好像是简单场的最后一场。

T1，简单的贪心。将 r 小的 l 大的排在前面，后有坑满足就选。不知道大家为啥都挂成 50pts 了。

T2，颜色之间的转化的最小值可以跑一次 Floyed。然后枚举每个位置的颜色做个 dp 就好了。

T3，有点小水平的矩阵题。容易发现每次每个位置除了开头结尾都为做出两次贡献。即 now=pre+2 \times pre-w[1]-w[n]。维护 pre,w[1],w[2]。做矩阵快速幂就行了。然后考虑第二次，同样的方式，但 w[n] 改变了。这个东西同样可以矩阵做出来，结束了。

T4，好像每场比赛都有题会爆 0。假掉了，还以为能 AK。看其他人的代码学的一个便捷的方法。用 st 表来维护 gcd。然后数一个区间内 gcd 的个数，直接上vector就好了。

没压住情绪，前三道写完就有点飘了，（下次狠狠抽自己。