CF1316E Team Building
Codeforces Luogu 分析 有一个显然的状压 DP：设 $dp_{i,S}$ 表示前 $i$ 个人，$S$ 中的位置被选中时的最大力量值，转移枚举当前这个人当观众还是进某个位置即可。 然而 $p+k\leq n$，所以这个做法不太行。 注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序，当 $i-|S|>k$ 时 $i$ 显然不会被选...
分类 题解 下的文章
- 首页
- 题解
CF1354G Find a Gift
Codeforces Luogu 分析 蓝题都不会做了 /kk 因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。 那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。 如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。 代码 // ==...
洛谷4654 [CEOI2017]Mousetrap
Luogu LOJ 分析 为了方便，将陷阱作为根节点。那么冷静分析一下可以得到一些结论（没有证明） 当老鼠走到一个叶节点时，它将被困住。 当老鼠被困住时，将其它岔路口堵住，然后将到根的路径擦干净是最优的。 设 $f_u$ 表示老鼠进入 $u$ 子树后回到 $u$ 的最小操作次数。显然老鼠会找一个 $f$ 最大的子树进去，所以堵住 $f$ 最大的子树最优，此时老鼠会进入 $f$ 次大的子树...
CF1354F Summoning Minions
Codeforces Luogu 分析 有几个比较显然的结论（证明不会）： 一定存在一组最优解，使得所有卡都被摆上去过。感性理解：因为 $b_i\geq 0$ 所以你就算摆上去再拿下来也不会更差。 一定存在一组最优解，满足首先摆上 $k-1$ 张卡，再将 $n-k$ 张卡摆上去后立即拿下来，再将剩下的那张卡摆上去。感性理解：此时 $b_i$ 的贡献是最大的，且 $a_i$ 的贡献没有影响。...
洛谷4006 小 Y 和二叉树
Luogu LOJ 分析 显然最小的 $d_i\leq 2$ 的点会是答案中第一个数。设这个点为 $rt$。 考虑从 $rt$ 开始跳父边。分类讨论一下当前点的情况 如果度数为 $1$，说明已经找到了根。 如果度数为 $2$，则有一条已经确定（是左儿子），我们只需要判断另一条边作为父边还是右儿子更优，只需要比较 $v$ 子树中最小的 $d_i\leq 2$ 的点和 $v$ 的大小即可判断。...
洛谷4774 [NOI2018]屠龙勇士
Luogu LOJ 分析 显然用来打每条龙的剑是确定的，可以用 std::multiset 预处理出来。假设打第 $i$ 条龙的剑的攻击力为 $atk_i$。 那么如果一个 $x$ 满足条件，则应有 这样子就可以直接 exCRT 了。 需要注意的是 $a_i\leq 10^{12}$，所以需要写慢速乘。 代码 // author: M_sea // website: https:/...
洛谷1587 [NOI2016]循环之美
Luogu LOJ 分析 可以发现，$k$ 进制分数 $\frac{x}{y}$ 是纯循环的当且仅当 $\gcd(y,k)=1$。证明可以点这里。 另外为了避免算重，我们只统计最简分数。 那么我们要求的东西就是（设 $l=\min(n,m)$） 这样子直接枚举约数递归下去算即可；当 $k=1$ 时无法继续往下递归，但此时相当于要求 $\mu(i)$ 的前缀和，杜教筛即可。 代码 // ==...
洛谷4094 [HEOI2016/TJOI2016]字符串
Luogu LOJ 分析 考虑二分答案 $mid$，则我们需要判定是否存在一个 $p\in[a,b-mid+1]$，满足 $\operatorname{lcp}(suf(p),suf(c))\geq mid$。 既然有 LCP，可以考虑后缀数组，则 $\operatorname{lcp}(suf(p),suf(c))\geq mid$ 相当于 $\min_{i=rk_p+1}^{rk_c}h...
洛谷1117 [NOI2016]优秀的拆分
Luogu LOJ 分析 设 $L_i$ 表示以 $i$ 为左端点的 AA 串的数量，$R_i$ 表示以 $i$ 为右端点的 AA 串的数量，则答案为 考虑计算 $L_i$ 和 $R_i$。 暴力就是 $\mathcal{O}(n^2)$ 枚举并用哈希 $\mathcal{O}(1)$ 判断，这样子可以拿 95 分。 考虑枚举 A 的长度 $l$，然后把所有是 $l$ 的倍数的位置标成关键...
洛谷4590 [TJOI2018]游园会
Luogu LOJ 分析 发现题目中那个 LCS 的限制不好处理，考虑建一个自动机来解决这个问题。 假设我们已经建出了自动机，我们就可以设 $f_{i,j,k}$ 为前 $i$ 个字符，已经转移到自动机的 $j$ 节点，已经匹配到了 NOI 的第 $k$ 位的方案数，然后根据 $k$ 转移即可。 现在考虑如何建这个自动机。考虑求两个串的 LCS 的过程，即设 $g_{i,j}$ 表示第一个串...