PKUWC Day 1 早上 7:40 起床，爽睡了。 路上 wc 跟我说只有我没到了，仔细一问原来我听错集合时间了，这下爆蛋了。最后迟了大概 7 分钟才到。 报道完在边上随机游走，cyf 带着 zxx 来和 zyz 面基，我在旁边有点尴尬就偷偷润了。 在报道厅里面到了那老师和 Meatherm。还收到了 Mea 的徽章。大家都好帅啊。 开幕式没啥好说的。午饭还行，不是绍一食堂承包，应该没有卫生问题。 吃完饭回报告厅开了一会 Phigros，然后背了下板子，没记住。 进考场试机，配了下 VSCode。看眼试机题，怎么是我玉玉症题，skip。第二题不会做，懒得想了，默写了一下 NTT。 开始之后先看 T1，感觉不太会做。看眼 T2，数据结构。再看 T3，看着好眼熟，但是没啥想法。 继续做 T1，没啥想法，先猜了个 a>b+1a > b + 1a>b+1 的结论，交上去发现假了，有点急。仔细想了一下，发现本质上是构造一个 a+ba + ba+b 个点的图使得最大独立集只有 a−1a - 1a−1。 这数据范围铁 O(T(a+b)+(a+b)2)O(T(a + ...

对于一些算法，如果我们可以将其视作对一个向量的若干线性变换，则称这种算法为线性算法。 具体地，我们可以将算法过程中维护的变量写成一个向量 v⃗\vec{v}v，然后如果对这些变量的操作都是在向量上的线性变换，那么这就是一个线性算法。 把线性变换写作一个矩阵 AAA，就可以将该算法表示为矩阵与向量的乘法 A×v⃗A \times \vec{v}A×v。 我们称 ATv⃗A^T \vec{v}ATv 为这个算法的转置算法。 但是我们显然不能把矩阵 AAA 给直接写出来，因此需要考虑如何快速得到转置算法。 首先把矩阵 AAA 拆成若干个初等矩阵相乘的形式：A=BkBk−1…B1A = B_k B_{k - 1} \ldots B_1A=Bk​Bk−1​…B1​，于是就有： BkBk−1…B1v⃗=B1TB2T…BkTv⃗B_k B_{k - 1} \ldots B_1 \vec{v} = B_1^T B_2^T \ldots B_k^T \vec{v}Bk​Bk−1​…B1​v=B1T​B2T​…BkT​v 这样就相当于把所有初等变换的顺序倒过来然后把每个初等变换转置一下，于是我们只需...

从 k 总那里搞到了个名额，CSP 是爆蛋了，还是看看远处的南京站吧。 Day -? 发了参赛手册，看了几眼，发现有很多 sxyz 毕业选手 & 发现左边是 nfls 队伍，害怕。 Day 0 早上去 sxyz 接 pi 老师，然后上高铁去南京。高铁上和队友练了会兵。 排队签到的时候看到了赤橙黄绿青蓝紫。 排完肚子饿死了，就先去吃了个饭，吃完被告知还要去领 kkk 的衣服…… 等衣服领完去领集赞的奖品就只剩暖手宝了…… 然后把 kkk 的衣服交给 panda，顺便拿了 hydro 的徽章，然后去食堂找了 zjc。 下午开幕式发现座位比较阴间，主席台方向屁也看不到。 热身赛队友慢速过了 B，然后我慢速过了 C，然后发现 E 是之前 VP 过的去年南京站，光速写了一下，过掉之后队友说 AD 都会完了，我直接开摆！ 然后去看了下 zjc、zqy 和 yk，回来队友告诉我 A 题做法假了？我看了下大概胡了个每次从一个点追另一个点，然后等队友把 D 写完，最后 D 也没过…… 其实还去远远地偷看了一下 szm & sk & madoka 队，但是因为社恐所以瞄了...

CSP-S 初赛 Day -2 晚上做了下 23 年的卷子，做得有点 yyz，最后 85.5 分。好像也不是很爆。 Day 1 上午不想偷学，开了一上午 chess。 中午吃完饭看了眼 J 组的题，好像全是唐题。 下午带着唐龙玩偶去找 zyz。 面到了诸暨的故人 & Binary。 然后随便聊了聊就进考场了。 发现我们考场有至少 7 个我认识的人…… 卷子发下来就直接从前往后做，发现有欧拉图题，乐了。 第 10 题看也看不懂题是啥意思，但是注意到 α\alphaα 可以取到 111，所以直接排除掉 C 选了个 D。 做完 15 题看了眼表，不小心以为两点开始然后以为已经过去 40min 了，几把吓断。 阅读程序 1，把 ~ 当成了 -，爆蛋。 阅读程序 3 没太看懂 solve() 在干嘛，然后瞟到了第 30 题，看懂了。然而没有注意到有个 sort 于是误以为复杂度是 Θ(nlog⁡log⁡n)\Theta(n \log \log n)Θ(nloglogn)，但是题里写的是大 OOO，于是误打误撞选对了。 完善 1 简单题，做完发现我怎么全选 A，但是不管先做 ...

前言 会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。 CF925F Parametric Circulation [!++] 考虑无源汇上下界可行流是怎么求的，是对所有 fi>0f_i > 0fi​>0 的点向汇点连容量为 fif_ifi​ 的边，fi<0f_i < 0fi​<0 的点从源点连容量为 −fi-f_i−fi​ 的边，然后流满就是有解。 考虑最大流等于最小割，而每种割的方案都是关于 ttt 的一次函数，因此最大流是下凸壳，而满流的大小是一个一次函数，因此有解即满流大小等于最小割大小的位置是一段连续的区间，于是就可以三分了。 为了避免实数问题，可以将所有参数都乘上 10710^7107。 CF542E Playing on Graph [!+] 对于连通图： 注意到奇环无论怎么操作都会变成一个更小的奇环，因此存在奇环则无解。 剩下的就是二分图。 答案至少可以是直径，因为从一个点 ...

前言 会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。 QOJ6345 Random Interactive Convex Hull Bot [**+] 考虑增量构造，每次加入一个点 iii 时，任意选凸包上的一个点 sss，找到距他凸包大小一半的点 ttt，询问 (s,t,i)(s, t, i)(s,t,i) 即可得到 iii 在直线 ststst 的哪一边，然后将 sss 和这边的凸包上的点连线将这个半平面划分成若干部分，此时可以二分出 iii 在哪一部分。 之后直接把 iii 两侧要删掉的点弹弹掉就好了。 CFgym104065B Call Me Call Me（2022 CCPC 绵阳） 考虑所有区间都有交怎么做。 那按交把整个序列划分成两部分，对于每一部分把每个区间按端点排序（右半部分按右端点从小到大排序，左半部分按左端点从大到小排序），然后对于每一半的每个元素给他一个 k/2k / 2k/2 的权值，每次更新就是...

赛时指赛时我过了这题或者嘴巴掉了，赛后指赛后补了或者嘴巴了。 第一场 B 星星（赛时） 就直接暴力 DP。 F 序列立方（赛时） 考虑立方的组合意义，即任意选三个子序列，使得它们相等的方案数。 dpi,j,kdp_{i, j, k}dpi,j,k​ 表示三个子序列末尾分别在 i,j,ki, j, ki,j,k 的方案数，这样不好转移，改成三个指针，每次选一个指针向后移一格或选择这三个指针上的数插到子序列末尾，为了避免数重钦定先移好第一个再移好第二个再移第三个即可。 D 传送（赛时） 线段树分治然后用并查集维护，每次相当于是要给一个集合加上某个权值。 给每个点打个 tag，令一个点的权值为其到根的所有祖先的 tag 之和。 设是把 xxx 合并到 yyy，若要给 xxx 子树加上 vvv，则 tagx←tagx+vtag_x \gets tag_x + vtagx​←tagx​+v。若要给 yyy 子树加上 vvv，则 tagy←tagy+v,tagx←tagx−vtag_y \gets tag_y + v, tag_x \gets tag_x - vtagy​←tagy​...

前言 会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。 洛谷 P8004 Welcome to Lunatic City [!!*] 大胆猜想只要度数和原树一样的树都能构造出来。考虑构造证明，给每条边都放两个传送门，这样每条边都被切成了两部分，分别连着两个端点，然后对于新树上的每条边，在两个端点各取一条，将传送门匹配起来即可。 然后考虑计算答案。 考虑在答案树上所有关键点及其祖先形成的含根的连通块，其中的非关键点一定是度数最大的一个前缀。枚举这个前缀，显然将其与关键点合并后从大到小加点最优。暴力 check 就是 O(n2)O(n^2)O(n2) 的。 考虑优化，首先枚举前缀的过程中维护树的形态，然后 check 的时候只需要插入剩余的关键点。然后每次不是插一个点而是改成插一层点，这样对于度数大于 222 的点，每次都会插入两倍的点，然后只剩下度数小于等于 222 的情况，可以方便地 O(1)O(1)O(1) check，然后就...

前言 会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。 CF1610I Mashtali vs AtCoder [**] tags: 博弈论\verb|tags: 博弈论|tags: 博弈论 Green-Hackenbush：给定一张无向图，有一个根，两个人轮流操作，每次删掉一条边，然后删掉与根不连通的连通块，无法操作者输。 当图是树时即 AGC017D。结论为： SG(u)=xorv∈son(u)(SG(v)+1)SG(u) = \mathop{\mathrm{xor}}\limits_{v \in \mathrm{son}(u)} (SG(v) + 1) SG(u)=v∈son(u)xor​(SG(v)+1) 回到原问题：当有多个根时，可以把这些根缩成一个点。 Fusion Principle：在 Green-Hackenbush 中，可以把一个偶环缩成一个点，把一个奇环缩成一个点下面再挂一个点，原本环外连向环上的边都连...

基本概念 对于求和式 ∑anxn\sum a_n x^n∑an​xn，如果是有限项相加，则称为多项式。记错 F(x)=∑i=0naixiF(x) = \sum_{i = 0}^n a_i x^iF(x)=∑i=0n​ai​xi，其中 aia_iai​ 称为该多项式的 iii 次项系数，记作 [xi]F(x)[x^i]F(x)[xi]F(x)，有时也用 F[i]F[i]F[i] 表示。 定义两个多项式的 ⊕\oplus⊕ 运算卷积为： [xn](F×G)(x)=∑i⊕j=n[xi]F(x)[xj]G(x)[x^n](F \times G)(x) = \sum\limits_{i \oplus j = n} [x^i]F(x)[x^j]G(x) [xn](F×G)(x)=i⊕j=n∑​[xi]F(x)[xj]G(x) 以下提到卷积一般指加法卷积。 FFT 多项式的点值表达：只需要 n+1n + 1n+1 个点值就可以唯一确定一个最高 nnn 次多项式。 两个多项式卷积就对应点值相乘。也就是对于任意 xxx，(F×G)(x)=F(x)G(x)(F \times G)(x) = F(...