AT 水题乱做

以每周一开始，每周日结束为一个计数周。

做的都是一些水题。希望自己能好好努力吧，不努力就退役了。

2024.10.21-2024.10.27 ​

while (true)
  puts("CSP RP++");

ARC164D - 1D Coulomb ​

题意比较复杂，但是梳理完之后其实并不困难。

大概是说若 $s$ 是一个 $+$ 和 $-$ 组成的字符串，定义 $p(s)$ 是这个字符串有关的一个问题的解。给定一个某些位置是 $?$ 的字符串，求可能的 $p$ 之和。

乍一看比较困难，但是认真梳理一下，发现每一个点的方向是确定的，点 $i$ 的方向为右等价于其左侧同色个数大于等于异色个数。再发现向右的点对 $p$ 的贡献是 $-i$，向左是 $i$，那么直接 DP 就可以了。设 $f_{i,j}$ 表示前 $i$ 个位置填完了，有 $j$ 个点是 +，的答案，设辅助 $g_{i,j}$ 表示方案数。

https://atcoder.jp/contests/arc164/submissions/59132037

ARC167F - Bracket Sequencing ​

😃

给 $n$ 个括号串，求是否能重排之后拼起来形成合法括号序。

很显然是贪心，但是刚开始做的时候不加证明，直接 WA 了 3 发，浪费了很多时间。最后看了洛谷题解。

首先，同一个串内，如果有 () 可以直接消除。那么每个串都形如 )))((( 的形式，即一段前缀 ) 和一段后缀 ( 拼起来。

直接贪心，若左括号个数更多，将其放在第一类中，否则放在第二类。那么第一类显然放在第二类左侧。考虑第一类之间，右括号少的尽可能放在左侧；第二类之间，左括号少的尽可能放在右侧。

拼起来之后判一下合法即可。

https://atcoder.jp/contests/abc167/submissions/59133602

ABC249E - RLE ​

感觉挺水的，不知道怎么就评到一千九了。题意是说对于一个字符串，定义压缩形式为字母加重复次数。例如 aaaaabbbc 被压缩为 a5b3c1。

求有多少个长度为 $n$ 的字符串满足其压缩之后长度不超过 $n$。要求 $O(n^2)$。

一看就是直接 DP，暴力 DP 设 $f_{i,j}$ 表示原串和压缩串长度，前缀和优化一下就好了。

https://atcoder.jp/contests/abc249/submissions/59139939

ABC297F - Select Edges ​

😃

题意：给定一棵树，边有边权，点有点权。要求选出任意条边，使得每一个点相连边中选中的边数量不超过点权，求最大选中边权和。

唐了，写了一个假的 DP，直接寄飞了，做了一个半小时破防了。

设 $f_{i}$ 表示点 $i$ 与父亲相连的边选，$g_i$ 表示不选的最大贡献。转移时先考虑从 $i$ 到儿子的边全部不选，则 $f_{i}=g_{i}=\sum f_{son}$，再考虑是否要选择到儿子的边。如果选中一条边，那么贡献为 $g_{son}+w(i,son)-f_{son}$，将其排序后选择即可。

https://atcoder.jp/contests/abc259/submissions/59141206

ABC348F - Oddly Similar ​

今天很颓，只是为了保持 Streak 才做这题。

这题洛谷评分是黄，题意是说给 $n$ 个序列，每一个长度为 $m$。如果两个序列同一个位置的值相同，称这个位置是好的，如果好的位置数量是奇数，那么称这两个序列是好的。求 $n$ 个序列两两能够组成多少个好的序列。

$1\le n,m\le 2000,1\le a_{i,j}\le 999$

这个数据范围很奇特，正解是 bitset，看了洛谷题解，发现暴力用位运算，不用 if，交 clang 或者开火车头可以过，就没有写 bitset。

https://atcoder.jp/contests/abc348/submissions/59213329

2024.10.28-2024.11.03 ​

AGC050C - Tree Restoring ​

非常好的题目。

题意：需要判定是否存在一棵树，满足点 $i$ 到其最远点距离为 $a_i$。

$1\le n\le 100$

这个数据范围极具迷惑性，因为这题做法是线性的。最远点首先想到直径，假设直径长度为 $d$，那么，$\lfloor \frac{d+1}{2}\rfloor$ 到 $d$ 是直径上点的 $a$ 的范围。计算每一个值的出现次数，若出现了小于 $\lfloor \frac{d+1}{2}\rfloor$ 的必然不合法。中间的两个点的出现次数需要特判，其余点不得少于两个。

https://atcoder.jp/contests/agc005/submissions/59250106

ABC214F - Substrings ​

水题。

题意：对于一个串 $S$，求其本质不同的子序列 $T$ 的数量，满足其组成位置在 $S$ 中不相邻。

$1\le n\le 2\times 10^{5}$。

容易想到 DP，设 $f_{i}$ 表示子序列最后一个位置选择了 $i$ 的方案数，考虑会算重，将 $f_{i}$ 减去所有 $j<i$ 的 $f_j$ 即可，前缀和优化。

https://atcoder.jp/contests/abc214/submissions/59250914

ACL1C - Moving Pieces ​

才发现自己很久没有碰过网络流了。

题意：给定一个棋盘，上面有障碍和棋子，要求不经过任何障碍，不出界，同一个格子同时只能有一个棋子，每次可以将棋子向右或是向下移动一步。要求最大移动次数。

$1\le N,M\le 50$。

完全没想到可以网络流，注意到这是费用流之后题目变得很简单了。每一个点向其能走到的点连一条费用为 $-1$，流量无限的边，跑费用流即可。

https://atcoder.jp/contests/acl1/submissions/59252262

本周 3 / 10 又没有完成目标。还不是因为不够努力。

2024.11.4-2024.11.10 ​

ABC377F - Avoid Queen Attack ​

VP 的一道题。

题意：给定一个 $n\times n$ 的棋盘，上面有 $m$ 个皇后，每一个皇后的攻击范围是上下左右对角线，问有多少个位置不会被任何皇后攻击。

$1\le n\le 10^{9},1\le m\le 3000$

每一个皇后的攻击可以表示为四种直线，每一条直线覆盖的位置数量很容易计算。但是会有重复计算的。

将这些直线去个重，每一种直线内部互相平行，一定不会重复覆盖一个格子。任意两种不同直线只有一个交点。

枚举两条直线，计算交点。用 map 存下每一个交点被计算次数。若一个点，

• 被计算 1 次，说明有两条直线覆盖了这个点。

• 被计算 3 次，说明有三条直线覆盖，即，$\binom{3}{2}$。

• 被计算 6 次，说明有四条直线覆盖。

https://atcoder.jp/contests/abc377/submissions/59460081

AGC059A - My Last ABC Problem ​

猜和推结论的能力太差，观察不够仔细，注意力不够集中。

题意：给定一个仅由 ABC 构成的字符串，每一次操作可以将一段区间中的 ABC 按照某一个排列轮换。有 $Q$ 次询问，每一次问至少多少次操作将这段区间全部变为全部相同。

$1\le N,Q\le 10^{5}$。

解法：连续一段相等的称为一段。考虑每一次操作，至多只能减少两个段（不知道证明）。当 $N\ge 5$ 时可以找到一种操作方式使得达到这个上界。当 $N=4$ 时需要两次操作，$N=3$ 时，若两端相等，只要 1 次，否则要两次操作。

VP AGC037 见 AT 总结 ​

ARC153C - ± Increasing Sequenc ​

非常好的构造题。

题意：给定一个长度为 $N$ 的序列 $a_i$，$a_i\in \{0,1\}$，需要构造一个 严格递增 序列 $b_i$，满足 $\left | b_i \right | \le 10^{12}$，并且 $\sum_{i=1}^{n}a_ib_i=0$，或者报告无解。

做法：调整。首先钦定 $b_i=i$，可以得到一个和 $S$。若要保证 $b$ 序列递增的性质，必定要调整 $b$ 序列的一个前缀减或后缀加。

例如 $S>0$ 时，可以找到 $a$ 的一个前缀和为 $1$ 的区间，将其区间减 $S$，或是找到一个后缀和为 $-1$ 的区间，将其区间加 $S$。这样必定是充分的。

如果找不到，就是无解。因为 $a$ 的前缀和是连续的，若存在一个前缀和大于 $0$，则必然存在前缀和等于 $1$。若不存在前缀和等于 $1$，说明前缀和均为非正数，无论如何操作，都不能使得前缀和减小，故必要性得证。

Submissions

ABC239F - Construct Highway ​

题意：给定一个 $n$ 个节点，$m$ 条边，要求补充 $n-m-1$ 条边，使得图变为一棵树。给定每个点的度数，给出构造方案或报告无解。

卧春，这题都不会了。

想到可以用并查集维护联通信息，每一次找两个未满足条件的一个连通块中不满足条件的点连起来。

但是这样会有问题，具体来说，样例过不了。

事实上，问题出在只有一个点度数和需求相差一的连通块上。假设现在有三个连通块，有两个与要求相差 1，有一个相差 2，可能前两个连通块相连了，整个图就不连通了。

所以每一次相差 1 的块要尽可能和相差大于 1 的块连接。如果没有相差 1 的块，则无解。如果没有相差大于 1 的块，就要求相差 1 的块恰好有两个，否则无解。

无解情况真多。

submissions

ABC200E - Patisserie ABC 2 ​

题意：定义一个三元组 $(i,j,k)$ 的排序方式为：以 $i+j+k$ 为第一关键字，$i$ 为第二关键字，$j$ 为第三关键字。求所有 $1\le i,j,k\le N$ 的三元组中，排名为 $K$ 的。

$1\le N\le 10^{6},1\le K\le N^{3}$

做法：很容易想到插板法，但是可能出现大于 $N$ 的情况，需要容斥一下。

没想到容斥就开始写，输麻了。

submissions

ARC075E - Meaningful Mean ​

这大水题吧。

题意：给一个长度为 $N$ 的序列 $a$，求有多少个区间的平均值不小于 $K$。

$1\le N\le 2\times 10^{5}$

平均值，直接将 $a_i$ 减去 $K$，问题转化为多少个区间满足区间和非负。考虑固定右端点，对左端点计数。左端点需要满足前缀和小于等于右端点的前缀和，这是一个二维数点问题。

submissions