ptz 记录

问 $0$ 和 $\frac{n}{2}$ 然后知道在那一边，然后二分。

E. XorTree

记 $b_{u} = \oplus a_{i}$ ，等价于 $b_{u}$ 和 $b_{v}$ 异或 $x$ 。连边，连通块内 $\oplus b_{i}$ 不变，等价于最大化划分为异或和为 $0$ 的连通块个数。相同的可以直接两两一组。剩下的 $O (3^{15})$ 计算。

F. Antennas On Tree

等价于任意一个 $d_{u} = k \geq 3$ 的点，至少有 $k - 1$ 个儿子的子树有值。以一个 $d_{u} \geq 3$ 的点为根，可以保证子树外至少有一个。

H. Generalized Insertion Sort

Q4805 的构造部分对任意图的通解。

对于根节点挂多条链，在每条链的链底维护排好序的一部分，把根节点的值插入排序。如果根节点就是自己，就随便扔到一个链最后，当重新回到根的时候必然做完了这条链，多 $n$ 次。

从下往上扔叶子，在最下面的分叉之前，每条链独立。最多做 $lo g n$ 次。

J. Simple APSP Problem

两个相邻整行都没有障碍，则一定有上边点数乘下面点数的贡献，然后缩起来。剩下 $O (n^{2})$ 个点，bfs。

Petrozavodsk Summer 2019. Day 9. MEX Foundation Contest

A. The One Polynomial Man

$\frac{( 2 a + 3 b ) ^{2} + 5 a ^{2}}{( 3 a + b ) ^{2}} + \frac{( 2 a + 5 b ) ^{2} + 3 b ^{2}}{( 3 a + 2 b ) ^{2}}$ 这种东西没理由能维护。但是若 $(a, b)$ 成立， $(ka, kb)$ 也成立。

把 $0$ 判掉。若 $(i, 1)$ 可行，则累加 $\frac{a}{b} = i$ 的数量。求原根，转为离散对数，差卷积。

B. Alexey the Sage of The Six Paths

最大匹配等于最小点覆盖。

同时钦定

Petrozavodsk Summer 2020. Day 6. Korean Contest

A. Mango

判掉只有一个 $\text{\$ } $，然后判掉$ \text{$} $前的部分，$ k $可以和$ 60 $取 min 。处理出每层走到第$ i$ 个点时长多少，每层二分一下。

B. Koosaga’s Problem

随机异或哈希。找一棵生成树，非树边和对应的树边异或相同的权值。此时偶环异或和为 $0$ ，奇环要删一个。

D. Non-Decreasing Subarray Game

后手要最大化，会选 $l / r$ 中最大的。在 $[l, r]$ 中一个前缀选 $r$ ，后缀选 $l$ ，先手选交界左右最小化。可以二分出来。

E. Observer Game

判掉直接赢。如果图中存在两个不同的 $k \times k$ ，那会交替填完 $nm - 2 k^{2}$ 个格子。

F. Rhythm Game

满足四边形不等式。

注意应当是有 $j$ 个没选，选到 $i$ ，对 $i$ 有决策单调性。

其他的几种都不对，感觉纯乱猜。

Petrozavodsk Summer 2021. Day 4. Shanghai ICPC Camp 2021 Onsite Day 1 by PKU

A. Counting Pairs

卷一下 $d_{u} + d_{v}$ 的 $(u, v)$ 对，再特判有边的 $(u, v)$ 对。

B. Cactus

能删就删，最后剩下一些全是偶度数的仙人掌，此时不存在只有两个点的点双，使用操作二。

建圆方树，对于一个环，保留连向父亲的一对点不动，其余绕环黑白染色，删光黑点，能删掉除了这对点以外的整个环。从叶子开始删即可，最后一定能删光。

C. Permute

这不是 4th ucup stage 2 D 吗！要是早几周 vp 也不至于场上破防那么久了。

注意到 $1 0^{k}$ 模 $7$ 的循环节为 $6$ 。

感受一下，随机排列 $mod 7$ 的概率均等，就随便划分成 $3$ 段，再随便给一个顺序即可。

但是要特判掉有一个位置是 $1$ ，一个位置极大的情况，此时不一定随的出来。其余情况基本都有解。

F. Interval Shuffle

维护 $an s_{i}$ 。操作形如：求出区间 $[l, r]$ 的 $m x$ ，将 $i \in [l, r], a_{i} = m x$ 加 $1$ ，其余赋值为 $m x$ 。

beats 即可。

I. Directed Acyclic Graph

赛时：

在瓶颈循环处应当把数组的值缓存到局部变量！

按 $B = 64$ 对询问分块。ull 压操作 $i$ 会不会影响到 $u$ ，拓扑排序。

当计算每个点在这一块收到的贡献时，先找最后一位赋值操作，与一下找到赋值操作后的所有取 min 操作。给取 min 重编号再压，直接位运算找最大的。

Petrozavodsk Winter 2022. Day 6. ICPC Camp Day 1

A. Soccer Match

直接随机染色，直到异色边数量 $> \frac{m}{2}$ 。此时不断扔掉 $d e g_{u} \leq k$ 的点就能得到合法解。

关于复杂度，不懂。

B. Gachapon

首先 $f_{i, j}$ 表示前 $i$ 轮最大为 $j$ ， $f_{i, j} = (\sum_{k \leq j} f_{i - 1, k})^{t_{i}} - (\sum_{k < j} f_{i - 1, k})^{t_{i}}$ 。

枚举卡 $x$ ，求 $(\sum p_{i})^{\prod t_{i}}$ 种随机方案，合法且随出 $x$ 的期望。等价于合法且第 $i$ 步随出 $x$ 的概率之和，等价于合法且第 $1$ 步随出 $x$ 的概率乘 $\prod t_{i}$ 。设 $g_{i, j}$ 表示第一次随出 $x$ 的，前 $i$ 轮合法且最大卡 $j$ 的概率，从一个 $g_{i - 1}$ 和 $t_{i} - 1$ 个 $f_{i - 1}$ 转移。

转置一下。

C. Survey

对于一个人 $i$ ，如果有 $j$ 个可选，有 $\frac{j}{n}$ 的贡献。

每个权值都有一个贡献。 $f_{i, j}$ ，加入新权值 $k$ 可以要求不超过 $\frac{j}{i}$ 。

G. Trans

是 FWT 求的东西。

求 $\sum_{t 1 + \dots + t_{m} = n} 1$ 和 $\sum_{t 1 + \dots + t_{m} = n} \prod i^{t_{i}}$ 。

是 $(m - 1 n + m - 1)$ 和第二类斯特林数 $S (n + m, m)$ 。

第二个大概有一个组合意义解释。对于 $n + m$ 个两两不同的球分给 $m$ 个盒子的分法 $a_{i}$ ，如果 $a_{i}$ 是前缀最大值，就是 $m$ 个特殊球，剩下的 $n$ 个在 $1 \sim p re m x$ 中任选对应乘 $i$ 。

I. EIP1559

以 $a - b$ 维护 $max a$ 和 $max b$ 。

K. Surround the Cat

这种题见过一次就会了，只是还是要写半天挂若干发。

大概是，每两个 ban 一个。当猫跑到离边界差 $1$ 或者一些离边界差 $2$ 的危险位置的时候，才开始 ban 没 ban 的那个。

Petrozavodsk Winter 2023. Day 7: Gennady Korotkevich Contest 7

A. Classical A+B Problem

不妨 $a \geq b$ ，则 $a$ 至少有 $n$ 的位数减 $1$ 位，共 $20$ 种。python。

B. Classical Counting Problem

按 $a_{i}$ 降序。设 $x$ 为最小的 $i \in / S$ ， $y$ 为最大的 $i \in S$ ，要求 $a_{y} + m \geq a_{x}$ 。固定 $x, y$ 后要 $S$ 合法，设 $l_{i}$ 和 $r_{i}$ 表示要 $S$ 合法 $i$ 最少/最多能加几次，要求 $\sum l_{i} \leq m v \leq \sum r_{i}$ 。以 $r_{i}$ 为例， $r_{1} \sim r_{x - 1}$ 和 $r_{y} \sim r_{n}$ 都等于 $m$ ，对于 $i \in [x, y)$ ，若 $i \in S$ ， $r_{i} = m$ ，否则 $r_{i} = m + a_{y} - a_{i}$ 。