C - Harmonic Mean 题意 要求构造一个长度为 nnn 的一个数组 aaa，满足以下条件： ∑i=1n1ai=1\sum\limits_{i=1}^n\dfrac{1}{a_i}=1i=1∑n​ai​1​=1 aaa 中的元素各不相同 1≤ai≤1091\leq a_i\leq 10^91≤ai​≤109 题解 利用 1k(k+1)=1k−1k+1\dfrac{1}{k(k+1)

G - Minimum Xor Pair Query 题意 给出一个初始为空的可重集合和三种操作。 插入一个数； 删除一个数； 输出集合内任取两数异或的最小值。 题解 一个重要的性质是：若 x<y<zx<y<zx<y<z，则 min⁡(x⊕y,y⊕z)<x⊕z\min(x\oplus y,y\oplus z)<x\oplus zmin(x⊕y,y

C - Mex Game on Tree 题意 给出一棵树，其中一些点标有数字。Alice和Bob轮流给剩下的点标数字，如果最终有一棵子树的所有结点 mex\mathrm{mex}mex 为 kkk，则Alice胜，否则Bob胜。要求判断两人最优操作下谁能获胜。 题解 很直观的想法是Bob每次操作都会填入 kkk，而若一棵子树中存在一个结点数字为 kkk，那么这棵子树的 mex\mathrm{me

点分治 点分治常用于解决树上路径统计问题。它的基本思路是：选定某个点 uuu，将路径划分为经过 uuu 和不经过 uuu 两类。对于前一种，我们直接处理。对于后一种，我们递归，在子树中处理。 首先要解决的是递归的层数，考虑一条链，如果从链的一端开始，每次向子结点递归，那么递归层数是 O(n)O(n)O(n) 的。解决方法是每次选取重心进行递归：即先处理整棵树的重心，然后递归处理每棵子树的重心。这样

D. Rating System 题意 给出一个得分序列。可以设定一个 kkk，使得分数到达 kkk 后不会再低于 kkk。求一个 kkk 使得最终得分最大。 题解 显然 kkk 应该为得分序列前缀和中的一个。对于给定的 k=sumik=sum_ik=sumi​，必然存在一个位置 j∈[i,n]j\in[i,n]j∈[i,n]，使得从该位置往后得分不再小于 kkk。所以我们直接维护后缀最大值即可（

E. Tenzing and Triangle 题意 在网格图 0≤x,y,x+y<k0\leq x,y,x+y< k0≤x,y,x+y<k 范围内有一些格点，每个点有点权。每次可以以 x+y=kx+y=kx+y=k 为斜边，圈定一个等腰直角三角形，消除范围内的点的点权，代价为 AAA 乘直角边长。也可以以某点点权为代价，消除该点。 问消除所有点的最小代价。 题解 我们用斜边表示

C - Dyed by Majority (Odd Tree) 题意 给定一棵树，保证每个点的度数都是奇数。对树上的结点进行黑白染色。现给出目标颜色序列，要求找到一个初始颜色序列，使得经一次操作后得到目标颜色序列。 操作定义为：对每个结点，记目标颜色为与它相邻的结点中超过半数所具有的颜色。将所有结点的颜色同时修改为目标颜色。 题解 从特殊情况入手。考虑叶子结点和它的父亲。显然，具有相同父亲的叶子结

123456789101112131415161718192021222324int cnt,nxt[maxn][26];bool exist[maxn];void insert(string s,int l){ int p=0; for(int i=0;i<l;i++) { int c=s[i]-'a';

F2. Omsk Metro (hard version) 题意 给定一棵树，每个点有点权 111 或 −1-1−1。每次询问两点，问两点的路径上是否存在一个子段其和恰为 kkk。 题解 不难发现，对于给定两点，符合条件的 kkk 当且仅当它介于路径上最小子段和和最大子段和之间。所以，问题就转变成了维护最大子段和和最小子段和。这个问题在序列上是容易的，记录下区间前缀最值、后缀最值和区间和，用线段树

G - Return to 1 题意 给定一张有向图，从 111 出发，每步从当前位置走向一个相邻的结点。问是否存在一种走法，使得 101010010^{10^{100}}1010100 步后回到了 111。 题解 首先，我们只关心那些能从 111 走到并且能走到 111 的点。令所有包含 111 的回路长度构成的集合为 LLL。令 GGG 为这些回路长度的 gcd⁡\gcdgcd。原问题有解当且