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 于是误以为复杂度是 Θ(nloglogn)\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∑anxn，如果是有限项相加，则称为多项式。记错 F(x)=∑i=0naixiF(x) = \sum_{i = 0}^n a_i x^iF(x)=∑i=0naixi，其中 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(...
洛谷 P7922 [Kubic] Pyramid 题解
题目链接
给定一个初始长度为 nnn 的序列 ppp。
设当前 ppp 的长度为 LLL，有以下两种操作：
A 操作先构造长度为 L−1L-1L−1 的序列 p′p'p′ 满足 pi′=min{pi,pi+1},i∈[1,L)p_i'=\min\{p_i,p_{i+1}\},i\in [1,L)pi′=min{pi,pi+1},i∈[1,L)。然后用 p′p'p′ 代替 ppp。
B 操作先构造长度为 L−1L-1L−1 的序列 p′p'p′ 满足 pi′=max{pi,pi+1},i∈[1,L)p_i'=\max\{p_i,p_{i+1}\},i\in [1,L)pi′=max{pi,pi+1},i∈[1,L)。然后用 p′p'p′ 代替 ppp。
再给定一个长度为 mmm 的序列 aaa，表示一共进行 mmm 组操作，第 iii 组中先进行 aia_iai 次 A 操作，再进行 aia_iai 次 B 操作。保证 2∑ai=n...
符号与约定
在本文中：
字符串索引默认从 111 开始。
用 s[l,r]s_{[l, r]}s[l,r] 表示子串 slsl+1sl+2…srs_l s_{l + 1} s_{l + 2} \ldots s_rslsl+1sl+2…sr，特别地，当 [l,r]=∅[l, r] = \varnothing[l,r]=∅ 时表示空串。
用 pre(s,i)\mathrm{pre}(s, i)pre(s,i) 表示 s[1,i]s_{[1, i]}s[1,i]，suf(s,i)\mathrm{suf}(s, i)suf(s,i) 表示 s[i,∣s∣]s_{[i, |s|]}s[i,∣s∣]。
定义
对于一个字符串 sss，若正整数 i<∣s∣i<|s|i<∣s∣ 满足 pre(s,i)=suf(s,∣s∣−i+1)\mathrm{pre}(s, i) = \mathrm{suf}(s, |s| - i + 1)pre(s,i)=suf(s,∣s∣−i+1)，则称 pre(s,i)\mathrm{pre}(s, i)pre(s,i) 为 sss 的...
Legacy
TopCoder XorBoard
给定 H,W,R,C,SH, W, R, C, SH,W,R,C,S，给一个 H×WH \times WH×W 的网格，初始全为白色，每次可以选一列或选一行白变黑、黑变白，问行操作 RRR 次，列操作 LLL 次，最终黑色面积为 SSS 的方案数。两种操作不同当且仅当存在一行或一列被操作的次数不同。
枚举染了几行几列然后算方案数即可。
TopCoder ConversionMachine
给定两个字符集为 {a,b,c}\{\texttt{a},\texttt{b},\texttt{c}\}{a,b,c} 的字符串 s,ts, ts,t，每次操作可以对 sss 的某个位置的字符向后变一位，给出每个字符变成下一个字符的代价和最大代价问把 sss 变成 ttt 的方案数。
每个位置都是先还原后再进行若干组 a→b→c→a\texttt{a} \to \texttt{b} \to \texttt{c} \to \texttt{a}a→b→c→a 的轮换，所以可以确定总的操作次数上限，然后设 dpi,jdp _ {i, j}...