题解wag-quaternary quaternary balance

题如其名，确实挺经典的。 我们称边权在输入中给定的边为特殊边，其它边为平凡边。称特殊边涉及到的点为特殊点，其它点为平凡点。 显然，对于连续的若干平凡点 \([l,r]\)，他们内部的最优连边方式就是连成一条链，花费 \(r-l\) 的代价。我们先把这样的代价加到答案中，然后将极长连续平凡点缩成一个点 ......

LG 任意时刻每个点最多被一条线段覆盖 暴力删每条线段是对的 插入 \([l,r]\) 时需要删除的线段要么被 \([l,r]\) 包含，要么覆盖 \(l\) 或 \(r\) 性质非常强所以做法非常多 一种比较神奇的：对于两条线段 \([l_{1},r_{1}],[l_{2},r_{2}]\)，定义 ......

题解 accoders::NOI 5511【漂亮轰炸（bomb）】 http://47.92.197.167:5283/contest/406/problem/4 BZOJ3252 是弱化版。 problem 一棵树，边带权。\(Q\) 次询问，给定 \(k\) 和一个首都点，选择 \(k\) 条路 ......

显然，询问的答案即为 \(x\) 所在的极长的满足颜色均在 \(\mathbb{A}\) 内的连续段的权值和。如果我们能维护对颜色的单点修改，以及求出某个位置所在极长连续段的左右端点 \(l,r\)，只需要树状数组即可求出答案。 一个朴素的想法是对每种颜色开一棵线段树，单点修改是平凡的，极长连续段左 ......

CF814E 其实是对这篇 题解 的一些理解。 Part 1 不难发现最终图大致长这样： 考虑一棵最短路树，以结点 1 为根，往下每一层有若干个结点，表示最短路距离相同的一些编号连续的结点。 其中每一层内部可以自由连边。 除了每层内部的连边和树边，其余边不合法。 Part 2 考虑第 \(i\) 层 ......

这题一看就不是计算几何，考虑区间 DP。 设凸多边形的 \(n\) 个顶点依次为 \(P_1,P_2,\cdots,P_n\)。 设 \(f_{i,j}\) 在 \(i < j\) 时表示 \(P_i,P_{i+1},\cdots,P_{j-1},P_j\) 组成的多边形的直径的平方，在 \(i > ......

好题。 后面的操作会覆盖前面的操作，这东西不好处理，我们不妨时光倒流，将问题转化为一个位置一旦被填了数，就再也不会变了。如果解决了这个问题，只需将操作序列倒过来，就得到了原问题的解。 显然，所有 \(x_i=y_i=2\) 的操作会最先被执行，所有 \(x_i=y_i=1\) 的操作会最后被执行。只 ......

AtCoder 天下一プログラマーコンテスト2014 本戦 高橋君 题意 给定 \(n, k\)，求 \[\sum\limits_{i = 0}^{k}\dbinom{n}{i} \]多测，\(1 \le n, k, T \le 10^5\)。 题解 可以考虑使用莫队求解，下文讲述如何移动指针。 \ ......

思路 定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程： \[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\} ......

题目描述 给你一个正整数数 \(n\)，问你它是不是多边形数 \(K\)，如果是，设 \(K_1\) 是最小的 \(K\)，\(K_2\) 是次小的 \(K\)，输出 \(K_1\) 和 \(K_2\)。 具体思路 我们主要来看上面这张表里有什么规律。 性质 1：\(1\) 是任何一个多边形数。 性 ......

\(d<n\le 2e5,m\le 10,1\le p\le 10^9,0\le a_i\le 1e9\) 每个位运算之间独立，所以我们可以构造一个 \(\{2^{k-1},2^{k-1}.....\}\) 和一个 \(\{0,0,0...\}\) 的数组，让他们倍增去做如上运算，最后用他们把 \( ......

思路 定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程： \[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\} ......

Typo Descreption 求反转一个不合法的括号序列中的一位使其成为一个合法序列的方案数（保证方案一定存在） Solution 其实也就是一道较复杂的模拟题 先判断哪一类括号数量更多，因为一定是将数量多的括号改成数量少的才有可能变为合法序列，这里就先用左括号举例 记录每个位置时没有配对的左括 ......

题目传送门 本题共有两种方法，分别是递归深搜和动态规划 方法一：递归深搜 Solution 从小到大一一枚举每一个划分的数，。只要找到一种方案就记录，具体细节代码中有注释。 Code #include <bits/stdc++.h> using namespace std; int n,k,ans; ......

A Equalize Prices Again 题解 题目大意 \(n\) 个商品，每个商品价格为 \(a_i\)，求一个最小的价格 \(x\)，使得不亏本（即 \(\sum\limits_{i=1}^n{(a_i-x)}\ge0\)）。 解题思路 输出平均数向上取整（即 \(\left\lceil ......

随机化写法很强，但是这里不说。 这里只记录数据结构写法。 枚举右端点，快速找左端点。 首先一种合法的方案中，一种颜色只会有两种情况。全部在区间中及全部在区间外。 对于区间外的情况，也就是最后一次出现的位置 \(p\) 大于右端点 \(r\)，我们可以维护当前枚举右端点之前的所有颜色非最后一次出现的点 ......

由于太懒了，所以不想（会）写 \(\texttt{A B}\) 和 \(\texttt{F2}\)。 C Common Divisors 题解 题目大意 给定一个长度为 \(n\) 的数列 \(\{a_i\}\)，求 \(\sigma(\gcd\limits_{i\in[1,n]}\{a_i\})\ ......

思路 首先，\(A\) 和 \(B\) 只会移动一个，那么，我们分开来算，我们先假定 \(B\) 会动。 不妨令 \(A\) 与 \(b\) 连边的端点为 \(x,y\)。如果有线段 \(pq\) 能与 \(xy\) 相交，一定满足如下其中一条规律： \(p < x \wedge q > y\) \ ......

首先看到询问有关位运算考虑拆为处理，由于 \(a_i \leq 10^3\) 所以一个数最多有 \(10\) 位。 我们考虑对于一位它的贡献是多少，我们发现第 \(j\) 位一个连续段的异或值为 \(1\) 时会产生 \(2^j\) 的贡献，所以问题转化为快速求所有位上异或和为 \(1\) 的区间个 ......

A Short Sort 题解 题目大意 给定一个长度为 \(3\) 、由 \(a,b,c\) 组成的字符串，问可以不变或交换两个字符是的变为 \(\texttt{abc}\)。 解题思路 由于大小固定，所以预处理可行的字符串（仅包含 \(\texttt{abc acb bac cba}\)）即可。 ......

很妙的性质题！全是意识流证明见过吗？ problem 每次选一个非空边集删掉，谓之曰砍树。砍树后需要满足每个连通块的点权和相同。 在一个方案中可以砍很多次树，都要满足砍树后的要求。一共有多少种合法方案呢？ \(n\leq 10^6,1\leq a_i\leq 10^9\)。 solution 假如我 ......

传奇团子师傅题解（模拟退火） 申明： 本篇题解借鉴了： https://www.luogu.com.cn/blog/SDNetFriend/solution-p7218 这篇博客（主要在bitset部分）。 题意： 给你个矩阵，包含三种颜色，一个美丽串要求你横着或者竖着或者斜着串成一串的三个颜色有特 ......

题目传送门 思路： 设有两个颜色 \(x_1 x_2\) ，两端分别为 \(l_1\) \(r_1\) ， \(l_2\) \(r_2\)。通过观察可以发现，若满足 \(x_1<x_2\) 且 \(r_1 > l_2\) 则 \(x_1 x_2\) 一定是单调不下降的。 那么我们可以先预处理出一个颜 ......

题目链接 对于括号问题，考虑区间 \(dp\)。这道题的括号序列是固定的，所以直接找出每个括号对应的括号在进行转化即可。 设 \(f_{l,r,0/1/2,0/1/2}\) 表示 \(l\sim r\)，左括号不染色/染红色/染蓝色，右括号不染色/染红色/染蓝色的方案数。 若 \(l,r\) 是一对 ......

最详细的题解 题目传送门：Progressions Covering 阅读前人题解时，限于个人能力有限，有一些地方想了好一会儿才懂。发现很多题解都是在 @SDLTF_凌亭风 等作者基础上延伸，但详细程度依旧有限，尽管这篇题解亦是站在他们基础上延伸的，这篇题解更为详细的点明了很多地方。 本人第一次写题 ......

题意 给定一棵由 \(N\) 个节点组成的树，每个节点有黑白两种颜色。定义一个节点 \(u\) 为好的当且仅当路径 \(1 \leftrightarrow u\) 上的节点均为黑色的，反之为坏的。初始情况下所有点均为白色。 定义一次操作为选取一个坏的节点并将其染黑，求将全部节点均染为黑色的期望操作次 ......

题目链接 Power Tree 分析 将叶子节点按dfs序重标号后，每次控制操作可以转化为将子树内叶子节点所在区间加（或减）一个数 不难可以想到将叶子区间进行差分 每次对 \(l\) 到 \(r\) 的操作可以转化为将 \(l\) 上的数转移到 \(r+1\) 上 每次操作后差分数组的和不变 将所有 ......

CF632F - Swimmers in the Pool 题目传送门 题意 给定一个大小为 \(n \times n\) 的矩阵 \(A\) 。假设 \(A\) 满足以下条件，那么称该矩阵为 MAGIC ，否则为 NOT MAGIC ，并输出对应的属性（即 \(A\) 是 MAGIC 还是 NOT ......

和队友一起打的 2023 年广东省大学生程序设计竞赛重现赛，写了 B, D, K，胡了一个 F。 D 题目大意 随着广东的建设与发展，越来越多人选择来到广东开始新生活。在一片新建的小区，有 \(n\) 个人要搬进 \(m\) 栋排成一行的房子，房子的编号从 \(1\) 到 \(m\)（含两端）。房子 ......

题目链接 对于括号题，基本是栈匹配没有匹配的左括号和区间 \(dp\) 两个方向。这道题括号序列并不确定，只能用区间 \(dp\) 搞。 如果直接设 \(f_{l,r}\) 表示 \(l\sim r\) 的合法括号序列，那么由区间 \(dp\) 的套路可知，需要枚举中间点进行合并，那么 \(()() ......