题解wag-quaternary quaternary balance

UPD 23.10.3 更新的对思路的描述，以及代码。 思路 对于每一个 \(a_i = 0\)，如果我们将它变为 \(x\)，都可以直接将 \(i \sim n\) 位置上的前缀和加 \(x\)。 设 \(a_j\) 是 \(a_i\) 后第一个 \(0\)，那么，在 \(j\) 时同样有上述规律 ......

原题链接 解题思路 如果直接按照题意开一个二维数组来模拟每个点最上面的地毯编号，会发现所占空间最坏情况下约为 (2*105)2*4B=4*1010*4B=1.6*1011B≈149GB，程序完全无法运行。 但实际上没有必要将每一个点的信息记录下来，只需要记录每一块地毯能覆盖哪些点，再依次判断哪那些地 ......

题目链接 本题解讲解环图的做法。 要将一个 \(1\sim n\) 的排列通过交换变成 \(1\sim n\)，可以先将 \(i\) 向 \(a_i\) 连边，那么最终一定会练成若干个环（每个点只有一个出度，也只有一个入度）。 假设交换在同一个环中的节点，一个环显然会变成两个环，也就是说，交换一次最 ......

A. Gift Carpet Problem 题目 Sol & Code 签到题 #include <bits/stdc++.h> #define N 21 typedef long long ll; int min(int a, int b) { return a < b ? a : b; } i ......

T2回家(home) 现在啥也不是了，虽然会了逆元，但是对期望概率题还是一窍不通，赛时相当于只推出了 \(n=1\) 的情况，结果运用到所有情况，理所应当只有20分。 题目描述 小Z是个路痴。有一天小Z迷路了，此时小Z到家有NN个单位长度。小Z可以进行若干次行动，每次行动小Z有 \(\frac 1 ......

前置芝士 排列组合 分析 明显的贪心，第一问与此题思路相似，优先选择做时间少的，可以尽可能让后面的罚时尽量的小。 难点在第二问，第二问问的是有几种可能性，有个显然的结论： 相同做题时间的题目，位置调换答案仍然相同。 那么可以用 桶+排列组合 来解决： 用桶储存这个做题时间的出现次数 \(b_i\)， ......

# 思路 简单动态规划，$dp_i$ 指当前操作后取和为 $i$ 的球的方案数，每次输出 $dp_K$ 即可。 需要注意的是对于每次 `+ x` 操作，计算 $dp$ 数组时要倒着循环。 时间复杂度：$O(QK)$。 # 代码 ```cpp#include<bits/stdc++.h>using n ......

正文 这是样例 1 第 1 组数据的图。 让我们观察一下，路径 1->6、1->7、2->6、2->7 是可行的，所以答案为 4。 上述路径中好像点 4 没有贡献？ 再看看样例 1 第 2 组数据的图。 发现点 1 和点 4 相互之间存在其他路径，无需经过点 \(a\) 和点 \(b\)。 综上，我 ......

题目大意 有 \(n\) 个桶， \(m\) 次操作。 在 \(pos\) 桶中加入一个 \(val\) 值， 求 \([l,r]\) 中选任意个桶使得异或和最大，求最大的异或和， 注意每个节点是一个桶可以放多个值 \(n,m≤5×104\) 。 题目思路 单点修改，区间查询，异或最大值 很显然是线 ......

题解 \(dp[i]\) 表示长度为i的格子的合法涂色数，考虑第 \(i\) 个怎么放 第 \(i\) 个前面 \(k-1\) 个位置有2种颜色，则第 \(i\) 个位置只能放这两种颜色中的一种 用合法方案减只有一种的方法，即得两种颜色的方案数 而只有一种颜色的方案数，等于 \(f[i-k+1]\) ......

这是一个只用最大流的做法。 思路 首先发现一个性质，除了 2 以外的所有质数都是奇数，而奇数 = 奇数 + 偶数，所以大多数情况下只能一奇一偶配对，唯一的特例是 \(1+1=2\)。 考虑先处理大于 1 的所有数的配对，对于所有 \(a_i + a_j\) 为质数的 \((i,j)\) 连边，由于合 ......

考虑 DP，设 \(f_{i,j}\) 表示在前 \(i\) 个盒子放 \(j\) 次球的所有方案得分之和，得到转移式： \[f_{i,j}=\sum\limits_{k=0}^{j}{j \choose k}f_{i-1,k}(a_i+j-k)\\ \]发现这个转移式简直是为 EGF 量身定制，于 ......

这是一个没有必要的复杂做法，但我考场上第一时间想到的就是这个做法。 分析 首先观察样例。发现答案有对称性，所以我们只需要求出 \(\left[2,k+1\right]\) 区间内的答案。又发现相邻两项答案是一样的，所以只需要处理其中奇数情况的答案。 推式子 设 \(f_s\) 表示点数和不为 \(2 ......

题意 给定一个长度为 \(N\) 的环，每次选取环上一段并使其中每个元素值均加 \(1\)。给定一个长度为 \(N\) 的序列 \(A\)，环上元素初始值为 \(0\)，求将环变为序列 \(A\) 的最少操作次数。 （\(1 \le N \le 2 \times 10^5, 1 \le A_i \l ......

此题是极其恶心的大分类讨论。 结论 首先我们可以发现一个重要的结论，在用两镖只打数字的情况下，可以拼出 \(0\) 到 \(5k\) 中除了 \(5k-1\) 的所有值，以及 \(0\) 到 \(6k\) 中一些不连续的 \(3\) 的倍数。 证明： \(0\) 到 \(5k\) 中 \(5k-1= ......

来个不一样的做法：扫描线，线段树上二分。 思路 我们发现只需找到小球落到每个挡板后的下一个挡板，就可以建出一张 DAG，在 DAG 上简单 DP 即可求方案。 所以我们考虑怎么建图。 大多人用扫描线是从下到上扫描的，但我们考虑从左到右扫描。 我们在挡板左端做加入操作，右端做删除操作，对于扫描中每一个 ......

题意 若非负数列 \(A\) 中任意 \(i(2 \leq i \leq N-1)\) ，都有 \(2A_i \leq A_{i-1} + A_{i+1}\)，则称 \(A\) 为凸数列。 问长为 \(N\) ，且数列中所有项的和为 \(M\) 的凸数列有多少个，答案对 \(10^9+7\) 取模。 ......

可能更好的阅读体验 大家好，我和 DP 有仇，所以我用猜结论的方法过了这道题。 可能是这道题的一个全新思路，可能人自闭久了什么都能想出来（（（ upd：好像这也是官方题解思路，看来大家做题不太喜欢看 CF 官方题解（（（ 首先考虑一个问题：如果这是一道构造题，怎么构造一组合法的解？ 在草稿纸上画了很 ......

决策单调性二分 传送门 数据加强版：P3515 前置知识：二分，决策单调性 首先很容易写出答案式子： \[ ans_{i}=\max_{j=i}^{n}{(a_{j}-a_{i}+\lceil \sqrt{\left| i-j \right |} \rceil)} \]先将向上取整符号拆掉，只要在输 ......

传送门 前排提醒：本篇题解没有使用压位和快速幂，运用了一种预处理的思想，希望能提供一种新的思路。 首先将 \(2^{p}-1(d)\) 转换为 \(1111…111(b)\)。 关于第一问： 我们先考虑 \(2\) 进制转 \(8\) 进制，将每 \(3\) 位转为 \(1\) 位，即每 \(\lo ......

传送门 题目大意： 一个 \(n\) 个叶子节点，一个节点最多可以有 \(k\) 条边连向子节点，每个节点 \(i\) 有一个权值 \(P_{i}\)。记每个节点子树内点的个数（不包括它自己）为 \(son_{i}\)，那么每个节点对答案的贡献就是 \(son_{i}^2 \times P_{i}\ ......

传送门 首先可以将题意大概可以简化为：取两端不重复的连续子序列，组成一个最长的连续递增子序列。 我们先 dp 预处理出以 \(i\) 为结尾的连续递增子序列长度 \(dpr_{i}\)。 同样预处理出以 \(i\) 为开头的连续递增子序列长度 \(dpl_{i}\)。 考虑对于每个 \(dpr_{i ......

题解 Codeforces Round 901 (Div. 1) / CF1874A~E 比赛情况：过了 AB。赛后发现 B 是假复杂度。 https://codeforc.es/contest/1874 A. Jellyfish and Game Problem Alice & Bob 又在博弈， ......

思路 题目要求的是 \(\max_{a = 1}^{n}\{\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\}\)，所以我们将 \(\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\) 化简一下，得： \[i \times A_1 + (i - ......

思路 首先我们可以发现，在任意一个节点数量大于 \(1\) 的强连通分量中的点都满足条件。 所以，我们可以对这张图跑一边 TarJan。 但是这样是错的，因为我们还需要考虑节点数量为 \(1\) 的强连通分量。 如果这种连通分量能够到达任意一个节点数量大于 \(1\) 的强连通分量，那么，这个连通分 ......

题意 传送门 有一个长度为\(n\)的歌单，问最长多少首歌互不相同？ 每首歌用一个\(1-10^9\)的整数表示。 样例输入 8 1 2 1 3 2 7 4 2 样例输出 5 算法 双指针算法。桶思想。 对于歌单中重复出现的数，可以用桶来存储。 定义两个指针i,j，i指向大数，j指向小数。当出现某个 ......

题目链接 先将所有作业按位置排序。 直接贪心显然是不行的，因为我们没有办法确定对于一个时间较久的作业，是在原地等待，还是在未来的某个节点返回，并且无法确定是那个节点，所以只能考虑 \(dp\)。 对于此类可以倒来倒去的问题，通常考虑区间 \(dp\)，若设 \(f_{i,j}\) 表示完成区间 \( ......

题目传送门 简化题意 有 \(t\) 组询问，每次询问是否能从 \(1 \sim n\) 中选择 \(k\) 个数使得它们的和为 \(x\)。 解法 考虑临界情况，从 \(1 \sim n\) 中选择最小的 \(k\) 个数时和为 \(\sum\limits_{i=1}^k i=\dfrac{(k+ ......

题目大意 题目大意 给定一个 \(n\) 个点和 \(m\) 条边的有向图，并给定 \(p_1, p_2, \cdots, p_n\) 表示第 \(i\) 个点的拓扑序必须小于等于 \(p_i\)，求出每个点的最小拓扑序。 题解 题解 题目要求拓扑序尽量小，转换一下就是在反图上拓扑序尽量大。考虑拓扑 ......

好可恶一道题，怎么没人告诉我输出之间有空行（ 思路是先抽象成图，然后跑一边dfs记录边的前后顺序。 对于不能成环的情况，只需要再开个数组记录度数判断奇点即可。 若存在奇点则break掉，剩下的跑dfs、 //produced by miya555 //stupid mistakes:1.多测要清空 ......