题意：给定 nnn 个点和 mmm 对偏序关系 ⟨u,v⟩\langle u,v\rangle⟨u,v⟩，构造最少的排列数目 kkk，使得在这 kkk 个排列中至少有一个排列满足 u<vu <vu<v。1≤n,m≤1061\le n,m \le 10^61≤n,m≤106。 解法：数据范围过于庞大意味着 kkk 必然不大。其实很容易发现一种任意情况下都成立的方案：k=2k=2k=2，一个排列是 {1,2,3,⋯ ,n}\{1,2,3,\cdots,n\}{1,2,3,⋯,n}，另一个排列是 {n,n−1,n−2,⋯ ,1}\{n,n-1,n-2,\cdots,1\}{n,n−...

题意：有一个 nnn 个点的树，第 iii 个点拥有的颜色种类由二进制数 cic_ici​ 定义。qqq 次询问，每次从 uuu 出发到 vvv，初始自选颜色，一秒的时间里可以移动到相邻同色节点（即该节点有自身的一种颜色），或者在一个点变换自身颜色（必须是这个点已经有的颜色）。问花费的最少时间。1≤n,q≤5×1051 \le n,q \le 5\times 10^51≤n,q≤5×105，0≤ci<2600 \le c_i < 2^{60}0≤ci​<260。 解法：一个贪心的想法是，能尽可能维持当前颜色不变就尽可能不变。因而首先处理出从当前节点 uuu 向上最多能不变色走...

题意：给定一个长度为 nnn 的序列 {a}i=1n\{a\}_{i=1}^n{a}i=1n​，一次操作可以选择两个不同的数字 aia_iai​ 和 aja_jaj​ 执行 ai←ai+1,aj←aj−1a_i \leftarrow a_i+1,a_j \leftarrow a_j-1ai​←ai​+1,aj​←aj​−1。问能不能有限次操作内让序列中每个数字都是质数。1≤n≤1031 \le n \le 10^31≤n≤103，1≤ai≤1091 \le a_i\le 10^91≤ai​≤109。 解法：当 n=1n=1n=1 时，显然和 sss 为质数才行。 当 n≥2n \ge 2n≥2...

题意：给定一个 n×mn\times mn×m 的字符矩阵 {S}(i,j)=(1,1)(n,m)\{S\}_{(i,j)=(1,1)}^{(n,m)}{S}(i,j)=(1,1)(n,m)​，定义一个 n×nn\times nn×n 的子矩阵是优美的当且仅当 ∀i,j∈[1,n]\forall i,j \in [1,n]∀i,j∈[1,n]，Si,j=Sn−i+1,n−j+1S_{i,j}=S_{n-i+1,n-j+1}Si,j​=Sn−i+1,n−j+1​。问 {S}\{S\}{S} 中有多少个优美的子矩阵。1≤n,m≤2×1031\le n,m \le 2\times 10^31≤n,m...

题意：给定两个十进制数 ，每次可以选择 十进制表达中的其中一位 ，然后执行 或 。问 最少经过多少次操作变成 。多次询问，，，强制在线。 解法：显然，每个点可以向外连出若干条边模拟一次操作。如果数字范围足够小那么是一个简单的全源最短路问题，但是本题数据范围较大，但是我们仍然需要这一建图的思想。 考虑固定枚举出中间某个特定的变化步骤，即取出一段长度为 的一段——因为一步操作至多使得 变化 。然后采用分治的思想： 定义起始数字 和结束数字 以及中间变化过程都在区间 ，考虑中间的 个数字 。这时可以考虑以 依次每个点跑单源最短路（bfs），求得每个点到 中每个点到其他点的正向（即...

题意：给定一张 G(n,m)G(n,m)G(n,m) 的有向图，使用 dfs 算法求解从 111 开始的单源最短路，问给定的图能否在任何边遍历顺序下都正确输出。1≤n,m≤1051 \le n,m\le 10^51≤n,m≤105。 解法：为什么我们要找支配树？可以考虑以下三个例子： 基本错误型：一个点（222）有多种到达方式。 一个环：多次遍历到的点不一定是有重复的。 破环：多种遍历方式会导致破环方式不同（如 6→46 \to 46→4，4→24 \to 24→2，5→35 \to 35→3），从而影响答案。 首先我们依然可以建立一个 bfs 树，找到从 111 出发到每个点的最短距离...

题意：给定一 n×nn\times nn×n 的 01 矩阵，每次可以翻转一行或一列，执行若干次操作。若将操作完成后的矩阵的每一行从做到右视为一个二进制数 {r}i=1n\{r\}_{i=1}^n{r}i=1n​，每一列从上到下视为 {c}i=1n\{c\}_{i=1}^n{c}i=1n​，要求 min⁡(ri)≥max⁡(ci)\min(r_i) \ge \max(c_i)min(ri​)≥max(ci​)，问是否可以实现，可以实现求最小操作次数。1≤n≤3001 \le n \le 3001≤n≤300。 解法：假设第一行有一个 111，则 max⁡(ci)≥2n−1\max(c_i) \...

题意：给定 nnn 表示有一个由 {1,2,3,⋯ ,2n}\{1,2,3,\cdots,2n\}{1,2,3,⋯,2n} 构成的 2n2n2n 张牌的初始牌堆，同时自己这里有一个空的牌堆。执行以下的操作： 翻开牌堆顶的一张牌，并放在自己牌堆的堆顶。 记自己牌堆堆顶的一张牌大小为 xxx。如果初始牌堆为空，结束。否则执行 333 操作。 若 x≤nx \le nx≤n，则猜测初始牌堆翻出的下一张牌 yyy 比 xxx 大，否则猜测翻出来的下一张牌比 xxx 小。这时翻开初始牌堆的堆顶，并将这一张牌放在自己的牌堆的堆顶。如果猜测正确，则跳转到 222 操作，否则结束游戏。 问对于 (2n)!...

G Steins’ Game 2 题意：有 nnn 堆石子 {an}\{a_n\}{an​}，满足 0≤a1≤a2⋯≤an≤m0 \leq a_1 \leq a_2\cdots \leq a_n \leq m0≤a1​≤a2​⋯≤an​≤m。Alice 与 Bob 依次从非空的一堆拿走正数个石子使得每堆石子的石子个数仍然是非递减的。求有多少种合法的石子分配方案使得 Bob 必胜。n≤4×104n\leq 4\times 10^4n≤4×104，m≤1×1012m \leq 1\times 10^{12}m≤1×1012。 解法：考虑 {an}\{a_n\}{an​} 的差分数组 {bn}\{b...

A Ancestor 题意：给出两棵 nnn 个节点的树 A,BA,BA,B，A,BA,BA,B 树上每个节点均有一个权值，给出 kkk 个关键点的编号 x1,x2,⋯ ,xkx_1, x_2, \cdots, x_kx1​,x2​,⋯,xk​，问有多少种方案，使得去掉恰好一个关键点使得剩余关键点在树 AAA 上 lca 的权值大于树 BBB 上 lca 的权值。1≤k≤n≤1×1051 \leq k \leq n \leq 1\times 10^51≤k≤n≤1×105。 解法：由于 LCA 是可合并但没有逆的，因而对于这种挖去一个的情况，可以考虑维护序列的 lca 前缀和 preipre_...

A Villages: Landlines 题意：有一个电站位于 xsx_sxs​，需要在 [xs−rs,xs+rs][x_s-r_s,x_s+r_s][xs​−rs​,xs​+rs​] 的范围内设置至少一个电塔将电引出。n−1n-1n−1 个用电处位于 xix_ixi​，需要在其范围 [xi−ri,xi+ri][x_i-r_i,x_i+r_i][xi​−ri​,xi​+ri​] 有一电塔才能保证供电。你可以任意设置电塔（与电站、用电所重合也可），但是这些电塔需要用线连接起来。问最少需要多长电线。n≤2×105n \leq 2\times 10^5n≤2×105，−1×109≤xs,xi≤1×...

K You are given a tree... 题意：给定一个 nnn 个节点的树，树上每个点有颜色 aia_iai​，边有边权。问从中选择 kkk 个颜色不同的点，他们构成的生成子图的边权值和最大值。n≤1×103n \leq 1\times 10^3n≤1×103，k∈[2,5]k \in [2,5]k∈[2,5]，ai≤1×109a_i \leq 1\times 10^9ai​≤1×109。 解法：若颜色种类非常少（小于等于 101010），可以直接使用状压 dp：fu,Sf_{u,S}fu,S​ 表示在子树 uuu 内选择了颜色集合为 SSS 的最大边权值和，枚举子集，使用子树合并...

F Shannon Switching Game? 题意：给定一个多重无向图 G(V,E)G(V,E)G(V,E) 和一对点 s,ts,ts,t，起始时 sss 处有一个令牌。先手可以选择删除图上的一条边，后手可以选择删除令牌所在点 uuu 邻接的一条边 (u,v)(u,v)(u,v)，然后将令牌移动到 vvv。当令牌移动到 ttt 时后手获胜，否则先手胜。问最终结局。∣V∣≤100,∣E∣≤1×103|V| \leq 100,|E| \leq 1\times 10^3∣V∣≤100,∣E∣≤1×103。 解法：若令牌所处的位置确定，则胜负已分。显然若令牌在 ttt 处为一个必胜态，若某个节点...

E Reviewer Assignment 题意：有 nnn 份论文，mmm 个人每个人可以审稿这 nnn 篇论文中的一些论文。找出一种方案，使得每个人只审核一篇论文的同时，设 fif_ifi​ 为至少被 iii 个人审核的论文数量，找到 (f1,f2,⋯ ,fn)(f_1,f_2,\cdots,f_n)(f1​,f2​,⋯,fn​) 的字典序最大值。若有论文没人审核认为不合法。n,m≤400n,m \leq 400n,m≤400。 解法：考虑费用流。源点 SSS 向每个审稿人连接一条费用为 000，流量为 111 的边，然后这些人向能审核的论文连接一条流量为 111，费用为 000 的边。为...