区间1336c cf dp

大常熟另类做法。不用排序。 要求直径长度，则想到把直径这一条链拎出来处理。然后考虑其他边会接在哪里，发现树最优情况下一定是一个毛毛虫的形式。更进一步，所有边都挂在接近直径中点的点上。 然后再考虑这些不在直径中的，长度为 \(l\) 的边带来的限制，设直径为 \(d\)，从每个点将直径切成两半，记其中 ......

来自机房大佬 FFT 的简单解法。 思路 首先有个结论：如果 \(a\) 中存在一个子串的和为 \(x\) (\(x>2\))，那么也就一定存在一个子串之和为 \(x-2\)。怎么证明？其实和为 \(x\) 的子串有 \(3\) 种情况： \(\text{1}\dots \text{1}\) 两边都 ......

官方题解。 思路 首先可以把 \(a\) 数组分成 \(n\) 块，每块都是长为 \(k\) 的 \(q\) 数组。于是我们可以把答案拆成两部分计算：块内的贡献和块外的贡献。对于块内，\(p_i\) 都是一样的，因此可以直接消去，计算的实际上就是 \(q\) 序列的逆序对数，把这个值 \(\time ......

思路 如果一条路径的 \(\text {mex} = k\)，那么 \(0 \sim k-1\) 这些点一定在路径中出现过，并且一定在一条链上。如果不在一条链上，那么就不满足简单路径这一条件了。因此我们在从小到大加点的过程中如果发现一个点不在已求出的链上，那么比这个点编号大的 \(k\) 答案一定都 ......

思路 首先最后的局面在两两字母间一定不会多于 \(1\) 个空格。考虑反证，假设有两个空格，那么有以下两种情况：\(\text{A}\_\_ \text{B}\)，\(\text{A}\_\_ \text{A}\)，也就是两边的字母不同，相同。对于第一种，在任意一个空格都可以填一个与他相邻字符不同的 ......

思路 题意这里就不讲了，直接进入正题。 贪心。 首先我们知道要想尽可能的让每一次操作都合法就得使 \(k\) 最大化，那么要使 \(k\) 最大就得尽可能的选择 \(0\) 操作，所以贪心策略就出来了:优先选择 \(0\) 操作，\(A,B\) 序列那个有 \(0\) 就选哪个合并。如果两个序列当前 ......

题目大意 A（Alice)和B (Bob)有一个字符串 \(\texttt s\)（所有字符都是小写字母）,他们在玩一个游戏：对于这个字符串 \(\texttt s\)，A可以删除其中长度为偶数的一串子串，B则可以删除其中长度为奇数的字串（也可以选择不删）。每次删除都能获得相应的分数，即将删除字串中 ......

CF1863E 参考这篇博客，本题解作为我的学习笔记。 思路 首先观察到提上说的依赖关系，容易联想到建出一张有向无环图。因为 \(a_i\) 要比 \(b_i\) 先完成，所以从 \(a_i\) 向 \(b_i\) 连一条边。而任务必须从入度为零的点开始依次往下做，因此想到拓扑排序（但题目给的就是拓 ......

题目链接：https://codeforces.com/problemset/problem/1919/E 题意 输入一个单调非减序列 \(p\)，求问有多少个序列 \(a\)，使得： \(|a_i| = 1\)； 令 \(s_i = \sum_{j = 1}^i a_j\)，则 \(s\) 排序后 ......

题意 给定一个序列 \(a\)，每次操作可以将区间 \([l, r]\) 中的所有元素加一，要求最后使所有元素等于 \(h\)。 要求： 任意两个区间的左右端点互不重合（\(l1 \neq l2\) 且 \(r1 \neq r2\)）； 对 \(10^9 + 7\) 取模。 思路 首先，可以考虑预处 ......

前言 多测不清零，亲人两行泪。 题意 对于一个空的数字串，有两种操作： 删除末尾的 \(n\) 个 \((n \ge 0)\) 元素，并将修改后数字串的最后一个元素加一； 在数字串末尾添加一个数字 \(1\)。 输入 \(n\) 个元素，表示第 \(n\) 次操作后数字串末尾的元素。 思路 首先考虑 ......

题目传送门 题目大意 给定一个长度为 \(n\) 的、只有 O 和 L 组成的字符串，求出一个 \(i\)，使得 \(i\) 左侧和右侧 O、L 的数量互不相等且每侧至少有一个 O 和一个 L。 思路 注意 \(n\) 的范围是 \(2 \le n \le 200\)，数据范围很小，暴力的时间复杂度 ......

第一次看的时候确实被题面吓了一跳，没有好好思考就放弃了。其实题目还是蛮简单的。 题意 对于两种操作，我们可以进行分类讨论。 当 \(a_i > a_j\) 时 操作一：将 \(a_i\) 变为了 \(2 \times a_i - a_j\)； 操作二：将 \(a_i\) 变为了 \(a_j\)。 当 ......

最近两次cf真的是给我打醒了 有一种前面上分都是靠运气的感觉 虽然知道确实不是靠运气。。 但是最近两次的大失败确实是非常值得反思的，也需要我直面和反思，不然没有进步 就结果来说，是非常非常离谱的失败，两次掉了我几乎300分 从过程上看，有什么问题？首先，是D题总是写不出来，C题也是经常非常勉强，从排 ......

算法学习 题单传送门 求最长上升序列（线性dp模板） Description 设有由 \(n\) 个不相同的整数组成的数列，记为:\(b_1\)、\(b_2\)、\(……\)、\(b_n\) 且 \(b_i<>b_j (i<>j)\)，若存在\(i_1<i_2<i_3< … < i_e\) 且有 \ ......

学习 算法学习——dd大佬：背包九讲（洛谷） 算法学习——dd大佬：背包九讲（博客园） 题单传送门 P236 采药 #include <bits/stdc++.h> using namespace std; int t, m; int f[1005]; int main() { cin >> t > ......

dp常见套路 题记：于2024/1/7日创建，作者发现dp套路太多了，于是用一个博客记录 相邻转移：把向前看作向后的反操作，且一个位置可以取负的，只要最后答案是非负即可。 每次任选做操作：另设一维状态，表示保留了几次操作，在之后的操作上释放。 ......

题意 给定一棵树和 \(3\) 个操作。 如果点 \(x\) 是白色，将她染红，否则对她地儿子做这个操作。 将点 \(x\) 子树内所有点染白。 询问 \(x\) 的颜色。 Sol 考虑对询问分块。 不难想到将当前块内的点建一棵虚树，然后再重构。 暴力建虚树即可。 Code #include <io ......

class Solution: def countSpecialNumbers(self, n: int) -> int: s = str(n) ''' 返回从i开始填数字，i前面填的数字集合是mask，能构造出的特殊整数的个数 is_limit 表示前面填的数字是否是n对应位上的，及下一个填的数字 ......

CF1553D Backspace 说实话这题不配绿题 题目传送门 题面 给你两个字符串 \(S,T\) ，问你能否通过将 \(S\) 中的若干个数换成 Backspace 来使其变成 \(T\) 。Backspace 能删去前一个输入的字符。 思路 很明显，如果将一个字符换成Backspace，那 ......

CF1551C Interesting Story 题目传送门 题意 给定 \(n\) 个仅由 \(\texttt{a,b,c,d,e}\) 组成的单词 （\(n \le 2\times 10^5\)），从其中选出尽可能多的单词，使得存在某个字母在这些单词中出现的次数比其他所有字母的出现次数之和还要 ......

更好的阅读体验 CF1801F Another n-dimensional chocolate bar 高妙的数论分块优化 DP。 第一步设计状态就有很大问题，如果直接设 \(f_{i,j}\) 表示前 \(i\) 个数成绩为 \(j\) 那就死了。这完全没有利用到整除的性质。正确做法是设 \(f_ ......

题目简述 给定一个字符串 \(t\)，由一个字符串 \(s\) 和这个字符串去掉所有 a 组成。求字符串 \(s\)。 思路 首先我们分析给定的字符串 \(t\)，它由 \(s\) 和 \(s\) 去掉所有 a 形成的字符串 \(s'\) 组成。那么当整个字符串 \(t\) 去掉 a 后，就得到了 ......

其实很简单的一道题。 思维路径 其实题目主要要考虑的就是以下三个条件。 每个人都要送一样多的硬币。 每个硬币都必须是不同的。 所有人送的硬币至少有 \(L\) 个是 Ivan 没有的。 我们一个一个来看。 每个人都要送一样多的硬币。 一共有 \(M\) 个朋友，所以说总共送的硬币的个数为 \(M\) ......

题目链接：洛谷 或者 CF 不是特别难的题，抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改，传统的 mex 求法里貌似就莫队类算法好带修，考虑带修莫队。 然而涉及到 mex 问题，你可能不由自主地想到回滚莫队求 mex 只删不加的板子题：P4137 Rm ......

题目链接：洛谷 或者 CF 不是特别难的题，抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改，传统的 mex 求法里貌似就莫队类算法好带修，考虑带修莫队。 然而涉及到 mex 问题，你可能不由自主地想到回滚莫队求 mex 只删不加的板子题：P4137 Rm ......

cf goodbye 2023(A-C) A - 2023 算法分析： 多组答案输出一组即可 先累乘，如果不是2023的除数也就是2023的因子就直接no 如果是2023的因子 先输出1 再输出2023/累乘的除数 #include<bits/stdc++.h> using namespace st ......

Preface 咕咕咕咕咕咕咕了半年有余。不得不说这题真的会把你调炸！！！！！！11 本题解中的所有 Hints 以白字显示。所以它可能不适合手机观看。 以及，首黑，2022 年 7 月 31 日 15:51。 Solution 算法一 询问次数 $2^h - 2$，适用于 $h \leq 4$。 ......

CF1665E 直接做不是很好下手，考虑找些性质。 有一个比较显然的贪心，就是按位从高到低的考虑，如果当前位至少有 \(2\) 个 \(0\)，就可以去掉该位为 \(1\) 的数。但是时间上显然是不行的。 假如没有重复的数，可以发现扫到最后一位时，剩下的数的数量是 \(\log V\) 的，证明省去 ......

CF1870F 题意：给一个长度为 \(n\) 的排列，求在其在 \(k\) 进制下按字典序排序后 \(\sum[p_i=i]\) 的值（\(n\le10^{18}\)）。 直接做是不好办的，只能在一些数中找到 \(p_i\) 的大小关系。 在手摸的过程中会发现一些长度相等的数之间会插入一些其它长度 ......