[树链剖分+线段树]Codeforces1023F【Mobile Phone Network】题解
题目概述有 $n$ 个点，$K$ 条特殊边，边权待定，保证无环，还有 $m$ 条普通带权边，现在确定特殊边的边权，使得最小生成树（边权相同选特殊边）包含所有特殊边。求上述条件成立的情况下最大边权...
[Pollard-Rho+高维前缀和]Codeforces1016G【Appropriate Team】题解
题目概述给出 $X,Y$ 和 $\{a_n\}$ ，问有多少 $(i,j)$ 存在 $v$ 满足 $(a_i,v)=X,[a_j,v]=Y$ 。解题报告来分析一波：$X|v,v|Y\Righta...
[贪心]Codeforces1016F【Road Projects】题解
题目概述有一棵带边权的树，询问 $m$ 次，每次新建一条边权为 $x$ 的边（不能建重边），问如何建使得 $1$ 到 $n$ 的最短路最大。解题报告可能不难吧，主要是需要比较显然的贪心来挖掘出性...
[几何+二分]Codeforces1016E【Rest In The Shades】题解
题目概述有一个光源按照 $(a\to b,s_y)$ 移动，还有 $n$ 个板 $(l_i,r_i)$ 。有 $q$ 个询问，问一个点 $(x,y)$ 被板挡住的总长度。解题报告斯波题，但是我不...
[计数+分段打表]BZOJ5383(湖南省队集训2018 Day2)【游戏】题解
题目概述在 $n\times n$ 的棋盘上放 $n$ 个车(ju)，使得车之间不会吃到，且在不经过车的情况下能够从 $(1,1)$ 走到 $(n,n)$ ，求方案数。解题报告能走到只需要满足没...
[Pollard-Rho+分块枚举子集]BZOJ5382(湖南省队集训2018 Day2)【走路】题解
题目概述有一棵树，如果 $w_i|w_j$ 且 $j$ 是 $i$ 的祖先那么 $j$ 可以直接到达 $i$ ，问从第一个点到所有点的方案数。解题报告$O(n^2)$ DP很显然，考虑优化。如果...
[去绝对值]HDU6435(2018多校训练赛第十场)【CSGO】题解
题目概述你在play♂CSGO，被第 $i$ 种枪打跪体现你有 $S_i$ 的手残值，并且有 $K$ 个参数 $\{x_{i,K}\}$ ，被第 $j$ 种刀捅挂体现你有 $S_j$ 的手残值，...
[Dsu on tree]HDU6430(2018多校训练赛第十场)【TeaTree】题解
题目概述给出一棵带点权的树，求每个节点 $i$ 的 $max\{(a_x,a_y)|LCA(x,y)=i,x\not=y\}$ 。解题报告因为 $10^5$ 内质因子个数最多只有 $2^7=12...
[构造]Codeforces1025E【Colored Cubes】题解
题目概述$n\times n(n\le 50)$ 的网格上有 $m(m\le n)$ 个方块，现在要把 $m$ 个方块归位，移动过程中不能碰到其他方块。求一种方案使得步数不超过 $10800$ ...
[Miller-Rabin+Pollard-Rho]Codeforces1025B【Weakened Common Divisor】题解
题目概述有 $n$ 组数对 $(a_i,b_i)$ ，求一个数使得 $\forall i,d|a_i\lor d|b_i$ 。解题报告因为随便求所以找共有的素因子就好了，那么先求出 $GCD$ ...
