CF526D Om Nom and Necklace
Codeforces Luogu 定义 我们可以先找到所有 $g(pre(i))=1$ 的 $i$，再往后扩展。 枚举 $i=|A|$，那么 $g(pre(ik))=1$ 的充要条件是 $S[1..ik-i]=S[i+1..ik]$。 因此我们可以将 $suf(i+1)$ 和 $S$ 匹配，如果匹配长度 $\geq i(k-1)$ 说明合法。 这个匹配的实质是后缀与前缀匹配，因此可以使用...
分类 题解 下的文章
- 首页
- 题解
洛谷3770 [CTSC2017]密钥
Luogu 分析 为了方便，把题目里的特征值称为「特征值 A」；再定义一个「特征值 B」表示不弱的 B 的个数。 那么可以将三个问题转化一下： 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $k$ 时，请问 X 在哪个位置。 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $k-S$ 时，请问 X 在哪个位置。 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $S$ 时，请问...
CF1220D Alex and Julian
Codeforces 分析 考虑两个数 $a,b$ 要满足什么条件才可以同时留下。 可以发现，$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环，这个环的大小是 显然可以根据 $a,b$ 的奇偶性进行讨论： 若 $a,b$ 都为奇数，则上式...
JOI 2018 Final 简要题解
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫，维护 ...
CF1097D Makoto and a Blackboard
Codeforces Luogu 分析 容易想到设 $dp_{i,j}$ 表示 $j$ 次操作后 $i$ 的期望大小，转移直接枚举约数即可。然而这样子显然是会 T 的... 注意到当 $\gcd(i,j)=1$ 时有 $dp_{i\times j,k}=dp_{i,k}\times dp_{j,k}$，因此我们可以将 $n$ 分解为 $p_1\!^{c_1}p_2\!^{c_2}\cdots...
洛谷5444 [APIO2019]奇怪装置
Luogu LOJ 分析 这个东西显然是有循环节的。 假设 $t_1$ 和 $t_2$ 两时刻 $x,y$ 相等，那么有 那么如果输入的区间中有长度 $\geq$ 最小循环节长度的，直接输出最小循环节长度；否则问题变为区间覆盖，按左端点排序后扫一遍即可。 代码 // =================================== // author: M_sea // we...
UOJ461 新年的Dog划分
UOJ 分析 我们先假装原图是个二分图。 我们可以先想办法求出原图的一棵生成树，那么对其黑白染色即可求出答案。 一个暴力的做法是尝试删掉所有边，如果删掉某条边后连通性发生改变则这条边在生成树上，保留这条边，否则删掉这条边。这样子询问次数是 $\frac{n(n-1)}{2}$。 事实上我们可以每次二分下一条树边的位置：如果删掉 $[L,mid]$ 中的边后图仍连通则下一条树边在 $(mid,...
BZOJ4722 由乃
BZOJ 分析 $[l,r]$ 的非空子集数为 $2^{r-l+1}-1$，而子集贡献数至多为 $1000(r-l+1)$。 当 $2^{r-l+1}-1>1000(r-l+1)$ 即 $r-l+1>13$ 时，根据抽屉原理显然有解，因此直接输出 Yuno 即可。 先考虑操作 $1$ 怎么做。用树状数组维护每个点被修改的次数，然后倍增即可求出答案。 再考虑操作 $2$。设 $dp...
LOJ6043 「雅礼集训 2017 Day7」蛐蛐国的修墙方案
LOJ 分析 我们把 $i$ 向 $p_i$ 连边，这样子会有很多环。可以发现，如果有奇环则无解，所以我们只考虑偶环。 显然一个偶环上只会是一个 (、一个 )、……，但是如果直接搜的话复杂度最大会达到 $\mathcal{O}(2^{\frac{n}{2}})$，无法接受。 考虑一个大小为 $2$ 的偶环，显然小的那个填 (、大的那个填 ) 更优，因此我们只需要搜大小 $\geq 4$ 的环...
BZOJ3837 [Pa2013]Filary
BZOJ 分析 首先我们可以得到 $k$ 至少为 $\frac{n}{2}$，构造方式是令 $m=2$。 也就是说，在最优解中每个数被选中的概率是 $>\frac{1}{2}$ 的。 考虑 rand() 一个在最优解中的数 $x$，我们把其它的 $\neq x$ 的数与 $x$ 作差并分解质因数，那么所有质因数中出现次数的最大值加上 $=x$ 的数的数量就是当前最大的 $k$。 这里有...