A - Villages: Landlines 题意简述，给出一些区间，求取最多添加多长的区间使得这些区间合并。 非常简单，按题意模拟即可。 #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<pair<int, int>> v(n); for (auto &[x, y] : v) { int...

Promising String 题意 给出一个仅仅包含'+' '-'的字符串，我们可以将两个连续的'-',合并为'+'。 求其所有子串经历变换后 '+' 的数量等于 '-' 的数量的个数。 思路 假若，我们有一段连续的序列了，其中有 x 个 '+' , y 个 '-'。 那么我们如果想要成立的话，那么我们需要以下几个条件成立。 y >= x x + k = y - k * 2 即 y - x = 3 * k 也就是说，我们只需要 (y - x) % 3 = 0 情况下的答案。 首先，如果，我们用 -+ 把所有的 + 排完。那么我们就得到 k >= (y - x) / 2。而...

ICPC 46th nanjing D Paimon Sorting 题意 如下所示的循环中 for (int i = 1 ; i<= n ; i ++ ) { for (int j = 1 ; j <= n ; j ++ ) { if(a[i] < a[j]) swap(a[i] , a[j]); } } 对于给定序列 A[N]A[N]A[N] 分别求其前缀 [1 , N] swap的次数 思路 我们不妨观察以下我们的序列。 首先，对于第一次循环。 我们会发现，我们将找到所有刚好比上一个最大值大的那个数。 然后我们第一次循环就是把最后一个...

C. Klee in Solitary Confinement 题意 给出一个数组，我们可以选择一段区间加上 k (或者不加)。求出现次数最多的数出现了几次。 思路 对于一段区间加上 k 的话。 我们不妨考虑最多的数为 a[i] + k 的情形。 我们敲定区间 [L , R] 我们最优的方案一定是刚好 a[L] = a[R] = k。这很容易想出，因为只有这种情况下，我们才可以保证 L 左边的和 R 右边的 a[i] + k 没被改掉。 我们不妨用 cnt[i] 表示区间 [1 , i] 内 a[i] 出现的次数，ckt[i] 表示区间 [1 , i] 内， a[i] + k 出现的次数。 ...

SP3267 D-query 题意 给出一段序列。求取区间范围[l,r] 中的序列出现的次数。 思路 足够详细的博文 这个题目最好的方法是采用前缀和的方式离线查询。 不过，为了学习莫队算法，这个题目主要用来讲解莫队算法该如何工作。 首先，我们对于区间 [l,r] 的查询，由于我们可以通过改变区间的方式进行不断的增大减小。 所以我们不妨开出来两个指针 l \ r 用来表示当前的区间，另外设置一个数字来表示当前的答案是多少。 每次查询的时候我们通过移动指针来更新答案。 由于我个人比较习惯闭区间的各种写法，因此我初始化区间为 [0 , -1] 。即 l = 0 , r = -1 表示空区间。 对于每...

G - Range Pairing Query 题意 有 n 个人站成一排，每个人的身上都有一个数字 c。求问区间 [l,r] 范围内共有多少个颜色一样的对。 思路 这题大概是一个裸的莫队 采取另外一种方法。 首先，我们采取离线的方式进行写题。 我们通过前缀和的方式进行更新我们的答案，并且我们的前缀和 pre 表示 pre[l] 表示区间 [l ,i] 上的答案位多少。 假如我们更新到了 i = 10 。并且 pos[] = [1 ,3 ,4 ,7 ,9] 。 假如我们将 i = 10 添加进去的话，那么如下几个区间的答案被更新了。 [8,9] | [4,4] | [2,3]。 因此我们可以得...

D. K-good 极为简单，却未能想出。重点记录 题意 给定一个整数 n 求是否能够用 kkk 个模 k 不同的数组成一个该数。 思路 我们发现对于这 n 个数而言，可以简单的缩略成一个式子。 n=ks+k∗(k+1)22×n=k×(k+2s+1)n = ks + \frac {k*(k + 1) }{2} \\ 2 \times n = k\times(k + 2s + 1)n=ks+2k∗(k+1)​2×n=k×(k+2s+1) 我们发现等式的右边变为两个数，一个是 k 另一个是 k 加上一个奇数。也就是说，可以将 2n 划分为 一个偶数×奇数的情况。 不难想到，如果我的 n 是一个...

D. For Gamers. By Gamers. 记录一下今晚状态极差的比赛。 思路 我们首先以 t 为时间线划分。士兵如果要打败怪物，kd×t≥Hkd\times t \ge Hkd×t≥H 。同理，怪物要打败士兵则需要D×t≥hD\times t\ge hD×t≥h。 我们发现都有共同的 t。不妨以 t 作为划分依据得到，hD≤t≤Hkd\frac h D \le t \le \frac H {kd}Dh​≤t≤kdH​。 然后我们省去 t 发现。 khd≤HDkhd\le HDkhd≤HD，而我们的目标是 min⁡kc\min kcminkc。 由于刚好消灭掉的时候不算。因此，等号...

P5904 [POI2014]HOT-Hotels 加强版 题意 求在一个树内有多少个三元组(i,j,k)(i,j,k)(i,j,k)满足 dis(i,j)=dis(i,k)=dis(j,k)dis(i,j)=dis(i,k)=dis(j,k)dis(i,j)=dis(i,k)=dis(j,k) 思路 假定，我们对于所有的三元组都处理成如下图所示的模样。 其中 I B K J 都是 点 A 的子树。 我们定义如下的变量。 F[u][i] --> 表示在点 u 的所有子结点中到达点 u 长度为 i 的个数。 G[u][i] --> 表示如上的二元组,连接到的中心节点 B 到达点 A...

Strange Fractions 题意 在规定的范围内求解整数 a , b 满足 ab+ba=pq\frac a b + \frac b a = \frac p qba​+ab​=qp​ 思路 这个题目让我来做的话，可能就暴毙了。 首先我们来看几个对这个题目而言很重要的性质。 ppp qqq 假设互质，那么原来的输入总可以考虑为 k×q=q′k\times q = q'k×q=q′ k×p=p′k\times p = p'k×p=p′。 总可以证明成功。 aaa bbb 假设互质，如果 a′=k×a,b′=k×ba'=k\times a, b'=k\times ba′=k×a,b′=...

H Life is a Game 思路 该题采用kruskal重构树。 kruskal 重构树的特点是将边权化为点权。 当我们使用kruskal求取最小生成树的时候，我们不需要直接生成该树。 每次，我们得到两个点的时候，我们将其连成边时，我们只需要将这棵树两个点提出来，然后我们新加上一个点，且该点的权值是我们原来的边权。 如图所示，我们加边的过程如下。 倘若我们再加一条从 B <--> C 相互连接的边的时候。使用如下图所示的方法加边即可。 c" src="https://uploadfiles.nowcoder.com/images/20220316/738444583_16...

read it on blog P5903 【模板】树上 k 级祖先 题意 给定一棵树，我们要求 x 的上 k 级祖先。 思路 由于该题为长链剖分的模板题，因此重要介绍一下，长链剖分。 对于一棵树，我们的长链剖分和重链剖分，我们对每个链取最长的那条链作为我们的重链。如上图所示，我们可以把这棵树拆成一个一个链。为了方便画图，我把这颗树位置变换了一下。 如上图所示，我们重构后的树就如其所示，我们不难发现这棵树有一个特点。对于所有的链而言，如果我将重链继承下来的话，那么我们通过不断合并，那么我们可以做到 O(N)O(N)O(N) 的时间复杂度将我们的答案统计完，因此，对于所有可以顺序继承的题目而...

P3647 连珠线 题解 题意 我们有 n 个珠子，我们可以选择一枚珠子作为我们的起点。然后我们可以选择用红线将新珠子与已有的珠子连起来，或者在用红线连起来的两个点间加入一个点，并将红线替换为两个蓝线。 蓝线的长度即为我们的分数，求最大得分。 思路 首先我们任意选取一个节点作为根。 那么一定会出现下图所示的的状况。 那么对于一个节点我们有两种情况，要么是两个蓝线的终点，要么不是，那么因此我们用 F[u][0/1]F[u][0 / 1]F[u][0/1] 来表示。 其中 0 表示不是中点，1表示是中点。 那么我们的答案就可以像下面这样的更新，假设点 vvv 为点 uuu 的子节点，lenlen...

ABC238F Two Exams 题意 在一个地方有 NNN 名考生，共参加了两次考试两次考试的排名分别为 Pi QiP_i \ Q_iPi​ Qi​ 。现在要求选出 KKK 名考生，使得这 KKK 名考生中不存在某位考生的两次排名 (Pi,Qi)(P_i , Q_i)(Pi​,Qi​) 都比某位未选上的考生的两次排名(Pj,Qj)(P_j,Q_j)(Pj​,Qj​) 低。 思路 对于该题目我们不妨将这些排名按照第一关键字为 PiP_iPi​ 第二关键字为 QiQ_iQi​ 排序。 我们发现如果在后面的考生想要参选，那么依照我们的排序规则我们已经知道了 Pi<PjP...