题解at_abc 321 abc

P4115 看到单点修改，求全局白色的最远距离，可以使用点分树。 考虑维护这棵点分树，想想树的直径的 dp 求法：\(f_u = \max\{f_v + w(u, v)\}\)，答案为 \(\max(f_v+f_{v'})(v,v'\in \{\text{son}_u\})\)，\(\{\text{ ......

\(\text{Links}\) [ABC259Ex] Yet Another Path Counting Luogu Blog 题外话 淀粉质题单做不动了怎么办？来做一道根号题振奋一下精神吧/se！ 我要饿死了，我要吃饭，以后在学校还是不要不吃早饭了/kk 题意 给一个 \(n\times n\) ......

计算几何 Link UVA 11178 Morley's Theorem Question Morley 定理是这样的，作三角形 ABC 每个内角的三等分线，相交成三角形 DEF，则 DEF 是等边三角形 给出 \(A,B,C\) 坐标，求 \(D,E,F\) 坐标 Solution 其实是一道计算 ......

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

[ABC180F] Unbranched 题面翻译 求 \(N\) 个点，\(M\) 条边且满足以下条件的图的数量： 图中无自环； 每个点度数最多为 \(2\)； 连通块大小的最大值恰好为 \(L\)。 答案对 \(10^9+7\) 取模。 \(2\le N\le300\)，\(1\le M,L\l ......

https://earthshakira.github.io/a2oj-clientside/server/Ladder32.html 只记录 Difficulty level >= 8 的。有很多题是口胡的。写了的会标注提交记录。还有些很久以前写过的题就懒得搬提交记录了。任何的 * 都表示该段的后 ......

怎么其他两篇题解都是 \(O(n\log n)\) 的，来发一个 \(O(n)\) 做法，当考前复习了。 对原序列建出小根笛卡尔树，节点编号与原序列中的下标相同。记 \(T_u\) 表示以 \(u\) 为根的子树，\(lc(u),rc(u)\) 分别表示 \(u\) 的左儿子和右儿子。 设 \(f_ ......

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

先考虑将原序列差分一下，事实上，我们对于这类每次可以操作一个区间减去固定值的时候，我们一般都需要差分，因为差分后，我们的操作实际上相当于 **在差分序列上修改两个点**，这个时候的问题是好考虑的。 这时候问题转化为，我们每次可以选择两个距离恰好为 $k + 1$ 的点，将 $l$ 加上 $w$，将 ......

B - 3-smooth Numbers 难度: ⭐ 题目大意 给定一个数字n, 问是否可以找到两个数x和y, 使得 n = 2x3y; 解题思路 因为n的范围最大到1e18, 所以只需要暴力找x和y即可; 神秘代码 #include<bits/stdc++.h> #define int long ......

题意 给定 \(N\) 个带有若干洞的节点，其中第 \(i\) 个点上有 \(d_i\) 个洞。 先可以在两个不同的节点的洞之间连边，一个洞最多连一条边，求使得最终形成的图是一棵树的方案数，对 \(998244353\) 取模。 洞之间相互区分，两个方案不同当且仅当存在一条边在两个方案中的连的洞不同 ......

blog。很 naive 的题，写这篇题解，主要是现有题解都用的线段树 / 平衡树，让我感到很难绷。 一眼 DP。\(dp_{i,j}\) 表示前 \(i\) 个宿舍，现在有连续 \(j\) 个灯亮大于 \(B\)，方案数。 \(dp_{i,0}=\max(\min(B, r_i) - l_i + ......

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

https://atcoder.jp/contests/abc280/tasks/abc280_f 对于每一个连通块单独处理，首先判断是否全为0环，可以用bfs判断。 从一个点出发计算其他点到它的最短距离，如果存在一个不唯一，说明存在非零环。 然后计算距离的时候直接-d[x]+d[y]即可 #inc ......

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

目录DescriptionSolutionCode Description 在一个教室里有 \(n\) 排座位，每排有 \(6\) 个，从左至右标号分别为 ABCDEF，其中 C 和 D 中有过道，通往教室前端和后端的两个房间，每个房间最开始没有人,每个座位上开始都有人。 有 \(m\) 个不同的学 ......

Day 1 kitty 核心思路：将转移过程中的方案加入转移矩阵，边转移边累加 string dp设计：\(f[i][x][y]\) 表示长度为 \(i\)，第一段以 \(x\) 结尾，且 \(x\leqslant p\)，第二段以 \(p\) 开头，以 \(y\) 结尾的两段完全相同的序列的对数。 ......

原题链接 \(b\) 的顺序与答案无关，先排序。能与 \(a_i\) 配对的肯定是 \(b\) 的末尾一段，因为 \(a_i+b_j\ge h\)，那么一定有 \(a_i+b_{j+1}\ge h\)。 设 \(c_i\) 为与 \(b_i\) 配对的 \(a\) 的个数，显然 \(c\) 是单调不 ......

原题链接： 洛谷 $\ $ AtCoder 如果你觉得 \(O(n)\) 没有跑到极限的话，你可以试试整除分块。 先来化一下式子： \[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\;[i\bmod j\ge k] \]\[\sum\limits_{i=1}^n\su ......

题目链接 依然枚举每个位置作为最小值的情况，记录“值/下标”二元组，按第一维从大到小排序后，每次将第二位的位置在序列中标成 \(1\)，那么选择的一定是序列里一个 \(1\) 的极长段。加入一个位置检查其左右是否加入过，如果加入过就用并查集合并掉，同时维护极长段的和/左右端点是简单的，复杂度 \(\ ......

[NOIP2022] 建造军营 题解 Part I 观察 注意到如果删掉的边在一个边双连通分量里面，那么无论如何都不会影响 A 国，所以 B 国只会删掉桥，于是把图边双缩点之后，同一个边双里面的点要么都不选，要么随便选至少一个。 Part II DP 再次发现军营一定是一个极大的连通块，所以可以考虑 ......

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

### 题意 给出一串数，请尝试在这串数中找到三段**连续**的子段，使得这三个子段的和分别为 $P$、$Q$ 和 $R$。问：是否可行？ ### 思路 通过观察，观察我们可以发现，其实我们可以根据题目的要求写出一段关系式： $A+P+Q+R+B$（其中 $A$ 表示被选子段前面没被选的子段和，其中 ......

这道题的思路非常简单，经过对样例的分析，我们发现，所有区间的总和为： $\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 ......

这个小丑看了好久题目才发现保证 \(t\) 不降。 好像与其他题解做法稍有不同。 思路 其他题解的标记做法非常复杂，怎么办。 我们可以使用适用性可加强大的矩阵乘法。 我们考虑维护： \[\begin{bmatrix} \sum v&\sum a\times b&\sum a&\sum b&len\\ ......

https://atcoder.jp/contests/abc327/tasks/abc327_f 我们将时间看作x轴，位置看作y轴，那么我们随着时间增加，维护新加的点对区间的贡献，同时减去过时的点，线段树区间加法维护最大值即可。 #include<cstdio> #include<algorith ......

B - Round-Robin Tournament 难度: ⭐ 题目大意 给定n个字符串, 每个字符串的长度为n; 如果第i个字符串的第j个字符为'o', 说明i在比赛中赢了j, 如果是'x', 则是j赢了i; 最后按照赢比赛的数量从多到少进行排序; 解题思路 暴力即可; 神秘代码 #includ ......

题意 给你一个数组 \(a1,a2…an\) 请计算有多少个四元组 \((i,j,k,l)\) 符合以下条件: \(1 <= i < j < k < l <= n\) \(a_i=a_k \ \&\&\ a_j=a_l\) \(4<=n<=3000,1<=a_i<=n\) \(input\) 2 5 ......

题目链接 题意简述 给定一个正整数 \(N\)，将它的因数分解式按规定输出。 题目分析 模拟题意即可。 具体地，我们可以枚举 \(2\) 到 \(\lfloor \sqrt N \rfloor\) 中所有数 \(i\)，如果 \(i\) 能整除 \(N\)，则不断地从 \(N\) 中除掉 \(i\) ......