ኣዝዩ ከቢድ እዩ።

· · 个人记录

CTT 2020 vp

https://qoj.ac/category/94

Day 1

A. 术树数

复盘

刚开始开这个题有点吓人。但是做过用环去异或路径的套路话这个题应该会非常简单。但是没写过 K 进制异或线性基，所以编了一些时间。

题解

路径与环在模 K 意义下组合后的到的依然可以是一条合法的路径，证明直接考虑每次拼上一个环之后路径张啥样。

而图上所有环可以通过一来一回走一条边以及生成树上的仅由一条非树边构成的简单环组合出来，所以可以上一个 K 进制异或线性基就解决了。

时间复杂度 O(Qm^2)。

B. 树数术

复盘

一个不知道好不好的习惯是看到这种东西上来就先想根号分治。

大于根号可以 O(n)。但是发现小于根号的时候好像没有啥特别有用的性质。

后来发现其实因为是静态的，把线段树上每个节点的状态处理出来一下之后可以直接做了。

题解

线段树上处理每个区间 [l,r] 中满足 b_i=\text{lca}_{[j,i-1]} 的点集 A 以及 t=\text{lca}_{[l,r]}。

发现合并区间只需要用左区间的 t 在右边区间的点集 A 上二分第一个满足 A_i 是 t 的祖先，然后把 A_i 后面的都合并过来就行了。查询因为不需要求点集 A 所以也可以对每个区间二分。

配合 O(n\log n)-O(1) 求 LCA，时间复杂度 O((n+q)\log ^2n)。

实际上应该根本没必要求每个点集 A，上楼房重建状物感觉完全是可以做到能动态维护的。

C. 述树术

有点彩币，好像没想到有分的做法。待补。

Summary

还是菜在构造交互通信一类问题上。 ## Day 2 ### A. 爬楼梯 #### 复盘 有点不是很有意思的签到题，分情况讨论一下。 #### 题解 分析完发现情况只有 $4$ 种，每种情况都只需要用到主席树求前 $k$ 大。 ### B. 随机游走 #### 复盘 唉呀，积分。会不了一点，后来推了一下发现不是特别难。 #### 题解 先转切比雪夫距离，之后两维独立。 接下来是一个一维随机游走状物，容斥之后推推式子就做完了。 ### C. 基础图论练习题 #### 复盘 感觉这个题也很签到。 #### 题解 考虑兰道定理，即将点按入度排序后，SCC 个数为满足前 $k$ 个点入度等于 $k\times(k-1)/2$ 的 $k$ 的个数。 发现反转一条边对入度序列的影响形如区间加减 $1$ 状物。直接维护所有情况下前缀合法的 $k$ 的个数就行了。 时间复杂度 $O(n^2)$。 ### Summary $100+100+100=300$。 很有感觉。 ## Day 3 ### A. 计数鸡 #### 复盘 场上看完题就知道是求行列式了。 #### 题解 求这个东西是偶数，直接变成偶数减奇数，这样就可以考虑每个 $1$ 变成 $-1$ 了。 $[p_i>p_j]$ 是行列式，后面的东西只是在矩阵某些位置上乘 $1$ 或 $-1$。 所以直接求行列式就做完了。 时间复杂度 $O(n^3)$。 ### B. Perotation #### 复盘 很快就猜到了 $60$ 分暴力的结论。接着看到数据范围和时限很自然的考虑根号做法，就会了。 还是写了有点久的 #### 题解 首先有结论，一个序列合法当且仅当每个数的后面有偶数个数小于它。不太会证明必要性。充分性可以构造。 然后考虑用分块维护操作。 交换两个数只会对中间的数有影响，并且影响的是一个值域后缀。所以考虑维护每个块的值排序后的差分数组，另外还需要支持查询某个位置后面有多少个数小于它的信息。每次整块暴力散块重构，重构的时候因为只修改了 $O(1)$ 位置的信息所以不需要重新排序。 所以时间复杂度是 $O(q(B+\frac{n}{B}\log n))$，取 $B=\sqrt{n\log n}$ 得到时间复杂度为 $O(q\sqrt{n\log n})$。 ### C. 树特卡克林 #### 复盘 场上 40 分都没写完，30 分暴力调了好久害得。 #### 题解 待补。 ### Summary $100+100+30=230$。 好像非常正常的分数。 ## Day 4 ### A. 杏仁 #### 复盘/题解 先来个简单 dp，然后子集卷积 exp 板子题。 但是我写了个 $O(3^n)$ 操过去了。 ### B. 甩锅 #### 复盘 可以用矩阵树定理，转化成求循环矩阵行列式。 好像接下来不会做了，有点难！ #### 题解 ![](https://userpic.codeforces.org/326687/title/e81120556d61f1db.jpg) 所以 FFT/NTT 一遍之后把得到的序列乘起来就是答案。 ### C. 同构判定鸡 #### 复盘 没有什么好的想法，最后写了个随机。 #### 题解 待补，不会。 ### Summary $100+60+39=199$。 挺正常的分数。 ## 结语 这四场打的，应该来说都非常不错。前三场每场都有 DS 题的体验非常良好。 另外一件很有趣的事是我发现这几场很多题的部分分分布是 10+20+30+40。 --- ## CTT 2019 vp [https://qoj.ac/category/102](https://qoj.ac/category/102) ## Day 4 ### A.xor 太抽象了，写了个 $O(D \log D \log n\times E)$ 的东西，$E$ 是将近 $\log$ 的一个常数。大概是边数位 dp 边 NTT 卷积转移。卡了卡常过了。 ### B.N 门问题 呵呵。 首先写个比较帅气的暴搜，维护每扇门的概率以及是否有车以及目前选手选了什么门。 枚举一个门打开算答案取 min 就行，具体地，打开一扇门会将这扇门的权重平均分配到剩下不被选手选中的门上，然后选手会随机挑选一个最大的权重的门选中。 $n>10$ 跑出来全是 $0$。然后最抽象的是 excrt 求个 $n$。