前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。
CF925F Parametric Circulation [!++]
考虑无源汇上下界可行流是怎么求的，是对所有 fi>0 的点向汇点连容量为 fi 的边，fi<0 的点从源点连容量为 −fi 的边，然后流满就是有解。
考虑最大流等于最小割，而每种割的方案都是关于 t 的一次函数，因此最大流是下凸壳，而满流的大小是一个一次函数，因此有解即满流大小等于最小割大小的位置是一段连续的区间，于是就可以三分了。
为了避免实数问题，可以将所有参数都乘上 107。
CF542E Playing on Graph [!+]
对于连通图：
注意到奇环无论怎么操作都会变成一个更小的奇环，因此存在奇环则无解。
剩下的就是二分图。
答案至少可以是直径，因为从一个点 bfs 后可以把同层的点缩起来。
上界也是直径，证明考虑归纳。
假设所有大小为 n 的图都满足条件，则对于大小为 n+1 的图：
- 图是树，显然答案是直径。
- 否则至少缩一次，答案就是缩一次后直径的最大值，显然不会超过原本的直径。
对于一般图答案就是每个连通块的答案加起来。
CF1906C [**]
考虑对于 n>3，只令 b3,3=1，这样就可以得到 a。然后构造答案就是先令 b 全为 1，设 (x,y) 为 a 中右下角的 1（即 (x,y) 右下方没有别的 1），然后当某个位置 (i,j) 不合法时修改 bi+x−1,j+y−1 即可。
对于 n=3，随机一个填法，有 21 的概率正确，期望 2 次。
洛谷 P7999 [WFOI - 01] 翻转序列（requese） [**]
显然 x 必须取奇数。
考虑插入排序，设当前复原的是 i，每次能跳 x 就跳 x，直到当前位置 p∈(i,i+x)。此时如果 p 与 i+x 奇偶性不同则可以直接跳到 i+x，否则就先跳到 p+x。
上述做法需要 i+2x−1≤n，也就是需要 2x 的空闲空间。考虑取 x 为小于等于 4n 的最大奇数，先复原后 2n，然后复原前 2n。对于后半部分，先跳到 i+x，再操作 [i,i+x],[i+1,i+x−1] 实现仅 i 与 i+x 的交换，然后将从 p 跳到 i+x 的操作逆序做一遍就复原了。
CF1889D Game of Stacks [++]
感觉很聪明的一道题。
把问题转化为每个点向栈顶元素的编号连边，然后就是每次走一条边并把这条边修改为栈中下一个元素，直到无路可走。
观察这个过程，发现环会走一圈绕回原点，因此可以直接将环消掉，然后环上每个点的边修改成栈中下一个元素。
因此一直消环直到只剩下若干个内向树就得到答案了。
ARC107E Mex Mat [**+]
IOID2T2 弱化版。
结论：对于位置 (i,j),i>4,j>4，有 ai,j=ai−1,j−1。
证明基于一个基本事实：除了题目钦定的第一行和第一列，不存在相邻两个元素值相同。
考虑这样一个 4×4 的矩阵：
??????????ac??bd
假设 a=d。
由于 a=b,a=c,a=d，因此 b=c。
??????ef?gab?hbd
f=b,h=b，因此 f=a∨f=d，且 h=a∨h=d。
假设 f=h=d，由于 e=f∧e=a,g=h∧g=a，因此 e=g=a，则 mex(e,g)=a=mex(b,b)=d，矛盾，因此有 f=a 或 h=a。
不妨令 f=a。
??????ea?gab?hbd
则有 mex(a,a)=b,mex(b,b)=d。可以推出 a=2,b=0,d=1。
??????e2?g20?h01
若 e=1，则有：
??20?212?020?h01
出现了不合法情况，矛盾，因此 e=0。
??21?20201200201
出现了不合法情况，矛盾，因此 a=d。
□
然后暴力求出前四行四列的情况就可以算答案了。
CEOI2023Day1T3 Balance [*+]
S=2k 显然提示分治构造。
考虑每个数在每列的出现次数是能算出来的，因此每次分成两半时只要让两边这个数的出现次数相差不超过 1 即可。
对于每一行如果一个数出现了超过 1 次，则可以两个两个放到两边，然后会剩下至多 1 个。剩下的问题就是每行每种数会出现至多 1 次的情况。
不妨先考虑更弱的 S=2 的情况。对于同一行要限制两个数不放到同一边。对于同一种数，可以将其两两配对，然后配对的两个限制不放到同一边。这是一个异或 2-SAT。我们对限制连边，显然是二分图，黑白染色即可。
回到原问题，将同一行连边改成同一行两两配对连边即可。
BalticOI2024Day1T2 Portal [++]
首先显然只需要考虑相对位置，因此所有传送门都减去其中某一个变成 n−1 个向量。
考虑只有 2 个向量时怎么做，答案是当向量线性相关时为无数种，否则就是两个向量围成的四边形的面积。
（图源据说是官方题解）
然后考虑更多向量的情况，我们发现将两个向量进行加减不会影响答案，也就是 a,b 和 a,a+b 和 a,a−b 的答案都是相同的。
因此考虑将其变成两个向量的情况，也就是维护两个向量，令其中一个为 (x,0)，每次加一个向量，通过向量加减将其也变成 (x′,0) 的形式，然后显然可以用 (gcd(x,x′),0) 来代替 (x,0) 和 (x′,0)。
COTS/CETS2023Day1T3 Trokuti [*+]
我草，这不 PR #10 T2 吗，咋一年前不会现在还是不会啊？
首先可以对 5 个点用 (35) 次询问然后高斯消元求出它们之间的边。
然后观察限制发现 3400≥3300=2100×99×32，因此我们考虑用 32 次询问问出一条边。
但是还是先别管这个限制，想想怎么把剩下的边问出来。方法是每次加一个点，然后每次选出已知的两个点 u,v 询问一下（因为 u,v 之间的边已知，因此以下不考虑这条边），如果答案为 0 或 2 就知道答案了，否则保留其中一个然后再选另外一个点，这样一直做直到问出 0 或 2，这样过程中的点就都知道了。但也有可能最后也没出现 0 或 2，此时我们发现过程中的点之间建成了“某两条边一个为 0 一个为 1”的关系，我们找到两条出现情况相同的边问一下就好了。
然后仔细分析一下，发现若有 p 的概率问出 1，则相当于有 p 的概率只确定一条边，1−p 的概率确定 2 条边，因此一次询问确定的边数期望为 2−p，而显然 p≤21，因此期望 ≥23！这样就刚好符合我们的要求了！
CEOI2022Day1T1 Abracadabra [!!++]
显然 t>n 时串就不会变了。
考虑归并的过程，发现每次放入一个数时，其之后所有比他小的数都会被放进去。因此对于两个序列都可以用前缀最大值划分成若干段，然后变成这些段的归并。
于是我们考虑按前缀最大值划分成若干段进行维护。由于归并会造成前面的段移到后面的情况，因此我们不对两部分分别维护，而是合并到一起，然后每次操作都是从中间断开然后进行归并。
我们发现划分完后的串是有序的，因此我们没有必要去归并，而是只维护连续段，这样顺序就可以直接根据段首的元素得到。
因此这个过程实际上就是每次把中间的段裂开，把它的后半部分再按前缀最大值划分然后加进去。
这个过程显然可以通过树状数组维护每个段首元素对应的段长度来实现。
同时容易发现每个断首只会被裂出来一次，因此总操作次数是 O(n) 的。
CEOI2022Day2T2 Measures [!!+]
首先可以二分。
设答案为 t，则最优一定是第一个人往左 t，之后每个人尽量向左移动。
设初始位置为 a1,a2,…,an，则最终位置 a1′=a1−t,ai′=max{ai−t,ai−1′+D}，如果某个时刻 ai+t<ai−1′+D 就寄了。
考虑其中任意一段区间 [l,r]，假设 al′=al−t，则 ar′≥al−t+(r−l)D，另外还有 ar′≤ar+t，因此 2t≥al−ar+(r−l)D。但是如果中间存在 ai′=ai−t 那这个下界就偏小了，但是这种情况会在 l=i 时被统计到。
因此根据上面这些分析，所有区间的 (al−ar+(r−l)D)/2 的最大值就是答案。
然后上面这个东西显然可以拆成 ∑i=lr−1ai−ai+1+D，然后对这个东西求最大子段和即可。对于修改，直接离线下来搞一搞就好了。
COTS/CETS2022Day1T1 Kraljice [***]
答辩构造。
注意到外面围若干圈对里面的点的贡献都是偶数，因此考虑从外向内放置。
构造方法大概是这样：
Q........................↓Q........Q...............↓Q....Q...Q...............↓Q....Q...Q.....Q.........↓Q....Q...Q.....Q...Q.....↓Q....Q...Q.....Q...Q.Q...↓QQ...Q...Q.....Q...Q.Q...↓QQ.Q.Q...Q.....Q...Q.Q...↓QQ.Q.Q...Q.....Q...Q.Q.Q.
这样一直下去，容易证明每一步都是合法的。
问题是边上填完之后剩下三个角都放不进去了。解决方法是先在内层右上角放一个。
QQQQ.Q...QQ...QQ...Q.QQQ.↓QQQQ.Q...QQ...QQQ..Q.QQQ.↓QQQQ.Q...QQ...QQQ..QQQQQ.↓QQQQ.Q...QQ...QQQ..QQQQQQ↓QQQQQQ...QQ...QQQ..QQQQQQ
然后发现本来的构造也是先在角上放一个，因此下一层对称一下即可。
然后对于奇数，需要特殊构造 3×3 的情况，具体方案样例中已经给出。
对于偶数，n=2 时答案为 1，但是当 n≥4 时可以构造出 n2−2 的解：
QQQ.Q..QQ..Q.QQ.↓QQQ.Q..QQQ.Q.QQ.↓QQQ.Q..QQQ.QQQQ.↓QQQ.Q.QQQQ.QQQQ.↓QQQ.Q.QQQQ.QQQQQ↓QQQ.Q.QQQQQQQQQQ
但是我不会证这是上界……总之这样就做完了。
COTS/CETS2022Day2T3 Točkice [++]
link.
ARC160F Count Sorted Arrays [!!]
应该是经典 Trick：判断一个串是否有序，等价于对于任意一个 k，令 <k 的为 0，≥k 的为 1，得到的串有序。
因此维护 01 串，只有 2n 种，然后记录操作完会有序的串。
对于每个串 S，向所有满足 TxorS=2k 的 T 连一条边，则答案就是从全 0 串到全 1 串的只经过被记录的串的路径数。
每次加一个串只更新他的超集，复杂度是 O(3nn)。对于每个 i,j(i<j) 维护第 i 位是 1 且第 j 位是 0 的串，每次操作只操作会修改的串，总复杂度就是 O(2nn2)。
CEOI2023Day2T1 Trade [!!]
令 w(l,r) 为区间 [l,r] 的贡献，则 w(l,r) 满足四边形不等式。
证明考虑区间 c 的和会被消去，记 w′(l,r) 为区间 s 的前 k 大的和，则变成证明 ∀a<b<c<d,w′(a,c)+w′(b,d)≥w′(a,d)+w′(b,c)，即证 ∀l<r,w′(l,r)+w′(l+1,r+1)≥w′(l,r+1)+w′(l+1,r)，然后稍微替换一下就能证了。
于是第一问直接分治解决，然后考虑第二问，对于每个 r 求出最优决策点中最靠右的那个 l，显然这个 l 是单调不降的，从左往右扫描 r 然后双指针 l 并统计过程中扫到的区间的答案。
为什么这样是对的呢，考虑 l1<l2<r2<r1 且 [l1,r1] 和 l2,r2 都是答案区间，显然可以舍去 [l1,r1] 而只统计剩下三个。则 [l1,r2] 和 [l2,r1] 也是答案区间，因此如果一个区间 [l,r] 没有被统计到，则存在 l′,r′ 满足 l<l′<r′<r 且 [l′,r′] 是答案区间，则会统计到 [l,r′] 和 [l′,r′] 和 [l′,r]。
