ABC266 ~ 273 题解

标签：10 le 题解 sum ABC266 273 Theta 复杂度 dp

缺省源

#pragma GCC optimize(3) 

#include <bits/stdc++.h>
namespace // to fold that junk code
{
#define filein(x) {freopen(x".in", "r", stdin);}
#define file(x) {freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);}
#define files(x) {freopen(x".in", "r", stdin); freopen(x".ans", "w", stdout);}
#define mem(x, a) memset(x, a, sizeof x);
#define cls(x) mem(x, 0)
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
template <typename T>
inline bool separate(cT l, cT r, cT L, cT R){return (R < l) || (L > r);}
template <typename T>
inline T sqr(cT _){return _ * _;}
template <typename T>
inline T read(){T x; cin >> x; return x;}
template <typename T>
inline void clear(T& q){typename remove_reference<decltype(q)> :: type _; swap(q, _);} // remove_reference_t is since C++14
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
template <typename T>
using pr = pair<T, T>;
template <typename T>
using maxheap = priority_queue<T>;
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T1, typename T2 = unsigned>
using umap = unordered_map<T1, T2>;
template <typename T1, typename T2 = unsigned>
using uset = unordered_set<T1, T2>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd;
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}

BOBO 让我板刷 ABC 的 A ~ F /youl

一些声明 / 约定：

如果我觉得有必要放代码则会放，若无特殊说明保证写了题解的题都是写过代码的，可以看我提交记录（ID: Jijidawang） .
Ex 题叫 Ex 不叫 H .
字符串无特殊说明则字符集为小写字母且非空 .
图无特殊说明无重边自环 .

别的：

总体上是（时间）从后往前做的，但是由于 ABC 在不断增多，所以下面的顺序不是时间顺序，而是标号顺序 .
每个比赛前面大概会有一个类似 Preface 的东西 .

AtCoder Beginner Contest 273
AtCoder Beginner Contest 272
- E. Add and Mex
- G. Yet Another mod M
AtCoder Beginner Contest 271
AtCoder Beginner Contest 270
AtCoder Beginner Contest 269
AtCoder Beginner Contest 268
AtCoder Beginner Contest 267
AtCoder Beginner Contest 266

AtCoder Beginner Contest 273

同时也是 Panasonic Programming Contest 2022 .

身败名裂

D 是码农 binary-search /tuu

E. Notebook

维护一个序列 \(\{a\}\) 和一个 Notebook，支持：

在 \(\{a\}\) 的末尾加一个元素或者删一个元素 .

将 \(\{a\}\) 记到 Notebook 的某一页（如果那一页原来有东西则先删掉它）.

将 \(\{a\}\) 变成 Notebook 的某一页 .

每次操作之后输出序列的最后一个元素 .

\(1\le q\le 5\times 10^5\) .

大概就是维护一个可持久化栈 .

注意到没有强制在线，于是可以离线建操作树，这是一个非常经典的 Trick，然后就平凡了 .

一般的简易写法是 \(\Theta(q\log q)\) 的，可以通过 . 话说似乎可以做到 \(\Theta(q)\)？

F. Hammer 2

有 \(n\) 面墙位于 \(a_{1\dots n}\) 和 \(n\) 个锤子位于 \(b_{1\dots n}\) .

走到锤子可以拿，墙不能走，标号一致的锤子可以干掉对应的墙，问从 \(1\) 到 \(x\) 至少走多少路 .

\(1\le n\le 1500\)，所有位置互不相同且绝对值在 \([1,10^9]\) .

前传：Hammer 1 .

教做人题 /kk 其实就是一个关路灯型区间 DP .

令 \(dp_{l,r}\) 表示走完区间 \([l,r]\) 后待在 \(l\) 或 \(r\) 的最小移动距离总和 .

转移平凡略过，时间复杂度 \(\Theta(n^2)\) .

“自从一个混乱之人发明了离散化，大部分关于区间的题目便都套上了它。”
——鲁迅

Code .

G. Row Column Sums 2

给序列 \(\{r_n\}\)，\(\{c_n\}\)，计数满足如下条件的 \(n\times n\) 方阵数量：

第 \(i\) 列之和为 \(r_n\) .

第 \(i\) 行之和为 \(c_n\) .

\(1\le n\le 5000\)，\(0\le r_i,c_i\le 2\) .

User Editorial 是什么鬼东西啊？你是在题解里写闲话还是啥？下面复读 Official Editorial .

令 \(\displaystyle\sum_{i=1}^nr_i=\sum_{i=1}^nc_i\)，否则答案必然为 \(0\) .

构造矩阵 \(\{\{a\}\}\)，使得：

\(\displaystyle\sum_{j=1}^na_{i,j}=r_i\) .
\(\displaystyle C_{i,j}:=C_j-\sum_{k=1}^ia_{k,j}\ge 0\) .

其中显然有 \(C_{i,j}\in\{0,1,2\}\)，于是当对于每个 \(i\) 都有 \(C_{n,i}=0\) 时则是一组满足条件的解 .

这样实际上是构造了一个双射，于是可以考虑 DP 求解，令 \(dp_{i,x}\) 表示前 \(i\) 行，并且有 \(x\) 个 \(j\) 满足 \(C_{n,j}=2\) .

令有 \(y\) 个 \(j\) 满足 \(C_{n,j}=1\)，则显然 \(\displaystyle\sum_{j=1}^nC_{i,j}=y+2x\) .

又根据 \(C\) 的定义（看上面的无序列表），则可以化简得

\[y=\sum_{k=1}^nc_k-\sum_{k=1}^ir_k-2x \]

这样 \(0,1,2\) 的数量就都能算了，于是即可转移：

\[dp_{i,x}=\begin{cases}dp_{i-1,x}&r_i=0\\(x+1)dp_{i-1,x+1}+(y+1)dp_{i-1,x}&r_i=1\\(x+1)(y+1)dp_{i-1,x+1}+\dbinom{x+2}2dp_{i-1,x+2}+\dbinom{y+2}2dp_{i-1,x}&r_i=2\end{cases} \]

详细而具体的解释可以看 Official Editorial .

然后这题就做完了，时间复杂度 \(\Theta(n^2)\)，可以通过 .

按理说可以滚动数组，不过也没什么必要了吧 .

真的很妙妙啊，人类智慧的加了一个限制就变得好做了呢，不过我不懂 DP 可能也不配发表对 DP 题的见解吧 .

Ex. Inv(0,1)ving Insert(1,0)n

一个元素是二元组的序列 \(A\)，初始 \(A=((1,0),(0,1))\)，进行若干次操作，每次选两个相邻的对 \((a,b),(c,d)\)，在 \(A\) 中追加 \((a+b,c+d)\) .

对于集合 \(T\)，定义 \(f(T)\) 为 \(T\) 中所有元素最少经过多少次操作可以在 \(A\) 中得到 .

给一个由二元组组成的序列 \(\{a\}\)，定义 \(\operatorname{sub}(l,r)\) 为子串 \(a[l:r]\)，求

\[\sum_{l=1}^n\sum_{r=l}^nf(\operatorname{sub}(l,r)) \]
对 \(998244353\) 取模 .

\(1\le n\le 10^5\)，\(\{a\}\) 的元素互不相同 .

很难揣测出题人是在什么样的精神状态下在 ABC 放了一道板板题的 .~~（可能问问 joke3579 能知道？~~

显而易见构造过程其实就是建了一棵 Stern–Brocot Tree（后称作 SBT），然后用经典 Trick SBT 二分即可 .

时间复杂度 \(\displaystyle\Theta(n\log^2n\log\max_{i\in[1,n]}\{a_i,b_i\})\)，代码不想写了 .

AtCoder Beginner Contest 272

ABCD 是模拟题，不说 .

F 是 SA 题，不会，不做 .

Ex 是 GF 题，CSP-J 选手考前做 GF 容易掉 RP（？），不做（我也不想写多点求值）.

放一下 F, Ex 的题面 .

题面

F. Strings

给两个字符串 \(s,t\) .

令 \(f(s,x)\) 表示 \(s\) 向前循环移位 \(x\) 位后的值 .

问有多少对 \((i,j)\)（\(0\le i,j<n\)）使得 \(f(s,i)<f(t,j)\)，小于号比较字典序 .

\(1\le n\le 2\times 10^5\) .

Ex. Flipping Coins 2

给一个的序列 \(\{a_n\}\)，序列每个元素都是在 \([0,n)\) 内的整数 .

有一个序列 \(\{b_n\}\)，初始全 \(0\) .

对于一个 \(1\) 到 \(n\) 的排列 \(\pi\)，进行 \(n\) 次操作，第 \(k\) 次操作时，对于 \(0\le j\le a_{\pi_k}\)，将 \(b_{(k-1+j)\bmod n}\) 加一 .

问随机选一个排列 \(\pi\) 进行操作，操作后 \(\{b\}\) 中偶数元素个数的期望，对 \(998244353\) 取模 .

\(1\le n\le 2\times 10^5\) .

Flipping Coins 1 好像是 ARC134F .

E. Add and Mex

一个序列 \(\{a_n\}\)，\(m\) 次操作，每次将 \(a_i\gets a_i+i\) .

每次操作之后回答序列 \(\{a\}\) 的 mex .

\(1\le n,m\le 2\times 10^5\)，\(|a_i|\le10^9\) .

人类智慧 .

暴力复杂度是对的，因为注意到 \(k\) 次操作后，每个 \(a_i\) 若满足 \(a_i+ki\le n\) 则才可能作为 mex .

也就是说所有时刻所有可能作为 mex 的数有

\[\sum_{i=1}^nO\left(\dfrac ni\right)=O(n\log n) \]

个（调和级数）.

于是暴力就只需要考虑 \(O(n\log n)\) 个元素，然后要用一个堆维护一下每一时刻的 \(a_i+ki\)，又喜提一个 log，总时间复杂度 \(O(n\log^2n)\)

G. Yet Another mod M

给一个序列 \(\{a_n\}\)，求一个整数 \(3\le m\le 10^9\)，使得 \(\{a\}\) 中有 \(\left\lfloor\dfrac n2\right\rfloor+1\) 个数在模 \(m\) 意义下相同 .

\(3\le n\le 5000\)，\(1\le a_i\le 10^9\) .

主元素问题就是摩尔投票或者随机化，这题看起来就不可摩尔投票，于是考虑随机化 .

假设有解 \(m\)，\(S=\{i\mid a_i\equiv z\pmod m\}\)（\(z\) 是主元素），则随两个数 \(a_x,a_y\)，\(x\in S\) 且 \(y\in S\) 的概率是 \(\dfrac 14\) .

假设随了两个数 \(a_x,a_y\) 且 \(x\in S\)，\(y\in S\)，则 \(m\mid (a_x-a_y)\) .

于是枚举 \(a_x-a_y\) 的因子 \(m\) 分别判断即可 .

令随机 \(r\) 次，则时间复杂度为 \(\Theta(rn\sqrt L\log n)\)，取 \(r=10\) 左右即可通过 .

不想写枚举因子 /wq

AtCoder Beginner Contest 271

同时也是 KYOCERA Programming Contest 2022 .

A 手头上没有 Python 解释器于是 RE 两发（AC 后才想起来有 Custom Test 这玩意 /hsh），身败名裂（迫真

A, B, C 题都是简单模拟题，略过 .

D 是平凡 DP 记录状态，不是很想说，略 .

Ex 好像是巨大分类讨论，不想做 .

E. Subsequence Path

给一张 \(n\) 点 \(m\) 边无向图和一个序列 \(\{e_k\}\)，找一条 \(1\) 到 \(n\) 的长度最短的路径 \(p\)，使得其经过的边按顺序排列好是 \(\{e\}\) 的一个子序列 .

只需输出 \(p\) 的长度 .

\(1\le n,m,k\le 2\times 10^5\)，\(n\ge 2\) .

~~有点偏序的感觉？~~

好水啊，我也不想写这题题解啊，但是不写的话就没几个题解在这个 H2 底下了 /hsh

把 \(\{e\}\) 看成点序列导致持续自闭 /px 我真的是好菜啊 .

按照 \(\{e\}\) 的顺序依次松弛，显而易见最后的最短路就是答案，具体可以从 DP 角度理解 .

时间复杂度 \(\Theta(n+m+k)\)，空间复杂度 \(\Theta(n)\) .

F. XOR on Grid Path

一个 \(n\times n\) 矩阵 \(\{\{a\}\}\)，问有多少条 \((1,1)\) 到 \((n,n)\) 的路径使得路径的异或和为 \(0\) .

\(2\le n\le 20\)，\(0\le a_{i,j}<2^{30}\) .

这个 meet-in-the-middle 相对板子一点啊 .

以前一直以为 meet-in-the-middle 不能解决计数问题，这次遇到一个计数的 meet-in-the-middle，学习一下 .

首先把矩阵斜着劈成两半，两边分别 DFS，可以发现异或和等于 \(0\) 就是左右异或和相等，于是 DFS 的时候把异或和扔 Hash Table 里查一下就好了 .

状态实际上只有 \(2^{n-1}\) 个，于是时间复杂度就是 \(\Theta(n2^n)\)，可以轻松通过 .

第一次写 meet-in-the-middle，好像还挺好写的，Code .

G. Access Counter

一个长度为 \(24\) 的序列 \(\{a\}\)，每个元素是 A 或 T .

每一时刻 \(i\) 有如下两种情况：

\(a_{i\bmod 24}\) 是 T，则 Alice 以 \(x\%\) 的概率进行一次 access .

\(a_{i\bmod 24}\) 是 A，则 Bob 以 \(y\%\) 的概率进行一次 access .

其中每次 access 是独立的 .

问第 \(n\) 次 access 是 Bob 进行的概率是多少，对 \(998244353\) 取模 .

\(1\le n\le 10^{18}\)，\(1\le x,y\le 99\) .

首先可以预处理出来 \(p(x,y)\) 表示这一次 access 在第 \(x\) 个时刻，下一个 access 在第 \(y\) 个时刻的概率 .

这个非常好处理，直接放柿子，其中 \(p_k\) 表示时刻 \(k\) 有一次 access 的概率：

\[p(x,y)=\dfrac{\displaystyle p_y\prod_{k=x+1}^{y-1}(1-p_k)}{\displaystyle1-\prod_{k=1}^n(1-p_k)} \]

然后令 \(dp_{i,j}\) 表示第 \(i\) 次 access 在第 \(j\) 个时刻的概率，则可以发现转移的时候就是乘一下 \(p\) 代表的矩阵 .

矩阵快速幂优化一下，\(\Theta(d^3\log n)\)，其中 \(d=24\) .

代码懒得写了 QwQ

AtCoder Beginner Contest 270

同时也是 TOYOTA MOTOR CORPORATION Programming Contest 2022 .

A, B, C 题都是简单模拟题，略过 .

G 是 SDOI2013 随机数生成器，做 BSGS 题单的时候大家应该都做过，也略过 .

D. Stones

有 \(n\) 个石子和一个序列 \(\{a_k\}\) .

Alice 和 Bob 轮流选一个序列里的数 \(a_i\)，要求 \(a_i\) 不大于目前的 \(n\)，然后取 \(a_i\) 个石子，取完石子结束 .

Alice 先手，两个人的目标都是取到石子数最多，问 Alice 最多取到多少石子 .

\(1\le n\le 10^4\)，\(1\le k\le 10^2\) .

第一眼就想到了 Educational DP Contest 的 L. Deque，以为是个类 Minimax 搜索的 DP，但是 Alice 和 Bob 都是要最大化自己的答案所以就不需要这么复杂了 .

注意到一个每个石子不是被 Alice 拿到就是被 Bob 拿到，令 \(dp_n\) 表示有 \(n\) 个石子的时候的答案，则

\[\begin{aligned}dp_n&=\max_{i\in[1,k]}\{n-a_i-dp_{n-a_i}+a_i\}\\&=n-\min_{i\in[1,k]}\{dp_{n-a_i}\}\end{aligned} \]

暴力 DP，时间复杂度 \(\Theta(nk)\) .

问一下这种 DP 转移有没有什么高论能优化的？

E. Apple Baskets on Circle

\(n\) 堆苹果排成一圈，第 \(i\) 堆有 \(a_i\) 个，一个人初始在第一堆苹果处，每次拿一个苹果（如果没有就不拿）并走一步，问拿到 \(k\) 个苹果时，每个堆的苹果数是多少 .

\(1\le n\le 10^5\)，\(0\le a_i\le 10^{12}\)，\(\displaystyle\max\left\{1,\sum_{i=1}^na_i\right\}\le k\le 10^{12}\) .

首先可以平凡破环为链 .

标程是 \(\Theta(n\log k)\) 的 binary-search，但是我不会 use binary-search，就说一下题解里面说的那个 \(\Theta(n\log n)\) 的 Bonus .

考虑算每一轮拿了多少苹果，这样将 \(\{a\}\) 排个序差分一下就好了，几乎没有 corner case，非常好写，具体看代码吧 .

其实 word-RAM model 下可以认为整数排序是线性的，这样就是 \(\Theta(n)\) 的了 .

核心代码：

int n;
ll k, a[N], b[N];
int main()
{
	scanf("%d%lld", &n, &k);
	for (int i=1; i<=n; i++) scanf("%lld", a+i), b[i] = a[i];
	stable_sort(a+1, a+1+n);
	int ptr = 1; ll dif = 0;
	while (ptr <= n)
	{
		ll d = a[ptr] - a[ptr-1]; int now = n - ptr + 1;
		if (k >= d * now){k -= d * now; dif += d;}
		else{dif += k / now; k %= now; break;}
		++ptr;
	}
	for (int i=1; i<=n; i++) b[i] = max(0ll, b[i] - dif);
	int cc = k; ptr = 1;
	while (cc--){while (!b[ptr]) ++ptr; --b[ptr++];}
	for (int i=1; i<=n; i++) printf("%lld ", b[i]);
	puts("");
	return 0;
}

测试点全是 random，写得很离谱也能得到很多点的 AC /hsh

F. Transportation

有 \(n\) 个点，如下操作：

对于 \(1\le i\le n\)，可以花 \(x_i\) 的贡献在 \(i\) 号点建一个机场 .

对于 \(1\le i\le n\)，可以花 \(y_i\) 的贡献在 \(i\) 号点建一个港口 .

对于 \(1\le i\le n\)，可以花 \(z_i\) 的贡献在 \(a_i\) 号点到 \(b_i\) 号点连一条无向边 .

如果两个点 \(u,v\) 满足下列条件之一，则 \(u,v\) 可以互相到达：

\(u,v\) 都有机场 .

\(u,v\) 都有港口 .

\(u\) 到 \(v\) 有边 .

问至少花多少代价才能让所有点连通 .

\(1\le n,m\le 2\times 10^5\)，\(1\le x_i,y_i,z_i\le 10^9\) .

比较套路的一道题 .

注意到如果没有机场和港口那么就是 MST 问题 .

然后建两个虚拟点 \(s_{\sf A},s_{\sf B}\)，每个点 \(i\) 向 \(s_{\sf A}\) 连边权为 \(x_i\) 的无向边，向 \(s_{\sf B}\) 连边权为 \(y_i\) 的无向边即可 .

这样 MST 出来基本就是答案了，但是虚拟点也占连通性，所以讨论一下用不用虚点跑 4 遍 MST 即可 .

时间复杂度 \(\Theta(m\log m)\)，MST 采用 Kruskal 算法 .

这题的细节：

不要想着 1 遍 MST 然后减掉贡献，MST 可能不唯一这样就寄了 .
INF 别开小了，要 long long 范围的 .
Kruskal 的 MST 跑完要看一下是否连通，别偷懒，把点数传进去，要不然就是错的（至少我目前没有发现什么方法能把它变成对的）.

血的教训，我吃 15 发罚时啊 /ll

Ex. add 1

一个序列 \(\{a_n\}\)，满足 \(a_1=0\) 且除 \(a_1\) 外的其它元素都大于 \(0\) .

一个序列 \(\{c_n\}\)，初始全是 \(0\)，每次随机选一个数把它变成 \(0\) 并且把其它数全部加 \(1\)，问对于所有 \(1\le i\le n\)，有 \(c_i\ge a_i\) 时，期望操作多少次 .

答案对 \(998244353\) 取模 .

\(2\le n\le 2\times 10^5\)，\(a_i\le 10^{18}\)，\(\{a\}\) 单调不减 .

非常有意思的一道题啊 .

定义一个状态 \(\{b\}\) 的距离为

\[\delta(\{b\})=\max_{1\le i\le n}\{max\{0,a_i-b_i\}\} \]

考虑 DP，令 \(dp_k\) 表示距离为 \(k\) 的状态期望需要多少步到达终止状态，则初始 \(dp_0=0\)，答案为 \(dp_{a_n}\) .

令目前的距离为 \(k\)，则转移首先可以发现若变为 \(0\) 的元素为 \(a_i\)，新距离即为

\[\begin{aligned}\delta'&=\max\{a_i,\max_{j\neq i}\{a_j-b_j-1\}\}\\&=\max\{a_i,\max_{j\neq i}\{a_j-b_j\}-1\}\\&=\max\{a_i,k-1\}\end{aligned} \]

也就可以得到

\[dp_k=1+\dfrac1n\sum_{i=1}^ndp_{\max\{a_i,k-1\}} \]

首先这个转移顺序就还不对，还有个 max 非常难搞，先把 max 拆开，令 \(a_p\) 为 \(\{a\}\) 中小于 \(k\) 的元素中下标最大的，则

\[dp_{k}=1+\dfrac pn\cdot dp_{k-1}+\dfrac 1n\sum_{i=p+1}^ndp_{a_i} \]

也就是 \(\displaystyle dp_{k-1}=\dfrac 1p\left(n\cdot dp_k-n-\sum_{i=p+1}^ndp_{a_i}\right)\) .

用 \(k\) 替换 \(k-1\) 即得

\[dp_k=\dfrac 1p\left(n\cdot dp_{k+1}-n-\sum_{i=p+1}^ndp_{a_i}\right) \]

发现转移顺序反了，于是令 \(f(k)=dp_{a_n}-dp_k\)，则

\[f(k)=\dfrac 1p\left(n\cdot f(k+1)+n-\sum_{i=p+1}^n f(a_i)\right) \]

转移并没有什么变化，但是这里的边界变为 \(f(a_n)=0\)，答案为 \(f(0)\)，这样就可以算了 .

直接暴力是 \(\Theta(n+L)\) 的，\(L\) 是值域，显然过不去，于是考虑优化 .

发现本质不同的转移只有 \(n\) 种，可以考虑合并起来，也就是先固定 \(p\)，则对于 \(a_p\le k<a_{p+1}\)，转移形式相同，于是令定值 \(\displaystyle F=\dfrac 1p\left(n-\sum_{i=p+1}^nf(a_i)\right)\)，则

\[f(a_p)=\dfrac np\cdot f(a_p+1)-F \]

这个转移可以到 \(a_{p+1}\)，于是解一下递推式即可得到

\[f(a_p)=\left(\dfrac np\right)^{a_{p+1}-a_p}f(a_{p+1})-\dfrac{1-(\frac np)^{a_{p+1}-a_p}}{1-\frac np}\cdot F \]

于是依次计算 \(f(a_{n-1})\) 到 \(f(a_1)=f(0)\) 即可，前缀和优化即可做到 \(\Theta(n\log p)\)，其中 \(p=998244353\) 是模数，log 由求逆元的快速幂贡献 .

做完了，代码还是非常好写的，Code .

AtCoder 模板库 modint998244353 真好用（

AtCoder Beginner Contest 269

也叫 UNICORN Programming Contest 2022 .

ABCD 比较水就不说了 .

有交互还是有点出乎意料的，不过这场 ABC 似乎确实比较水 .

Ex 要 NTT，不做 .

E. Last Rook

交互 .

一个 \(n\times n\) 的棋盘里有 \(n-1\) 个车，每次可以问一个矩形内有多少个车，问哪个格子可以再放一个车 .

\(2\le n\le 10^3\)，最多 \(20\) 次询问 .

注意到行列独立，分别二分一下即可 .

询问次数上界 \(2\lceil\log_2n\rceil\)，轻松跑过 .

F. Numbered Checker

\(n\times m\) 的网格，\((i,j)\) 上的数为

\[\begin{cases}0&i+j\text{ is odd.} \\(i-1)m+j&\text{otherwise.}\end{cases}\]
\(q\) 次询问，每次求一个矩形内元素和，对 \(998244353\) 取模 .

\(1\le n,m\le 10^9\)，\(1\le q\le 2\times 10^5\) .

大水题，分奇偶性经过一些分类讨论可以得到通项 .

具体的，答案是

\[\sum_{a\le x\le b}\sum_{c\le x\le d}[x+y\text{ is even}]((x-1)m+y) \]

也就是

\[\sum_{a\le x\le b}(x-1)m\sum_{c\le x\le d}[x+y\text{ is even}]+\sum_{c\le x\le d}y\sum_{a\le x\le b}[x+y\text{ is even}] \]

处理一下区间内所有奇数的和，然后等差数列求和即可单次 \(\Theta(1)\) .

于是总时间复杂度即为 \(\Theta(q)\) .

G. Reversible Cards 2

有 \(n\) 张正反两面写有数字的卡片，正面 \(a_i\) 反面 \(b_i\)，初始时全是正面，正反两面数字之和 \(m\le 2\times 10^5\)，你可以翻转这 \(n\) 张卡片的任意一张。对于每个 \(k\in[0,m]\)，问当前朝上的数字之和等于 \(k\) 时的最少翻转数，不能为 \(k\) 输出 -1 .

\(1\le n\le 2\times 10^5\)，\(0\le m\le2\times 10^5\) .

我觉得 Reversible Cards 1 是 ABC271E / Flip and Adjust，有点玄妙 . 时间刺客？

显然每次翻转的增量为 \(b_i-a_i\)，于是分正负分别考虑，每种都有 \(\lceil\sqrt m\rceil\) 种本质不同的增量，成等差数列时取到，于是总共本质不同的增量个数就是 \(2\lceil\sqrt m\rceil\) .

处理出所有增量和其出现次数，然后就是多重背包了 .

单调队列优化即可做到 \(\Theta(n+m\sqrt m)\) .

因为这个增量之和是有限制的，官方题解指出，若 \(\displaystyle\sum_{i=1}^kw_i\le W\)，则 \(\displaystyle\sum_{i=1}^k\log w_i=O(\sqrt W)\) .

~~当初在洛谷问这个玩意都他妈告诉我等于 \(O(\log W)\)，气人啊~~

于是二进制拆分优化的多重背包的时间复杂度是要比 \(n+m\sqrt m\) 快一点的 . 是否可以记为 \(o(n+m\sqrt m)\)？

多重背包我不想写 .

AtCoder Beginner Contest 268

也叫 UNIQUE VISION Programming Contest 2022 Summer .

ABCD 大水题略过，C 可能作为一道 ABC 的 C 题是 educational 的 .

~~D 是基础 XIN 队算法综合应用练习题？真是一道 CSP 前不可多得的复建暴力好题啊。~~

FGH 串串三连击 /hsh ~~字符串滚出 OI~~

E. Chinese Restaurant (Three-Star Version)

给一个 \(1\) 到 \(n\) 的排列 \(\{p_n\}\)，将其循环移位若干次，最小化：

\[\operatorname{fru}(p)=\sum_{i=1}^n\operatorname{dist}(p_i,i) \]
其中 \(\operatorname{dist}(p_i,i)\) 是循环的 \(p_i\) 与 \(i\) 的距离 . 只需输出最小的 \(\operatorname{fru}(p)\) .

\(3\le n\le 2\times 10^5\) .

其实就是和 C 差不多的算贡献 .

只不过这次的贡献累加不像 C 那么平凡，这个是由两个等差数列拼成的一个单峰玩意 .

比较经典，二阶差分维护即可 \(\Theta(n)\) .

数据范围开 \(2\times 10^5\) 是想放带 log 的做法过嘛？

核心代码：

const int N = 422222;
int n, p[N];
ll d[N];
int main()
{
	scanf("%d", &n);
	for (int i=0; i<n; i++) scanf("%d", p+i);
	auto op = [&](int k) -> void
	{
		int x=0, y=n/2, z=n/2+n%2, w=n;
		++d[x+k+1]; --d[y+k+1]; --d[z+k+1]; ++d[w+k+1];
	};
	for (int i=0; i<n; i++) op((i <= p[i]) ? p[i] - i : n + (p[i] - i));
	for (int i=1; i<=2*n; i++) d[i] += d[i-1];
	for (int i=1; i<=2*n; i++) d[i] += d[i-1];
	ll ans = 0x3f3f3f3f3f3f3f3fll;
	for (int i=1; i<=n; i++) chkmin(ans, d[i] + d[i+n]);
	printf("%lld\n", ans);
	return 0;
}

Details:

建议选为最有价值题解 .

F. Best Concatenation

\(n\) 个字符串 \(\{s_n\}\)，字符集为数字（\(1\) 到 \(9\)）和 \(\tt X\) . 将其按某种顺序拼接在一起得到字符串 \(S\) .

一个 \(S\) 的价值如下定义：若 \(S\) 的某一位 \(i\) 上是数字 \(d\)，且这一位前面有 \(x\) 个 \(\tt X\)，则它对价值产生 \(xd\) 的贡献 . 字符串的价值即为每一位的贡献之和 .

求最大价值 .

\(2\le n\le 2\times 10^5\)，\(\{s\}\) 的长度之和不超过 \(\displaystyle\sum_{i=1}^n|s_i|\le 2\times 10^5\) .

不怎么人类智慧的贪心题 .

处理出每个字符串含多少个 \(\tt X\)，以及所有数字之和是多少，分别记作 \(a_i\) 和 \(b_i\) .

假设有一个 \(S\) 是最优解（由若干段拼成，一个「段」是在序列 \(\{s\}\) 中的某个 \(S\) 的子串，意会一下），则考虑交换相邻两段 \(i\) 和 \(i+1\)，首先交换这个对其他段显然没有影响，于是算一下这两段分别的贡献 .

显然交换前贡献是 \(a_ib_{i+1}\)，交换后是 \(a_{i+1}b_i\) . 因为 \(S\) 是最优答案于是 \(a_ib_{i+1} < a_{i+1}b_i\) .

移项可得 \(\dfrac{a_i}{b_i}<\dfrac{a_{i+1}}{b_{i+1}}\)，这已经构成一个严格偏序，于是按这个排序即可 .

时间复杂度 \(\Theta(n\log n)\)，可能还能更优但是没啥意义 .

G. Random Student ID

\(n\) 个字符串 \(\{s_n\}\)，字符集是小写字母 .

随一个从小写字母到小写字母的置换，对每个 \(\{s\}\) 施加这个置换，问最后每个元素排名的期望（比较按字典序比），对 \(998244353\) 取模 .

约定：\(\{s\}\) 互不相同，\(n\ge 2\)，\(\displaystyle\sum_{i=1}^n|s_i|\le 5\times 10^5\) .

妙妙题 .

根据期望线性性，令 \(p(i,j)\) 表示 \(s_i>s_j\) 的概率，则 \(s_i\) 的排名期望就是 \(\displaystyle\sum_jp(i,j)\) .

讨论一下：

若 \(s_i\) 是 \(s_j\) 的前缀，则 \(p(i,j)=0\) .
若 \(s_j\) 是 \(s_i\) 的前缀，则 \(p(i,j)=1\) .
否则，它们的字典序大小就取决于第 \(|\operatorname{lcp}(s_i,s_j)|+1\) 位的大小，这样就显然得 \(p(i,j)=\dfrac12\) .

对于前两种用 Trie 算一下串数，这样三种情况的串数就都得到了，然后简单算一下就可以得到排名 .

复杂度 \(\displaystyle O\left(\sum_i|s_i|\right)\) .

另外还有规避 Trie 的方法，注意到我们只是算一下给定集合中某个字符串的前缀有多少个，我们可以将每个字符串 \(s\) 复制一遍变成 \(s'\)，然后在 \(s\) 的末尾加上一个比字符集内所有字符的字典序都要大的字符，这个新字符串记作 \(\operatorname{SuS}(s)\) .

这样，一个字符串 \(s_1\) 是 \(s_2\) 的前缀当且仅当 \(s_1<s_2\) 且 \(\operatorname{SuS}(s_1)>s_2\)，排一下序即可 .

复杂度是字符串排序的复杂度，如果使用 Radix Sort 则是 \(\displaystyle \Theta\left(\sum_i|s_i|\right)\)，区别仅仅是把 \(O\) 变成了 \(\Theta\) .

两种做法都不难写 . Trie 树 | 排序 .

Ex. Taboo

给一个字符串 \(s\) 和 \(n\) 个字符串 \(\{t_n\}\)，将 \(s\) 的若干位改成 \(\tt*\)，要求所有 \(t_i\) 都不是 \(s\) 的子串 .

问最少改多少位 .

\(\{t\}\) 互不相同，\(\displaystyle\sum_{i=1}^n|t_i|\le 5\times 10^5\)，\(1\le n,|s|,|t_i|\le 5\times10^5\) .

大撒子 Official Editorial 用的 SA，我不会，只好写个 ACAM 题解 .

首先有个显然的贪心策略是直到有一个下标必须删除才删除，这样建出 \(\{t\}\) 的 ACAM，然后用 \(s\) 在上面跑，跑到匹配就跳回根（相当于对应位改成 \(\tt*\)），这样就好了 .

时间复杂度 \(\displaystyle O\left(|s|+|\Sigma|\sum_i|t_i|\right)\) .

注意不要像我一样每次傻乎乎地匹配的时候跳 fail，这样会被全相同的串串卡掉，要提前预处理一下每个点能不能匹配上，这样复杂度才是对的 . Code .

这个 ACAM 做法比较无脑，还可以 Hash 做，具体见 zhangmj2008 博客 .

AtCoder Beginner Contest 267

也是 NEC Programming Contest 2022 .

这签到题怎么出的这么码农啊 /hsh 索性 skip 掉 B 不做了！

Ex 多项式优化 DP，不做 .

E. Erasing Vertices 2

给一张 \(n\) 个点 \(m\) 条边的无向图，点有点权，需要进行 \(n\) 次操作，每次选择一个点删掉它和它的所有邻接边，花费与其直接相连的所有点权之和的代价 .

问所有操作的代价的最大值的最小值是多少 .

\(0\le n,m\le 2\times 10^5\)，\(1\le a_i\le 10^9\) .

大概有两种做法：

贪心：注意到一个贪心策略是每次移除当前代价最小的那个，那么最终一定是最大值最小的情况 . 于是可以用优先队列维护这个代价最小的点，移除后暴力修改邻接点的代价，并且将它们入队 . 暴力修改的复杂度其实就是边的数量，因此总的时间复杂度是 \(\Theta((n+m)\log(n+m))\) .
二分：首先最大值最小就必然可以二分，然后判断的时候把小于当前值的所有点从小到大挨个跑一边看看能不能全删掉即可，时间复杂度 \(\Theta((n+m)\log L)\)，\(L\) 是点权和 .

提交记录：二分，不太想写贪心的，感觉就是 Dijkstra .

F. Exactly K Steps

给一棵 \(n\) 个结点的无根树，\(q\) 组询问，每次询问给 \(x,k\)，求树中任意一个与 \(x\) 距离为 \(k\) 的点，或者返回无解 .

\(2\le n\le 2\times 10^5\) .

~~考古 JRKSJ Round 6 2C/1A~~

早知道不看题解了，太损害思考体验了 /hsh

首先直径上必然存在答案，于是讨论一下就变成树上 \(k\) 级祖先问题了 .

这个数据范围似乎是放带 log 做法过的，不过树上 \(k\) 级祖先问题存在 \(\Theta(n+q)\) 的一个简洁离线做法，具体就是把询问挂树上然后 DFS 记录祖先序列 .

在线如果要做到 \(\Theta(n+q)\) 的话代码就会变得非常难写，不过也是能做到的 .

于是问题的总复杂度就是 \(\Theta(n+q)\)，找直径只能两遍 DFS 因为要找端点 TAT，Code .

G. Increasing K Times

给一个序列 \(\{a_n\}\)，问有多少个排列 \(\{p\}\) 满足恰好有 \(k\) 个 \(i\in[1,n]\) 使得 \(a_{p_i}<a_{p_{i+1}}\) . 答案对 \(998244353\) 取模 .

\(2\le n\le 5000\) .

比较平凡的排列 DP（或者叫插入 DP，预设型 DP 啥的），难点主要是在 \(\{a\}\) 的重复元素上，于是维护一下对于 \(x\)，已经插入进去的与 \(x\) 相同的元素有多少个就好了 .

时间复杂度 \(\Theta(nk)\)，Code .

一个进阶版本练习题：ARC148E .

AtCoder Beginner Contest 266

事实证明我连 A % 998244353 Problem 都不能 1A 了……CSP 肯定挂挂了 /kk（flag×1）

Mark 一下 C 的叉积做法 Code .

E. Throwing the Die

一个六面骰子，每次投一下，投到 \(n\) 次强制停止 .

得分是你最后一次投到的数，问最大期望得分是多少 .

\(1\le n\le 100\) .

不会期望实锤了 .

令 \(dp_n\) 表示 \(n\) 轮的答案，则

\[dp_n=\sum_{i=1}^n\max\{i,dp_{n-1}\} \]

直接递推就完了，时间复杂度 \(\Theta(n)\)，可以滚动数组但是没必要 .

然后如果加强一下可以矩阵快速幂优化 .

F. Well-defined Path Queries on a Namori

给一个 \(n\) 点 \(n\) 边的无向图，多组询问每次给 \((u,v)\) 判断 \(u\) 到 \(v\) 是否只存在一条简单路径 .

\(1\le n,q\le3\times10^5\)，保证图连通 .

怎么感觉这个 Namori 是某著名日本画师……？

显然原图是基环树，于是看一下 \(u,v\) 是否在同一子树即可，\(\Theta(n+q)\) .

原来基环树找环有超级简洁的做法，模拟赛口胡害人不浅啊 .

事实证明在口胡算法之后还是要看看大众写法
——APJifengc

Code .

G. Yet Another RGB Sequence

给四个正整数 \(r,g,b,k\)，计数如下字符串的数量：

字符集为 \(\{\texttt R,\texttt G, \texttt B\}\) .

\(\texttt R,\texttt G, \texttt B\) 的数量分别为 \(r,g,b\) .

\(\tt RG\) 子串的数量为 \(k\) .

对 \(998244353\) 取模 .

\(1\le r,g,b\le 10^6\) .

高级平凡数数题（？

首先至少 \(k\) 个 \(\tt RG\) 子串好做，就是一个高考数学难度的组合：

\[F(k)=\dbinom mi\dbinom{m-i}x\dbinom{m-x-k}y\dbinom{m-x-y-k}b \]

其中 \(x=r-k,y=g-k,m=x+y+k-b\) .

二项式反演的一种形式：

\[F(n)=\sum_{i=1}^n\dbinom niG(i)\iff G(n)=\sum_{i=1}^n(-1)^i\dbinom niF(i) \]

于是 \(G\) 就是答案，暴力代入算即可，时间复杂度 \(\Theta(n)\)，Code .

有一个做法是把 \(k\) 个 \(\tt RG\) 换成 \(\tt K\) 然后问题就是没有 \(\tt RG\) 子串的方案了，然后把二项式反演换成容斥，额其实都是本质相同的，但是这个做法好像能用快速阶乘算法优化到 \(\Theta(\sqrt p\log p)\)？/yun 其中 \(p=998244353\) 是模数.

Ex. Snuke Panic (2D)

一个网格，一个 bot 初始在 \((0,0)\)，每个时刻可以向上左右（注意没有下）走一步或者不动 .

第 \(i\) 个 Snuke 会在 \(t_i\) 时刻出现在 \((x_i,y_i)\)，问 bot 最多能遇见多少 Snuke .

\(1\le n\le 10^5\)，\(0\le x_i,y_i,t_i\le 10^9\) .

口胡一波 .

令 \(dp_{x,y,t}\) 表示时刻 \(t\) 在 \((x,y)\) 点的答案，则

\[dp_{x,y,t} = \max_{\substack{t'\le t,y'\le y\cr y-y'+|x-x'|\le t-t'}}\{dp_{x',y',t'}\} \]

考虑怎么干掉这些限制，首先 \(t'\le t\) 可以由后面两个推出来所以没用，然后去绝对值即得

\[\begin{cases} y' \leq y \\ y - y' + (x - x') \leq t - t' \iff t' - x' - y' \leq t - x - y \\ y - y' + (x' - x) \leq t - t' \iff t' + x' - y' \leq t + x - y \end{cases} \]

就是三维偏序，CDQ 分治就完了，\(\Theta(n\log^2n)\) .

题解吊打三维偏序的方法是 2D 树状数组 / 2D 线段树，很强啊！

标签：10,le,题解,sum,ABC266,273,Theta,复杂度,dp
From： https://www.cnblogs.com/CDOI-24374/p/16792927.html