A Car Show 题意：给定长度为 nnn 的序列 {ai}\{a_i\}{ai​}，其中 ai∈[1,m]a_i \in [1,m]ai​∈[1,m]，求有多少个连续子区间包含 [1,m][1,m][1,m] 中每个数。n,m≤1×105n, m\leq 1\times 10^5n,m≤1×105。 解法：使用双指针即可。时间复杂度 O(n)\mathcal O(n)O(n)。 #include <bits/stdc++.h> using namespace std; const int N = 100000; int cnt[N + 5], a[N + 5]; int ma...

K Symmetry: Convex 题意：给定 nnn 个点的凸多边形 CnC_nCn​，输出前 iii 个点构成的凸包的对称轴。n≤1×105n \leq 1\times 10^5n≤1×105。 解法：找对称轴可以使用 Manacher。本题先预处理整个凸包构成的串的 Manacher（注意不要倍长），然后依次加入点去考虑。 容易发现一个性质：随着 iii 的增大，∠CiC0C1\angle C_iC_0C_1∠Ci​C0​C1​ 是在不断变大的。除非该对称轴是其角平分线，则该角必然与另一个角大小相同（对称）。使用一个 map 记录每个角的大小，然后去枚举 ∠CiC0C1\angle C...

I Equivalence in Connectivity 题意：给定 kkk 个 nnn 的点的图。对于第 iii 个图，其由 pip_ipi​ 图删除或者新增一条边构成（保证 pi<ip_i<ipi​<i），问这 kkk 张图依据连通性可以分成多少组。n,k≤1×105n,k \leq 1\times 10^5n,k≤1×105。 解法：显然可以注意到，对图的操作序列可以构成一棵树。首先简化问题：若每次只在上一张图上进行删除或新增操作，如何实现。 显然维护连通性可以用并查集，但是并查集无法维护删除操作，因而考虑只能添加不能删除。那么使用线段树分治：将这个操作序列建立一颗线...

G Lexicographic Comparison 题意：给定两个长度均为 nnn 的排列 A,PA,PA,P。有以下 qqq 次三类操作：  交换 AxA_xAx​ 与 AyA_yAy​； 交换 PxP_xPx​ 与 PyP_yPy​； 查询 APxAP^xAPx 与 APyAP^yAPy 的大小。其中 APiAP^iAPi 表示排列 AAA 在 PPP 置换操作下迭代 iii 轮得到的置换。x,y≤1×1018x,y \leq 1\times 10^{18}x,y≤1×1018。  n,q≤1×105n,q \leq 1\times 10^5n,q≤1×105。 解法：考虑维护 PPP ...

F Longest Common Subsequence 题意：给定两个长度分别为 n,mn,mn,m 的序列 S,TS,TS,T，问其最长公共子序列长度。其中 SSS 与 TTT 都是通过 xi+1=f(xi)=(axi2+bxi+c) mod px_{i+1}=f(x_i)=(ax_i^2+bx_i+c) \bmod pxi+1​=f(xi​)=(axi2​+bxi​+c)modp 迭代产生。∣S∣,∣T∣≤1×106|S|,|T| \leq 1\times 10^6∣S∣,∣T∣≤1×106。 解法：容易注意到，若 Si=TjS_i=T_jSi​=Tj​，则从这两个位置开始，后面都一定完...

D Poker Game: Decision 题意：桌面上有 666 张扑克牌，Alice 和 Bob 手上各有 222 张且明牌。二人以最优决策依次从桌上抽取一张牌直到二人各有五张牌，最终根据德州扑克的规则比大小。问最终谁会赢。 解法：首先写清楚德州扑克的大小比较：依次按照牌型从大到小的顺序看能否构成这一种牌型。由于此处张数较少，可以暴力枚举每一种抽牌情况，暴力 dfs 计算当前的最优决策。设 dfs 返回值为 −1,0,1-1,0,1−1,0,1 为 Bob 胜利、平局、Alice 胜利，Alice 会从中选择尽可能大的状态转移，而 Bob 会选择最小的。 #pragma GCC opti...

A Puzzle: X-Sums Sudoku 题意：考虑一宫大小为 2n×2m2^n\times 2^m2n×2m 的方形数独， 求横排字典序最小（4×24\times 24×2 的数独如下）的数度中第 xxx 行或列的前或后 XXX 个数的和，其中 XXX 为第 xxx 行或列的第一个数字。  其中第二行 8=3+4+18=3+4+18=3+4+1，因为第一个数字为 333 代表取 333 个数字。第二列最下方的 343434 表示取本列后 777 个数字的和。n,m≤30n,m \leq 30n,m≤30，TTT 测，T≤1×105T \leq 1\times 10^5T≤1×105。 ...

A Floor Tiles in a Park 题意：给定 h×wh \times wh×w 的矩形，将其分为 kkk 个子矩形的方案数。h,w≤1×109h,w \leq 1\times 10^9h,w≤1×109，1≤k≤51 \leq k \leq 51≤k≤5。 解法：kkk 很小可以考虑分类讨论，但是不建议此做法。最好的分类方案是以子矩形在大矩形内部分割产生的点的位置进行分类讨论。小于等于 444 的情况可以简单分类讨论出来。 对于 k=5k=5k=5 有以下四大类：  全竖线分割、全横线分割（无新产生分割点）。(h−14)+(w−14)\displaystyle {h-1 \cho...

K 题题意：给定 nnn 堆石子，一次一个人选一堆非空的石子拿走至少一个石子，然后可以选择将这堆石子合并到其余非空的石堆去。qqq 次询问，给定区间 [L,R][L,R][L,R]，问有多少个子区间 [l,r]⊂[L,R][l,r] \subset [L,R][l,r]⊂[L,R] 使得先手必胜。n,q≤1×105n,q \leq 1\times 10^5n,q≤1×105。 解法：当局面变成偶数堆时，先手不能合并操作使得堆数变成奇数（1），因而只能不断拿石子，这时后手也会做类似操作，因而堆数不变。当此时所有的堆（堆数仍为偶数）都变成了只有一个石子，那么先手必输——后手永远可以仿照先手的操作下...

J 题题意：求长度为 nnn，且每个数字都在 [0,k−1][0,k-1][0,k−1]，使得区间连续和为 kkk 倍数的子区间有 ttt 个的序列个数。n,k≤64n,k \leq 64n,k≤64，t≤n(n−1)2t \leq \dfrac{n(n-1)}{2}t≤2n(n−1)​。 解法：区间连续和很容易想到前缀和，那么问题转化为前缀和的差的倍数有 ttt 个的序列个数。又数字范围在 [0,k−1][0,k-1][0,k−1]，因而前缀和序列取模后也可以一一对应原序列。同时，区间 [i,j][i,j] [i,j] 的连续和为 kkk 的倍数要求前缀和序列中 si−1=sjs_{i-1}...

I 题题意：定义一个串的最小表示为——按出现某个字符第一次出现顺序从小到大的排序，并依次编号 abc⋯zabc\cdots zabc⋯z。给定串 SSS，对其全部后缀进行最小表示的排序。∣S∣≤2×105|S| \leq 2\times 10^5∣S∣≤2×105。 解法：考虑朴素的后缀数组排序，即是对后缀 i,ji,ji,j 的最小表示排序。如果对于每对比较可以在 log⁡n\log nlogn 的复杂度内可以完成，那么总的复杂度就为 O(n2n)\mathcal O(n \log^2n)O(nlog2n)。对于 log⁡n\log nlogn 的字符串比较，通常可以转化为求 lcp\rm ...

B 题题意：给定平面上一 nnn 个点的整点凸多边形，使其绕着任意对称轴在空间中旋转，求其扫过的体积。若无对称轴则输出 000。n≤1×105n \leq 1\times 10^5n≤1×105。 解法：由于是整点多边形，因而对称轴至多不超过 O(log⁡n)O(\log n)O(logn) 条，可以考虑暴力枚举每条多边形的边的中垂线以及点来判定对称轴。更优美的解法（或对于非整点多边形）是使用哈希或者 Manacher 来判定（字符串题与计算几何的第一次交流），具体做法为，找到这个多边形的几何中心 (1n∑i=1nxi,1n∑i=1nyi)\displaystyle \left( \dfrac...

E 题题意：给定 nnn 个互不相同的数字和一个初始为空的序列 {a}\{a\}{a}，依次将其插入到序列的末尾，问至少经过几次相邻交换操作可以让序列符合三分特性（单峰）。n≤2×105n \leq 2\times 10^5n≤2×105，对每次插入输出答案。 解法：首先离散化。考虑最终的形态为一高-低-高形态（一个最低值），因而一个数字所处的位置有最低值左侧（L）和最低值右侧（R）两种。统计最终的交换次数等价于统计与一个数字有关的逆序对（或顺序对）数目，取决于所在的位置。 若当前新加入的数字 aia_iai​ 在 L 侧，其贡献是确定的——它在原序列的左侧，所有比 aia_iai​ 小的数字...

B Eezie and Pie 题意：给定一个 nnn 个点的树，第 iii 个节点可以到达其第 j,j∈[1,di]j,j \in [1,d_i]j,j∈[1,di​] 级祖先。问每个点能被几个点到达。n≤2×106n \leq 2\times 10^6n≤2×106。 解法：树上差分。对于每个点，其贡献在于从它往上 did_idi​ 个节点的一条链。倒过来从儿子往父亲差分，那么只需要给当前节点打上 +1+1+1 标记，di+1d_i+1di​+1 级祖先打上 −1-1−1 标记即可。总时间复杂度 O(n)\mathcal O(n)O(n)。 #include <bits/stdc++...