CF

首先考虑 \(k = 0\) 的情况。 贪心，最后一步之前每个 \(i\) 只会跳到 \(j \in [i, i + a_i]\) 且 \(j + a_j\) 最大的点 \(j\)，这个信息或许可以线性处理？但是我没脑子，我用线段树维护，时间复杂度 \(\mathcal O(n \log n)\)。 ......

题目链接：https://codeforces.com/contest/1687/problem/C 题意简述 有两个长为 \(n\) 的数列 \(a\) 和 \(b\)。有 \(m\) 条线段，你可以进行任意次以下操作： 选择一条线段 \([l, r]\)，若 \(\sum\limits_{i = ......

CF1348B. Phoenix and Beauty 思路 最后输出的一定是一个周期为k的数值。我们只需要查看输入进来的数组中的元素的种类和k的关系即可。元素种类大于k输出-1；小于等于k，输出每个不同的元素，不够k个的话就用1补齐 ac代码 #include <bits/stdc++.h> us ......

Problem - E - Codeforces I Wanna be the Team Leader - 洛谷 差一点就想到了/ll 遇到困难？排序肯定不会变差！ 性质：每个项目分配的程序员肯定是一段（显然） \(m\) 很小？考虑设 \(dp_{i,S}\) 表示考虑前 \(i\) 个人选项目集 ......

Monocarp and the Set - 洛谷 Problem - D - Codeforces 非常之降智 加入一个数让他满足他是最大值需要判断前面加入的那些数中最大的是哪个，但删除一个数让他满足是最大值只需要直接把他删掉即可 因此我们要反着考虑这个问题： 如果当前是 <，则删除最小的数，有一 ......

不难发现这是个 Nim 游戏，于是对每对 \((L_i, R_i)\) 所求转化为： \[\bigoplus_{i = 1}^n (a_i - L_i)[a_i \ge L_i] \]暴力做时间复杂度就是 \(\mathcal O(n^2)\)，考虑优化。 感觉好像可以倍增？设 \(f(i, k)\ ......

String Journey 题面翻译 对于一个字符串数组 \(t_1, \ldots, t_k\)，若对于每一个 \(t_i\) 都是 \(t_{i-1}\) 的真子串的话，即 \(t_i\) 是 \(t_{i - 1}\) 的子串且 \(t_i \ne t_{i-1}\)，则称为有序串组，列如 ......

由题意可以发现一个性质： \[f[(l, r)] = \bigcup_{i = l}^{r - 1} f[(i, i + 1)] \]进而可以推广至： \[f^k[(l, r)] = \bigcup_{i = l}^{r - 1} f^k[(i, i + 1)] \]证明显然，即若 \([l_1, ......

某人在换根时根还设置成 \(1\) 交了整整 \(11\) 发，我不说是谁。 先考虑一下 \(2\) 询问的实际用途，因为我们可以用它来确定深度，根据树上交互题的常见技巧，我们通过这种方式确定了一个拓扑序，只要能在拓扑序的前缀中快速查询一个点的父亲，就可以求出这棵树。 考虑先以一条边为根，那么其会有 ......

给定一变量，初始为 \(1\)，每次等概率随机进行以下两种操作之一： 令 \(x\) 加一。 令 \(x\) 乘二。 求期望多少次操作之后 \(x\) 会 \(\ge n\)。 \(T\) 组数据，\(T\le 100\)，\(n\le 10^{18}\)。 对着 aw 老师的题解学的，感觉太深刻。 ......

不难发现一件事：对于在 \(i\) 之后能跟 \(i\) 匹配的 \(j\)，最好的办法显然是使得 \(j\) 最大。则用前缀和统计整个和，并且用前缀和维护负数和，在枚举 \(i\) 统计出最小答案时在后面计算出满足最大答案的条件并输出即可。 ac records #include<bits/std ......

题意：给定一张有向图，询问 \(s, t\) 两点间字典序最小路径上的第 \(k\) 个结点。 首先要验证 \(s, t\) 间是否连通，所以建反图，枚举 \(1 \sim n\)，跑 dfs。这部分时间复杂度 \(\mathcal O(n^2)\)。 确定了哪些点跟 \(t\) 连通后，\(s\) ......

原问题可以看作是二分图博弈的模型，那么可以将博弈问题转化为最大匹配的一定性判定性问题，实际上博弈的 \(\text{dp}\) 过程直接摊开就是每次删任意一个叶子与其父亲，将父亲变为 \(1\)，这个也就是最大匹配的求解过程，而是否为匹配的上端点即该点的 \(01\) 状态，那么实际上每一行的 \( ......

whk 考试前写题解攒 rp 有用吗 仍然是讲讲想出来的过程。 首先，我们只需要关心一个联通块中有哪些点，而不用关心图的具体形态。 然后，将每个连通块看作一个点，就变成了一个无根树计数问题，但是带权值。首先想到 prufer 序列。 prufer 序列的定义：一棵无根树中，每次将编号最小的叶子取出来 ......

大常熟另类做法。不用排序。 要求直径长度，则想到把直径这一条链拎出来处理。然后考虑其他边会接在哪里，发现树最优情况下一定是一个毛毛虫的形式。更进一步，所有边都挂在接近直径中点的点上。 然后再考虑这些不在直径中的，长度为 \(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题也是经常非常勉强，从排 ......

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

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