D Link with Game Glitch 题意：给定 nnn 个物品和 mmm 种物品合成方式 (a,b,c,d)(a,b,c,d)(a,b,c,d)：kakaka 个 bbb 物品合成 kckckc 个 ddd 物品，k∈R+k \in \R^+k∈R+。原定方式会导致出现无穷多个物品，现在需要求出最大的参数 www，使得每个合成方式均变成 (a,b,wc,d)(a,b,wc,d)(a,b,wc,d)。求最大的实数 www。n,m,a,c≤1×103n,m,a,c \leq 1\times 10^3n,m,a,c≤1×103。 解法：将合成方式抽象成有向图，边权为 ca\dfrac{c...

B 题题意：kkk 个城市有 nnn 个人去上班，每个人选一个城市上班，第 iii 个城市需要 eie_iei​ 个人去上班。第 iii 个人去第 jjj 个城市上班的代价为 ci,jc_{i,j}ci,j​，问最小化代价。n≤1×105n \leq 1\times 10^5n≤1×105，k≤10k \leq 10k≤10。 解法：如果不看范围，这题就是一个板子最小费用最大流——每个人向城市连边，流量为 111 费用为 ci,jc_{i,j}ci,j​；源点向每个人连边流量 111 费用 000，第 iii 个城市向汇点连边流量 eie_iei​ 费用 000。 但是此题边数达到了 1×10...

F 题意：有一个 nnn 个点 mmm 条边的无向图 GGG，qqq 次询问，每次询问给定 xi,yix_i,y_ixi​,yi​，表示一个长度为 nnn 的排列的第一项和最后一项，问是否能找到一个长度为 nnn 且首尾项为 xix_ixi​ 和 yiy_iyi​ 的排列，使得 ∀i∈[1,n−1]\forall i \in [1,n-1]∀i∈[1,n−1]，排列的前 iii 项构成的子图和后 n−in-in−i 项均联通。n,q≤1×105n,q \leq 1\times 10^5n,q≤1×105，m≤2×105m \leq 2\times 10^5m≤2×105。 解法：考虑以割点进行...

D Directed 题意：给定一个 nnn 个点以 111 为根的树，现在要从 sss 出发到 111 号节点。现在随机选择 kkk 条树边变成单向边，方向由儿子指向父亲。同时人在某一个节点以等概率选择出边，问期望多少步走到 111 号节点。 解法：对于一个有根树，从儿子节点 vvv 走到父节点 uuu，其期望步数为 Ev=2sizv−1E_v=2siz_v-1Ev​=2sizv​−1，其中 sizvsiz_vsizv​ 表示 vvv 的子树大小。 由此，如果没有改为单向边的操作，考虑从 sss 到 111 的期望步数，即是从 sss 一步一步走到其祖先直到 111 的期望步数之和。记从 s...

题意：给定长度为 nnn 的模式串 SSS，和长度为 mmm 的权值数组 {wi}\{w_i\}{wi​}。对于一个长度为 mmm 的串，wiw_iwi​ 表示使用该串上第 iii 个字符与 SSS 匹配可以获得 wiw_iwi​ 的权值。kkk 次询问一个长度为 mmm 的串 TTT 与 SSS 的最大权值公共子串。n,m,k≤1×105,mq≤1×106n ,m,k\leq 1\times 10^5,mq\leq 1\times10^6n,m,k≤1×105,mq≤1×106。 解法：对 SSS 建立 SAM，然后对于每次询问都可以将 TTT 串拉上去跑，对于 TTT 串，每匹配一个字符，...

G Geometry 题意：给定两个 nnn 个点和 mmm 个点的凸包和运动方向，问是否会发生碰撞，何时发生碰撞。3≤n,m≤5×1043 \leq n,m \leq 5\times 10^43≤n,m≤5×104。 解法：两个多边形速度为 v1⃗,v2⃗\vec{v_1},\vec{v_2}v1​​,v2​​ 等效于一个凸包以速度 v2⃗−v1⃗\vec{v_2}-\vec{v_1}v2​​−v1​​ 运动。那么问题就转化为了两个凸包的闵氏和与射线 (0,0)→v2⃗−v1⃗(0,0) \to \vec{v_2}-\vec{v_1}(0,0)→v2​​−v1​​ 有无交点，最近交点在哪里。...

题意：给定 nnn，记随机变量 XXX 为一个长度为 nnn 的排列中满足 ai=ia_i=iai​=i 的个数，求所有排列中 E(Xk)E(X^k)E(Xk)。1≤n≤1×10181 \leq n\leq 1\times 10^{18}1≤n≤1×1018，0≤k≤n+50000 \leq k \leq n+50000≤k≤n+5000。 解法：由错排定义可得 n!=∑i=0n(ni)Dn−i\displaystyle n!=\sum_{i=0}^n {n \choose i}D_{n-i}n!=i=0∑n​(in​)Dn−i​。 E(Xk)=∑i=0nikPr⁡[x=i]=∑i=0nik(...

A A Math Challenge 题意：给定 ​，求 ​。 解法：遇到 的式子，通常想到类欧几里得算法。此法的核心在于可以将这类的求和在 的时间内算出。 朴素的类欧几里得算法是计算 ​​​ 的。边界条件即是 ，此时答案等于 。考虑以下两种转移： ​ 或 ​。将 ​ 化成 ​，因而有 ​。 且 。可以证明，。容易发现， 交换了位置，并且每次折半，因而可以做到 的复杂度。 记 ​​，。依旧考虑上面的两种转移（此时细分为三种）： 。我们想要将 变成 ，想象一个 截取整个区域：，则会有一部分矩形区域 ，这部分和为 ，因而直接累加上去即可。此时剩余的部分即是 。令 ，将 进行二项...

C Fuzzy Graph 题意：给定一个 个节点组成的无向图，现给这些点染成红、绿、蓝三色。若一条边的两个端点颜色不同，则该边仍为黑色，否则染成两端点共同的颜色。要求： 基础要求：所有的点仍被黑色边连接。 （可选）三种颜色的点数量相同。 （可选）三种颜色中点数目最多的一个颜色，不存在该颜色的边。 需要在2、3点要求中选择一条达成。问染色方案。 解法：如果此题图是一个二分图，那么染色方案就非常的简单了——直接图进行黑白染色，对于染色数目少的颜色再分一半出去给第三个颜色即可满足第二个条件。考虑到一个图可以被视为是二分图上再加上一些别的边，因而可以考虑还是做一次黑白染色。 经过 dfs 过程...

B xay loves monotonicity 题意：给定两个长度为 的序列 与 ，，。有如下的修改操作： 给定 与 ，令 。 给定 ，区间 翻转。 有如下询问：给定区间 ，将 放入集合 中，记集合 中最后一个元素为 ，找到 中满足 且 的最小的 ，并插入集合。记 最终大小为 ，问 中相邻不同的个数。。 解法：首先考虑如何才能统计不连续的 序列的答案。注意到我们需要让每一次的 变大，因而我们可以划定一个下界，只有 在下界之上的才进行统计。 定义一个 cal 函数——cal(l,r,maximum)，其中 maximum 为一个 pair 类型，存放了要求的...

C Delete Edges 题意：给定一个由 个点组成的完全图，每次可以选择三个点 ，如果边 均存在，则删去这三条边。求一种构造可以不断的进行这样的操作使得最后剩下来的边数不超过 。 解法：我们需要删掉的边总数至少为 。一开始我们可以有一个朴素的想法：找一个点出来，剩下的点两两配对，这样构成三点，这样我们删去边的次数为 次。如果这个能重复 次我们的目标就达到了。因而，我们可以考虑重复这个过程，即每一个点都拎出来，和剩下的点两两配对。如果能做到不重复的构造就行了。 基于这个思想，我们可以考虑利用数字关系。对于第 号点，我们为其找的配对点对满足条件 或者 。这样一来不容易构成重复，二...

B Boxes 题意：有 个盒子，每个盒子中装有黑球白球概率均为 。打开第 个盒子所需代价为 。现在有一个机会，使用 的代价知晓剩余盒子中黑球个数，问使用最优策略开盒子直到直到全部盒子装球颜色情况的期望最小代价。 解法：显然询问盒子中有几个黑球这个策略一定只会用一次：第二次用的答案一定可以通过第一次询问的结果与中间新开出来的结果得到。并且越早用越好，因而在 的情况下一定是先用 的代价去询问。 由于每个盒子黑白球概率相同，因而一定是先开权值小的盒子。按照权值排序，从小到大的开盒子。接下来考虑第 个盒子在什么时候会打开。 记一开始的询问结果为 。开盒子的终止条件，可以是摸到了 个黑球...

B Sample Game 题意：使用一个不等概率的 随机数生成器，如果当前这一轮摇出来的数比之前摇出来的数都大或者等，游戏继续；否则终止游戏，其得分为轮数的平方。问得分的期望。 解法：如果游戏不结束，那么我们生成出来的序列一定形如：，当然中间有些数可能不取。 那么我们可以考虑构造一个多项式函数（生成函数）来表示这个序列：，共 个大的乘法。对于第 个括号，其内部 的次方数表示第 个数被选取了多少次。因而整个序列一定是这个多项式函数中每个括号里选一项出来组合而成的。这个函数中的 表示了待选择的物品，但是在每个括号中这个 含义不同——它们分别代表了 中每一个数。 这个时候考虑 其...

B Black and white 题意：给定一个 的全白方阵，每个小方格有一个点权 ，先要将其全部染黑，对于方格 其染黑代价为 。若对于某一个方格 ，存在另外一行一列满足 均已被染色，则当前无条件染色。问最小全部染黑代价。 解法：一个非常常见的方法是将点化边，边化点。对于每一横行和纵行，都认为是一个点；对于每一个点，都认为是沟通了其行列的一条边，其权值为 。那么原问题就转化成为了一个最小生成树：显然，只要两行两列均被连接，那么最后那个已经连接的边就不必要加入了——可以由其他的三条边导通。 类似题如洛谷 P5089 [eJOI2018]元素周期表 ，和此题如出一辙。 因而最后跑一个 Kr...