cf

传送门 description 对于一个 \(1\) 到 \(n\) 的排列 \(p\)，第 \(i\) 个位置的权值是 \(p\) 中数字 \(i\)，所在的连续自然数段的长度（可以递增，也可以递减）。现在给定一个数组 \(a\)，求第 \(i\) 个位置权值为 \(a_i\) 的排列 \(p\) ......

洛谷题面 CF1879F 分析 当 \(x\) 大于最大值时一定可以被约化为等于的情况，考虑枚举 \(x\)， 通过枚举倍数的方式可以知道存在若干段区间消耗同一精神状态的次数是相同的，那么区别就是其精神状态的差值。 那么可以用ST表维护精神状态次数的最大值和次大值，然后枚举倍数求出对于单个 \(x\ ......

思路 首先，对于 \(a_i\) 他必须得不小于最后的 \(a_{i-1}\)，所以每个数乘的次数都是固定的。 如果暴力去乘 \(2\) 直到不小于为止，将会超时，所以考虑使用其他的方法进行优化。 因为前后两个数可以同时乘以 \(2\)，相对比值不会变化，所以我们可以考虑对于最开始的 \(a_{i- ......

Lomsat gelral 把树拍成一条链，询问子树等于询问区间。 这样一看这道题就非常莫队。 但是有要求个数最多的颜色的编号，我们可以用线段树动态维护颜色的最大值。 这样，一个无脑莫队线段树的暴力就做出来了。 int n,a[N]; int dfn[N],nfd[N],cnt; int b[N], ......

一道 *2600 调了一年，代码细节是有点粪了，但自己菜也是挺菜的。/oh/oh 考虑容斥，令 \(f(A)=\sum\limits_{i,j\in A}\operatorname{lcp}(i,j)\)，那么答案就是 \(f(A\cup B)-f(A)-f(B)\)（这里的并表示可重集合并）。 令 ......

做法大同小异，但不知道为啥我跑这么慢而且还容易被卡。/kk 由于这题看上去和概率一点关系都没有并且 CF 标签中有 probabilities，不难想到随机。 由于答案子集大小至少为 \(n\) 的一半，我们每次随机一个数 \(a_i\)，它在最终答案集合里的概率为 \(\frac{1}{2}\)。 ......

提前了一个月，就做掉了这题，不过还是庆祝一下吧。（ 考虑 dp。令 \(f_{u,i}\) 表示货架 \(u\) 还剩 \(i\) 罐未被吃的蜂蜜的概率。答案就是 \(\sum f_{u,0}\)。 考虑一次修改 \(u\to v\)，由于被移动的蜜罐都被吃了，所以 \(v\) 的 \(f\) 数组 ......

题目 问有多少个长度为 \(n\) 的排列 \(P\) 满足 \(|P_i-i|=1\) 的 \(i\) 的个数恰好为 \(k\) 个 分析 设 \(dp_{i,j,k}\) 表示前 \(i\) 个数钦定 \(j\) 个数满足上述条件且现在 \(i\) 和 \(i+1\) 因此被占用的方案数。 那么 ......

分析 发现每个字符串只会被它的后缀规定，那么就从后往前计算，使得计算每个字符串的时候其后缀已经合法。 因为每一次计算我们都只想删最少的字符，而且删得越少这个字符串的字典序就越大，所以它的前缀的最小字典序就越大，需要删的字符就越少，所以对于每一次计算都只删最少的字符的贪心策略符合全局最优，所以这个贪心 ......

CF1520 \(div3\) 信心场! Do Not Be Distracted! 开一个 \(vis\) 数组即可 只要连续两个字符不相同 就将前一个打上标记 那么我们访问任意一个具有标记的节点就判断无解即可 #include <bits/stdc++.h> using namespace st ......

A Many Equal Substrings 很容易想到要找border，一看数据范围n<=50,kmp,直接暴力找就行了 #include<bits/stdc++.h> using namespace std; int n,k; char s[55]; int maxid; signed mai ......

分析 先对每一列都做 DP 寻找极长单调不降区间，能够得到若干极长单调不降区间，只要询问的区间是这些区间的子区间，那么说明在这个区间内必有一列的这个区间是单调不降的。 思考如何快速判断子区间。 用 \(f_{x}\) 表示以 \(x\) 为所有左端点为 \(x\) 的区间的右端点最大值，那么对于询问 ......

气死我了，我决定水了这篇题解。 反悔贪心，考虑决策及反悔，记到第三层反悔就行。 然后你发现要一次只考虑一个不行，要两个两个考虑，然后就做完了，如果深入往下分析能分析出更多可以简化做法的结论。 #include <bits/stdc++.h> using namespace std; const in ......

分析 思考对于 \(M\) 的每个数而言，贡献是一定的，它最多只能换掉一个数。 那么贪心地能换就换，但是如果换小的可能会导致更小的数换不掉，那么就换能换的最大的，这样不会干扰只能换小数的其他数，能换这个数的可以去换其他数，如果连其他数都换不掉说明这两个数等效，换谁都一样，所以这样换一定是最优的。 如 ......

分析 发现操作 \(6\) 次后就会回到初状态，于是将状态打表，将 \(n\bmod6\) 即可。 代码 #include <iostream> using namespace std; constexpr int MAXN(1000007); int a[6][3] = { {0, 1, 2}, ......

思路 如果每一次加或者删一个区间，再去暴力找有没有互不相交的区间的话，铁定 TLE。 那么，我们考虑维护有多少对互不相交的区间，那么每次加或者删一个区间，就去算这个区间对答案的贡献，然后再看答案是否为 \(0\) 即可快速判断有没有互不相交的区间。 现在考虑如何计算一个新加入或者删去的区间能让互不相 ......

分析 看到异或不难想到 01Trie。 不难想到，当两个数的值相等的时候，我们可以当这两个点是一个点，因为连边的费用为 \(0\)。 那么对于一个序列 \(n\)，若存在 \(m\) 种不同的权值，那么在 Trie 树上子节点数为 \(2\) 的节点就有 \(m-1\) 个（因为如果一个数新加进来与 ......

题目 有一个长度为 \(m\) 的书架，以及 \(n\) 个长度 \(a_1,a_2,\dots,a_n\) Alessia 和 Bernardo 从书架上取书。每次由 Alessia 选择一个之前没选过的 \(i\)， 并选择一个长度为 \(a_i\) 的区间，需要保证这个区间内的书全都没有被取过 ......

同步发布与洛谷（太懒了不想写东西直接搬过来了（（（逃 ） 原题链接 简单贪心。 题意 求一个起始全为 \(0\) 的数列 \(a_1,a_2 \cdots a_n\) 每次可以选择一个数 \(i\) 使 \(a_i \cdots a_n\) 都加上或减去 \(1\)，求修改成给定的序列 \(b_1, ......

题意简述 给出一个长度为 \(n\) 的序列 \({a_n}\) ， 找出一个子序列 \({b_k}\) ，使其满足 \(\min(b_1, b_2) \leq \min(b_2, b_3) \leq ··· \leq \min(b_{k - 1}, b_k)\) ，求 \(k\) 的 最大值。 \ ......

A Log Chopping 直接把每次总切割数算出来就行 #include<bits/stdc++.h> using namespace std; int t; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) ......

分析 手玩样例发现连一条边实际上是将一个多边形分割成两个部分，而且不能在这两个部分直接连边，发现这两个部分是完全独立的，于是考虑区间 DP。 设状态 \(f_{l,r}\) 表示将 \([l,r]\) 区间连成树的方法数量。 那么存在两种转移，一种是 \(l,r\) 间不直接连边，这样中间的点都需要 ......

应该是 OI 退役前最后一次发「CF 刷题计划」了。 难度范围实时浮动，取决于智商浮动。 反正也不会再出模拟赛了，所以干脆都放上来吧。 难度标识（0-5 保留一位小数）： 标准参考 1 一眼丁真 2 需要时间思考 3 需要题解提示 4 需要仔细阅读题解 CF1430G Yet Another DAG ......

CF1586I 题解 传送门 更好的阅读体验 简化题意：有 $n\times n$ 的网格，你需要进行黑白染色，使得每个格子的颜色恰好与 2 个与其四联通的格子的颜色相同，其中有些位置已经确定，问是否有解及是否有唯一解。 思路： 很神仙的构造题。 先从特殊的地方入手。对于 4 个角，它们只和 2 个 ......

感觉，好自然啊！ 想法 dp，想办法分解这个博弈的过程。发现警察会从一片叶子到另一片叶子，在叶子抓住小偷时所有小偷可以全树乱走。因此 dp：\(f_{u, i}\) 表示警察位于 \(u\)，全树剩余 \(i\) 个小偷时的答案。 因为两边都绝对理性，小偷在警察离开叶子后不会移动并位于多片叶子上。考 ......

本来开了某场远古 Div 1，然后学了一堆前置知识至今仍然不会 E。换一场写来得及吗？ A. Channel 模拟，略。 B. Split Sort Description 给你一个长度为 \(n\) 的排列。 每次操作你可以选择一个数 \(x\)，然后类似于快速排序地把小于 \(x\) 和大于等于 ......

对集合的一些判断可以考虑随机化哈希。 给每个数随一个权，如果集合 \(S\) 中每个数的出现次数都是 \(k\) 的倍数，那 \(S\) 中元素的权值之和就会是 \(k\) 的倍数，否则会是一个在 \([0,k)\) 中随机的值。 也就是说如果这个集合不满足要求，我们做一次这个检测，有 \(\fra ......

分析 看到 \(n \leq 35\) 的数据范围就想到了 meet-in-middle。 先爆搜出对于 \(1 \sim \frac{n}{2}\) 和 \(\frac{n}{2} \sim n\) 两个下标范围内在模意义下所有的和。 然后用一个常见 trick，就是枚举第二个部分的和，然后匹配第 ......

分析 很容易想到从 \(0\) 开始枚举 \(a_i \neq i\) 的位置个数一直枚举到 \(k\) 计算每种情况下的答案加在一起即为答案。 对于 \(k\) 确定的情况，\(a_i = i\) 的位置共有 \(C_{n}^{n-k}\) 种情况，剩下的位置要保证 \(a_i \neq i\)。 ......

分析 题意为选出最多的操作使机器人执行完仍停留在原地。 分为左右和上下两类，则每一类的可执行操作数都是操作次数最少的一种操作的二倍（因为正反操作都要执行才能抵消）。 直接统计每种操作的操作次数计算答案即可。 代码 #include <iostream> using namespace std; co ......