cf

CF1552D题解 思路 首先，$a_i$ 的正负不重要，如果 $a_i=b_j-b_k$，那么就有 $-a_i=b_k-b_j$，读入时将 $a_i$ 全部转化为正数。 若满足 $a_i+a_j+\ldots+a_k$，那么就可以构造出 $b$ 序列，否则不行。 从左到右遍历一遍 $a$ 序列，动 ......

https://codeforces.com/contest/1864/problem/D 结论很好猜，直接从上到下做就行 我们可以维护差分数组，表示对下面的影响，逐行往下推就行，当然+和-要分开，因为一个是往前推，一个往后推。 时间复杂度\(O(n^2)\) #include<cstdio> #i ......

Link CF1899 D Yarik and Musical Notes Question 给出一个序列 \(a\) ，我们定义 \(b_i=2^{a_i}\) 求 \(b_i^{b_j}=b_j^{b_i} (i<j)\) 的个数 Solution 考虑化简式子 \[\begin{aligned ......

好久没打div了 然后思维太差 现在被抓回来继续打了QWQ 终于被我逮到一场G数据结构的 ak了 既然ak了就开心地写下题解 别被hack别被hack别被hack 这场挺简单的 之前打的div3都好难qaq A. Game with Integers 题意：给一个数字，两人轮流操作，可以+1或者-1 ......

https://codeforces.com/contest/1864/problem/C 思维越来越僵化了 假如\(n=2^k\)，直接每次/2就行。 否则，我们可以考虑如何转化成上面的情况 令\(n=2^k x\)，那么我们显然可以转移到\(n=2^k (x-1)\)，因为x是奇数，所以2的次幂 ......

Game on Sum (Hard Version) 题面翻译 Alice 和 Bob 正在玩一个游戏，游戏分为 \(n\) 个回合，Alice 和 Bob 要轮流对一个数 \(x\) 进行操作，已知这个数初始值是 \(0\)。 具体每个回合的行动规则如下： Alice 选择一个在区间 \([0,k ......

首先将题意转化一下，假设我们在第一步中将原图划分成了 \(p\) 个连通块，计第 \(i\) 连通块大小为 \(siz_i\)，那么每个连通块可以向外连 \(\min{(k,a_i)}\) 条边。而使原图联通显然至少需要 \(p-1\) 条边，形式话的来讲，我们能在第二步使图联通这个条件等价于 \( ......

blog。抽象意义上单杀了。 首先第一位必定为 \(0\)，然后取反串就不用去考虑了。 \(n\le50\)，考虑爆搜。搜整个串的前一半（设半长为 \(M=\left\lfloor\dfrac n2\right\rfloor\)，前一半的串在十进制下值为 \(v\)），后半段的数量可以计算： 整个串 ......

feecle 的题单 . 后文复杂度分析中默认 \(v\) 是值域 . 目录CF1292B Aroma's Search (*1700)CF1304C Air Conditioner (*1500)CF1313D Happy New Year (*2500)CF1322B Present (*210 ......

Vive le R & M! 还被种草了 Hurt，真的颇有感触，但这是 Solution Set，就不写了。 A. The Monster exgcd，但是发现 \(1 \leq a, b, c, d \leq 100\) 直接暴力枚举即可。我认为这是 \(O(1)\) 的，但题解认为是 \(O( ......

思路 简简单单构造题，就是要认真读题，是能且只能满足两个条件。 我们可以考虑每种数字，如果数字只有一个，是不能满足任何一个条件的，那就随便给一个 \(b\) 即可。 如果这个数字有多个，那么就只能有两种 \(b\)，否则就会满足三个条件，所以一种数字最多满足一种条件。 所以，如果只有一个或者甚至没有 ......

传送门 decription 给定 \(n\) 和长度为 \(n\) 的排列 \(p\)。在一个位置 \(i\) 可以采取如下行动： 花费 \(a_i\) 走到 \(i+1\)。 如果 \(p_i\) 后存在一个 \(p_j>p_i\)，则可以花费 \(b_i\) 跳到 \(j\)，否则可以花费 \ ......

Archaeology 有一颗带权树，有三个操作： 给一个点打上标记。 删除一个点的标记。 查询有标记的点的导出子树的边权和。 \(n, q \le 10^5\)。 求的实际上就是虚树的大小，求这个有一个常用的方法就是把点按 dfn 排序后相邻点对（首尾也算相邻）之间的距离和除以 2。 所以我们可以 ......

这道题的思路非常简单，经过对样例的分析，我们发现，所有区间的总和为： $\sum_{i = 1}^{n} a_i \times d_i $（其中 $a_i$ 为原数组的第 $i$ 项，$d_i$ 为第 $i$ 个元素被区间覆盖的次数） 这里有一个小细节：对于某一个元素被覆盖的次数我们可用差分进行优化 ......

题意 给出一串数，请问，通过将 \(a_i\) 和 \(a_{i+1}\) 同时加 \(1\) 或减 \(1\)若干次，能否使它单调不减？ 思路 我们发现，如果要让 \(a_i\) 和 \(a_{i - 1}\) 满足单调不减，可以通过修改 \(a_i\) 和 \(a_{i+1}\) 让 \(a_i ......

非常好题目，使我的大脑旋转（？） 还是一样，介绍思路。 既然题目让我们计算 \(f_{\max}(n)\) 的数量，则先考虑 \(f_{\max}(n)\) 的值怎样求得。容易发现，设 \(n=\prod p_i^{k_i},p_i\in \operatorname{prime}\) ，则 \(f( ......

题目描述： 给定 \(n\) 个点的树，点有点权，求满足最大点权与最小点权之差小于等于 \(d\) 的连通子图数目。答案对 \(10^9 + 7\) 取模。 数据范围： \(1\le d\le 2000,1\le n\le 2000\) \(1\le a_i\le 2000\) \(1\le u,v ......

题意 给定一棵根为 \(1\) 的有根树，以及字符串 \(S\)。 \(x, h\) 求 \(x\) 的子树内，深度为 \(h\) 的节点的字符能否重排为一个回文串。 Sol 不难发现，回文串显然至多有一个字符出现奇数个。 所以我们对于每种字符随机附权值，维护前缀异或值。 查询时枚举 \(26\) ......

CF1436E Complicated Computations mex的定义是：一个区间中没有出现过的数中最小的整数。 对于一个区间，当正整数x在区间中没有出现过、[1, x - 1]（整数）在区间中全部出现过，那么正整数x就是该区间的mex 正整数x在区间中没有出现过 我们一共有n个数字，所有的 ......

题目传送门 题目主要内容 题目要求判断给定两个字符串 \(s\) 和 \(t\) 是否匹配。字符串 \(s\) 可以包含一个通配符，它可以表示任意长度的字符序列。如果可以通过替换 \(s\) 中的通配符来得到字符串 \(t\)，则表示匹配。 主要知识: 字符串处理：包括字符串的比较，截取，查找等操作 ......

题目简述 题目要求在一个 \(m\times m\) 的棋盘上放置 \(n\) 个棋子，使得满足以下规则：对于任意的两个棋子 \(i\) 和 \(j\) ，有 \(|r_i-r_j|+|c_i-c_j|\geq|i-j|\)。 思路简述 \(m\) 的最小值为 \(\frac{n}{2}+1\)。 ......

Hot Bath 题解 题目简述 \(5\) 个正整数 \(t_{1}\)，\(t_{2}\)，\(x_{1}\)，\(x_{2}\)，$ t_{0} $。 这是一个简单的数学推理题。我们需要找到两个龙头的流速 \(y_1\) 和 \(y_2\)，使得满足以下条件： 最终水温不低于 \(t_0\)； ......

题目描述（翻译） Valera 是大学的本科生。他的期末考试即将来临，他必须要通过恰好 \(n\) 门考试。Valera 是一个聪明的人，他可以在第一次尝试时通过任何一门考试。此外，他可以在一天内考多门考试，并且可以以任意顺序进行考试。 根据考试时间表，他可以在第 \(i\) 门课程上考试的日期是 ......

CF906 div2 A.Doremy's Paint 3 题意 给出一个序列，可以随意打乱顺序，问最后能否使得所有相邻两个元素的和相等。 数据范围 多组数据，\(2 <= n <= 100 , 1 <= a_i <= 10^5\) 样例输入 5 2 8 9 3 1 1 2 4 1 1 4 5 5 ......

容易发现新加的边一定是 \(1\) 到某个深度大于 \(i\) 的节点。 考虑每次摧毁深度小于等于 \(i\) 的节点，如果有多个连通块，那么对于 \(b\) 不在的连通块答案是不会变的。 所以如果有两个及以上的连通块中最深的节点是原树上最深的节点，那么答案一定是这个深度。 考虑倒过来从深度大的开始 ......

容易发现分配给一个子树的钱只要够了就会移除 具体来讲，如果一个结点被分配到了 \(x\) 块钱，那么有两种情况： 子树全部都拿到了该拿的钱，自己拿到了一部分或者全部拿到了 对于每个儿子，其子树拿到的钱均不超过某个值 对于情况 1 容易构造使其不发生，对于情况 2 可以每次二分。 \(O(n^2\lo ......

CF1662F 遇到绝对值想想拆开。 考虑优化 bfs 时扩展过程,设当前点为 i,考虑 i,j 连边。 |\(i-j\)|\(\leq\) \(\min(p_i,p_j)\),则 j 至少应该在 [\(i-p_i\),\(i+p_i\)]。 分类讨论一下 \(j\geq i\) 时 \(j-i\l ......

怎么会有这么离谱的题目啊。 【模板】前缀和优化 dp。 思路 考虑一个基本的东西。 由于要求字典序的限制。 我们可以枚举最长公共前缀计算。 考虑如何求长度为 \(i\) 的排列有 \(j\) 个逆序对的数量。 设 \(dp_{i,j}\)。 \[dp_{i,j}=\sum_{k=0}^{i-1}dp ......

The Shortest Statement 给一张 \(n\) 个点 \(m\) 条边的无向连通图，保证 \(m - n \le 20\)，\(q\) 次询问求两个点间的最短路。 \(n, m, q \le 10^5\)。 由于边数只比点数多 20，所以如果我们建出这张图的一棵生成树，那么非树边至 ......

传送门 description 给定 \(n,k,f\)。规定一个由长度为 \(n\) 的 01 串组成的多重集是合法的，当且仅当对于所有长度不超过 \(n\) 的非空 01 串（有 \(2^n-1\) 个）\(s\)，有 \(p_s\leq c_s\)。其中，\(p_s\) 是 \(s\) 在多重 ......