[原根+循环矩阵快速幂]liu_runda NOIP模拟题【随】题解
解题报告先来介绍一波原根：如果 $\forall i\not=j,g^i\not\equiv g^j\ (mod\ P)$ ，那么 $g$ 是 $P$ 的一个原根，如果 $P$ 是素数那么一定有...
[Burnside引理+背包]BZOJ1004(HNOI2008)【Cards】题解
题目概述有 $R$ 张红牌，$B$ 张蓝牌，$G$ 张绿牌。现在给出 $m$ 种洗牌法（把 $i$ 位的放到 $x_i$ 上），如果两套牌可以通过 $m$ 种洗牌法洗成同一套则这两套牌相同。问有...
[BFS+链表]BZOJ1098(POI2007)【办公楼biu】题解
题目概述有 $n$ 个人和 $m$ 条关系 $(x,y)$ 表示 $x$ 和 $y$ 有联系方式。如果两个人没有联系方式就需要在同一个连通块，求出连通块个数和每个连通块点的个数。解题报告其实就是...
[二分]Codeforces1064E【Dwarves, Hats and Extrasensory Abilities】题解
题目概述交互题，有 $n$ 个点，你需要指定每个点的坐标 $(x,y)$ ，每次指定之后会告诉你这个点的颜色。你需要确定你的点的坐标使得你给出的点能被直线分成两半，输出这条直线。解题报告我是zz...
[最短路]Codeforces1064D【Labyrinth】题解
题目概述给出一张地图，有障碍和空地。问从 $(s,t)$ 出发最多往左走 $max_L$ 步，往右走 $max_R$ 步能到达多少点。解题报告翰爷秒了Orz。看似有两个限制，实际上把式子写一下发...
[区间DP]BZOJ1939(Croatian2010)【Zuma】题解
题目概述有 $n$ 个珠子，可以把不少于 $K$ 个同样颜色的连续珠子消去并把两端接起来。现在可以随意加珠子，问最少加多少珠子使得所有珠子都消去。解题报告挺妙的DP：$f_{i,j,k}$ 表示...
[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解
题目概述一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的点且只能取 $T$ 次。一个点不能...
[数位DP+堆]BZOJ3131(Sdoi2013)【淘金】题解
题目概述有 $n\times n$ 的网格，每个格子有 $1$ 块金子，现在处在 $(i,j)$ 的会变到 $(f(i),f(j))$ ，其中 $f(i)$ 表示 $i$ 十进制表示下所有位的乘...
[KMP-border]BZOJ4974(Lydsy1708月赛)【字符串大师】题解
题目概述如果 $S$ 是 $T$ 重复无数次之后的前缀，那么 $T$ 就是 $S$ 的循环节，现在给出一个串每个前缀 $i$ 的最短循环节 $per_i$ 表示前缀 $per_i$ 是前缀 $i...
[划水]CodeChef(SURCHESS)【Chef and Surprise Chessboard】题解
题目概述给出 $n\times m$ 的 $01$ 棋盘，有 $q$ 个询问，每个询问 $k$ 表示能够修改最多 $k$ 个格子的颜色，问能选出的边长最长的 $01$ 相间且是正方形的子网格。解...
