AtCoder 做题记录 - 壹

Children Yearn for the Evil Kindergarten

来源：AT_abc458_g

难度：2831

这道题把我困扰了好久，然后写这篇题解的当天下午发现自己理解错题了。然后就会了这种写法。

本写法为 slope trick + deque 优化，线性。听说有二分、贪心的做法，可以参考官方题解。这里就不做赘述了。

换一个角度考虑问题，即我们可以把这个看起来有点复杂的规划问题转换成“填小孩”这里用词是不是有点不当的问题，即在奖牌形态固定的情况下，每个小孩在第 $i$ 天 escape 的代价为 $b_1+b_2+\dots+b_{i-1}+(b_i+c_i)$。看起来似乎可以动态规划。这里的 $i$ 个加项分别依次对应第 $1$ 天到第 $i$ 天的代价。注意这里第 $j$ 天的奖牌第 $j$ 天到第 $n$ 天都能使用，所以要加一维奖牌数。

那么现在我们梳理一下 dp 维度，天数一维，小孩总数一维，小孩结束个数一维，转移一维，奖牌一维，哇似乎是五维的，把奖牌一维固定下来即维护每个状态最小消耗奖牌数也是四维的，这也太不好做了。唉，正难则反嘛，我们倒过来遍历，对于结束个数和总数就可以当做是同一维度的了。即，当前只需要知道第 $i$ 天及以后结束的小朋友个数，对于前面结束的小朋友是之后遍历的内容，暂时不用管。那么就可以消掉一维啦！

现在得到一个状态 $O(n^2)$ ，时间 $O(n^3)$ 的做法，对于 $f_{i,j}$ 表示第 $i$ 天以后共有 $j$ 个小朋友 escape，还需要从前 $i-1$ 天里面借的最少奖牌数。注意转移的时候第 $i$ 天可能有若干个小朋友结束，所以时间多了一维。

我们发现这就是个最优化取 $k$ 物品价值和问题，不难证明 $f_i$ 函数是单调递增且下凸的。所以我们考虑 slope trick。先推导出题目条件和约束：

• 如果第 $i$ 天以后共有 $j$ 个小朋友 escape，那么前 $i-1$ 天剩下留到后面的奖牌数至少是 $j\sum_{1\le p\lt i-1}a_p$ 块。这个信息是最重要的，也是奖牌数个数限制的充要条件。
• 对于每天新增 $a_i$ 块奖牌对于 $f_i$ 的影响是所有元素减去 $a_i$ 和 $0$ 取 $\max$。
• 对于每多一个小孩，$f_{i,j}$ 会和 $f_{i+1,j-1}+(\sum_{1\le p\le i}b_p)+c_i$ 取 $\min$。

我们注意到对于第三条而言相当于和一条直线做 $(\min,+)$ 卷积，第二条是整体平移然后局部清零，第一条相当于是和 $l:y=(\sum_{1\le p\lt i-1}a_p)x$ 取 $\max$。于是我们想到取维护斜率，然后做区间覆盖，维护区间值并支持查询与线任意一条线段 $x$ 固定的大小。当然用线段树上二分是可以的，不过用 deque 维护同斜率线段可以做到线性。

ps：其实我之前把题目理解成少于 $b_i$ 的小朋友奖牌清零而不用 drop out，这似乎就可以用一个单调栈去维护了，反而更简单。

ll solve(){
	int n=read(),m=1e6+1;
	REP(i,1,n)a[i]=read(),b[i]=read()+b[i-1],c[i]=read(),A[i]=A[i-1]+a[i];
	deque<pl>q; // length and slope
	PER(i,n,1){
		ll v=b[i]+c[i];
		int sum=m*(i==n);
		while(!q.empty()&&q.back().se>=v){
			sum+=q.back().fi;
			q.pop_back();
		}
		if(sum)q.push_back(mkp(sum,v));
		sum=0;
		while(a[i]){
			ll x=q.front().fi,y=q.front().se;
			q.pop_front();
			if(x*y<=a[i]){
				a[i]-=x*y;
				sum+=x;
				continue;
			}
			ll s=x*y-a[i];
			sum+=x-s/y-(s%y>0);
			if(s>=y)q.push_front(mkp(s/y,y));
			if(s%y)q.push_front(mkp(1,s%y));
			break;
		}
		if(sum)q.push_front(mkp(sum,0));
		sum=0;v=0;
		while(!q.empty()&&(!sum||b[i-1]*sum>v)){
			ll x=q.front().fi,y=q.front().se;
			if(!sum&&y>=b[i-1])break;
			if(b[i-1]*(sum+x)>=v+x*y){
				sum+=x;
				v+=x*y;
				q.pop_front();
				continue;
			}
			ll val=(b[i-1]*sum-v)/(y-b[i-1]);
			sum+=val;
			q.front().fi-=val;
			v+=y*val;
			if(b[i-1]*sum==v)continue;
			if(q.front().fi==1)q.front().se-=b[i-1]*sum-v;
			else{
				q.front().fi--;
				q.push_front(mkp(1,y-(b[i-1]*sum-v)));
			}
			break;
		}
		if(sum)q.push_front(mkp(sum,b[i-1]));
	}
	return q.front().fi*(!q.front().se); // remember to update
}

Two Arithmetic Progressions

来源：AT_arc221_a

难度：1686

我们发现，由 $\gcd(a,b)=\gcd(b,a\bmod b)$ 可以对 $A$ 和 $C$ 进行消元。消到 $C$ 为零，也就是形如求 $\gcd(Ai+B,D)$ 的形态。

接下来想一想如何求出 $\gcd(Ai+B,D)$。当 $D$ 是负数是，取正即可。为零的情况放到章末再讨论。可以发现，我们通过枚举 $D$ 的约数 $d$，对每一个约数判断是否能够整除 $Ai+B$，然后再稍微容斥一下可以求出 $\gcd$ 的和。所以现在我们要快速求出所有 $Ai+B$ 被 $d$ 整除的个数。我们发现对于 $i$ 满足 $d\mid Ai+B$ 的解集必然是一个无限等差数列，所以我们只要找到最小的 $i$ 就行。

对于 $d\mid Ai+B$ 可以转换为 $-Ai+dy=B$，也就是解一个同余方程。这里我们可以用 exgcd 解决。

如果有误，或者更好的解法，欢迎私信骚扰。

Roads and Gates

来源：AT_abc463_e

难度：1055

这场 D 和 E 自己做的方法好麻烦，导致没时间做 F 和 G。

提供一个别于建两个虚点的思路。对于特殊边而言，若真的建出 $\frac{1}{2}n(n-1)$ 条双向边，发现边数会爆炸。所以不可行。

考虑一下将 $\frac{1}{2}n(n-1)$ 条边不直接建出来，显然这之中大部分边是没用的。注意到 $w_{i,j}=x_i+Y+x_j$，观察 Dijkstra 的过程，对于已经找到最小值的点集 $S$，和尚未找到最小值的点集 $T$，显然有 $S\cap T=\varnothing,S\cup T=V$，下一个更新 $\text{dis}$ 的点必然是由 $S$ 中某一点 $u$ 所连一条边的另外一个端点 $v$，且 $v\in T$。实际上，对于特殊边，也是一样的。考虑 Dijkstra 堆优化每一次实际是把 $\text{dis}$ 最小的点拿出来，对于 $x_u+Y$ 的部分只要找到 $S$ 的某一个点使其最小即可，$x_v$ 的部分同理，那么我们在 Dijkstra 贪心过程中，每当 $S$ 发生变化，即找到一个点 $u$ 的 $\text{dis}$ 确定了，可以把这条没有建出来的边扔到堆里，实际上只会新增 $n-1$ 条虚边。

void dijkstra(int S){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<pli>q;
	dis[S]=0;
	q.push(mkp(-dis[S],S));
	ll minn=x[1]; // 记录集合 S 的最小 dis_u + x_u
	while(!q.empty()){
		int u=q.top().se;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		Min(minn,dis[u]+x[u]);
		s.erase(mkp(x[u],u)); // 将 u 移出集合 T
		for(auto it:E[u]){
			int v=it.v,w=it.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(mkp(-dis[v],v));
			}
		}
        
		if(!s.empty()){ 
			auto it=*s.begin();
			int v=it.se;
			if(dis[v]>minn+y+x[v]){ // 找到连接 S - T 的最短特殊边
				dis[v]=minn+y+x[v];
				q.push(mkp(-dis[v],v));
			}
		}
	}
}

Senshuraku

来源：AT_abc463_f

难度：2127

挺考验基本功的一道题。

令 $k=\max_{1\le i\le 2N}a_i$，最大值可能为 $k$ 或者 $k+1$。根据这两种情况分类讨论。

当最大值为 $k+1$ 时，必然是某些 $a_i=k$ 赢了成为 $k+1$。经过讨论每组两个数 $(x,y),x\lt y$ 的大小情况，我们得到如下几个种类：

1.$x=y=k$，随机选一个都会贡献一个最大值 $k+1$；

2.$x\lt k,y=k$，选 $y$ 才会提供最大值 $k+1$，否则不提供最大值；

3.$y<k$，不会提供最大值 $k+1$。

然后我们接下来分别枚举 $a_i$ 为最大值的时候。由于概率与最大值数量有关，所以我们需要知道最大值的数量。我们发现，对于除了 $a_i$ 所在组以外的组别，其是否提供最大值以及提供最大值的数量只与上文叙述组别种类有关。对于第 1 种最大值必然贡献 $1$；第 2 种根据提供最大值的数量，提供类似一个组合数状物的贡献；第 3 种最大值必然贡献 $0$。这里第 2 种的贡献数量是不确定的，假设贡献了 $i$ 个最大值，则最大值数量为 $sum_1+i$ 。对于 $i$ 的系数是组合数，所以预处理组合数 + 枚举数量可以 $\Theta(n)$ 算出。

当最大值为 $k$ 时，所有 $a_i=k$ 全输了，可能会有部分 $a_i=k-1$ 赢了成为 $k$。同样进行分类：

1.$x=y=k$，只要存在这样的组别就不可能实现，因为无论谁赢都会使最大值变成 $k+1$；

2.$x=k-1,y=k$，必须选 $x$ 才会提供两个最大值 $k$；

3.$x<k-1,y=k$，必须选 $x$ 才会提供一个最大值 $k$；

4.$x=y=k-1$，随机选一个都会贡献一个最大值 $k$；

5.$x\lt k-1,y=k-1$，必须选 $y$ 才会提供一个最大值 $k$，否则不提供最大值；

6.$y\lt k-1$，不会提供最大值 $k+1$。

存在组别 1，那么无解。发现对于第 5 种是自由元，其他的贡献固定，所以可以类似处理 $k+1$ 的情况，假设贡献了 $i$ 个最大值，则最大值数量为 $2sum_2+sum_3+sum_4+i$ 。同理预处理组合数 + 枚举数量。

那么此时我们的算法是 $\Theta(n^2)$ 的。注意到剩下的组的贡献仅与剩下组的各个种类数量相关，等同于 $a_i$ 当前所在组种类相关，所以实际上可以存下当 $a_i$ 当前种类不同时的答案，相同直接 $\Theta(1)$ 引用，无需 $\Theta(n)$ 做。可以优化到 $\Theta(n)$。

接下来大家自行推导吧，就不给出具体系数和代码了。自己推导挺好的。

Random Walk Distance

来源：AT_abc463_g

难度：2452

oonp 怎么还有这种题的。

这是一个组合数前缀和状物。单独处理每次询问需要 $\Theta(n)$。考虑能不能将所有询问混起来做。

考虑单独处理的时候是怎么样的。先扔掉期望，这实际上是 $i$ 号点站了 $\binom{n}{i}$ 个人，然后问所有人到某一个点的距离之和。单独处理的一种做法是从最左端开始移动 $x$，记录当前答案和左右两边各站了多少人。一开始左边没人，右边站了 $2^n$。跨越 $i$ 号点，就要将左右两边站的人数和答案做一次系数为 $\binom{n}{i}$ 的更新。预处理组合数可以简单解决。

现在的问题是要把所有询问整合处理。我们在移动的时候只关照了 $x$ 维度，对于 $n$ 维度目前似乎是没有办法。考虑 $n$ 变到 $n+1$ 的过程，实际上是每一个点的人有丝分裂成人数相同的两拨人分别往左右移了一个。对于远离 $x$ 的点，两拨人左右各移动一格抵消贡献了，实际上贡献恰好翻倍了。如果 $x$ 作为上一轮的点，设当前有 $\binom{n}{i}$ 个人，则贡献为翻倍和 $2\binom{n}{i}$，因为有两拨 $\binom{n}{i}$ 的人从这个点离开走了一步 $\binom{n}{i}$；左边和右边的人都同时翻倍且加上了 $\binom{n}{i}$。如果 $x$ 作为下一轮的点，设左边有 $\binom{n}{j}$ 个人，右边有 $\binom{n}{j+1}$，则贡献仅有翻倍，左边和右边的人都同时翻倍且各减去 $\binom{n}{j}$ 和 $\binom{n}{j+1}$。这不难理解。对于 $n$ 变到 $n-1$ 同理。也就是，我们实际上可以通过维护左边、右边的人数和当前答案去做到变化 $n$ 的复杂度是线性的。

那么更改 $x$ 和 $n$ 移动 $1$ 的复杂度是 $\Theta(1)$ 的。发现这不就是莫队吗。然后莫队直接上。时间复杂度 $\Theta(N\sqrt{N})(N=2\times10^5)$。注意这篇题解为了方便理解把期望扔掉了，实际写代码的时候需要加上期望系数。

Celester 2

来源：AT_abc464_g

难度：2592

感觉这题用反悔贪心做的真的牛完了。我是一个比较蠢的选手，所以这篇题解还是大家喜闻乐见的闵可夫斯基和 + 分治优化 DP。

题目要输出的是改 $x$ 个位置最多能获得多少个 $\text{RS}$。这不一眼 $\Theta(n^2)$，但是似乎没有什么前途。所以交换两维，对偶一下即询问获得 $x$ 个 $\text{RS}$ 最少需要改多少个位置。然后不难证明这个这个函数是单调不减且下凸的（好吧其实我并不会怎么严格证明，但由于这题可以给出最小费用最大流建模，同时可以用来证明函数凸性和反悔贪心正确性）。

关于 DP 状态，处理两个分治区间合并的时候，要关注可能左区间的最后一个元素为 $\text{R}$ 且右区间的最后一个元素为 $\text{S}$ 时，会贡献一个新的 $\text{RS}$。所以设计如下的 DP 状态：

$$f_{l,r,i,0/1,0/1}$$

表示区间 $[l,r]$ 中至少存在 $i$ 个 $\text{RS}$ 且左右端点分别为 $\text{R/S}$ 和 $\text{R/S}$ 最少需要更改的位置数。记得 $l=r$ 且两个 $0/1$ 状态相反时是没有意义的，要特判。

然后用 $\text{vector}$ 维护每个分治区间的函数，合并两个函数的时候根据函数凸性双指针加入，合并的复杂度是线性的。分治共有 $\log$ 层，所以复杂度是 $\Theta(n\log n)$。

vector<int>merge(vector<int>a,vector<int>b,int len,int dl){ // dl=1 时中间可以贡献一个新的 RS，为 -1 时无意义
	vector<int>f(len+1,inf);
	if(dl==-1)return f;
	PER(i,a.size()-1,1)a[i]-=a[i-1];
	PER(i,b.size()-1,1)b[i]-=b[i-1];
	int p=0,q=0,i=dl;
	f[dl]=a[p]+b[q];
	while(p+1<a.size()&&q+1<b.size()&&i+1<=len){ // 根据函数凸性，双指针合并函数
		++i;
		if(a[p+1]<b[q+1])f[i]=f[i-1]+a[++p];
		else f[i]=f[i-1]+b[++q];
	}
	while(p+1<a.size()&&i+1<=len){
		++i;
		f[i]=f[i-1]+a[++p];
	}
	while(q+1<b.size()&&i+1<=len){
		++i;
		f[i]=f[i-1]+b[++q];
	}
	if(dl)f[0]=f[1];
	return f;
}
struct node{
	vector<int>f[2][2];
};
string s;
node solve(int l,int r){
	node res;
	int len=(r-l+1)/2;
	REP(i,0,1)REP(j,0,1)res.f[i][j]=vector<int>(len+1,inf);
	if(l==r){
		res.f[0][0][0]=s[l-1]!='R';
		res.f[1][1][0]=s[l-1]!='S';
		return res;
	}
	int mid=(l+r)>>1;
	node L=solve(l,mid),R=solve(mid+1,r); // 分治下去
	REP(i,0,1)REP(j,0,1)REP(p,0,1)REP(q,0,1){
		int dl=0;
		if(j==0&&p==1)dl=1;
		if(l==mid&&i!=j)dl=-1; // 特判，下行同理
		if(mid+1==r&&p!=q)dl=-1;
		vector<int>v=merge(L.f[i][j],R.f[p][q],len,dl);
		REP(k,0,len)Min(res.f[i][q][k],v[k]);
	}
	return res;
}

---

接下来是最小费用最大流的建模。具体建图方式如下：

• 第一层：源点 $S$。
• 源点 $S$ 向每一个奇数点连 $(1,0)$ 的边。
• 第二层：奇数点。
• 每个奇数点 $k$ 向 $\text{R}$ 和 $\text{S}$ 分别连 $(1,[s_k=\text{S}])$ 和 $(1,[s_k=\text{R}])$ 的边。
• 第三层：奇数点根据选择 $\text{R}$ 和 $\text{S}$ 拆成两个点 $\text{R}k$ 和 $\text{S}k$。
• 每一组相邻的 $k,k+1$ 奇数点 $\text{R/S}$ 向偶数点的 $\text{S/R}$ 连边。
• 第四层：偶数点根据选择 $\text{R}$ 和 $\text{S}$ 拆成两个点 $\text{R}k$ 和 $\text{S}k$。
• 每个偶数拆点 $\text{R}$ 和 $\text{S}$ 向 $k$ 分别连 $(1,[s_k=\text{S}])$ 和 $(1,[s_k=\text{R}])$ 的边。
• 第五层：偶数点。
• 每一个偶数点向汇点 $T$ 连 $(1,0)$ 的边。
• 第六层：汇点 $T$。

Reverse Permutation

来源：AT_abc465_c

难度：443

这个入想着要去噗叽组炸街，所以有了这篇题解。这题讲思路好像没啥意义，所以直接上做法。

提供一个简单的双指针做法。倒序扫描 $S$ 数组，对于答案数组 $A$ 会有一段可能为空的后缀 $p,p+1,\dots,n$。当扫描到第一个 $S_k$ 为 o 时，说明 $[1,k]$ 作为一个整体最后被翻转。由于 $k$ 只被翻转过一次，所以 $k$ 必然填在下标为 $1$ 的位置上，即：

$$A[]=\{k,\text{empty},\dots,\text{empty},k+1,k+2,\dots,n\}$$

。其中，$\text{empty}$ 表示这个位置暂时不确定位置。然后由于 $[1,k]$ 做了一次翻转，所以原先填充 $[k+1,n]$ 时是从右往左填充，现在要换个方向，从左往右填充。当第二次遇到 $S_p$ 为 o 时，需要再次翻转填充的顺序，从左往右变为从右往左。那么只需要维护左右两个指针，初始移动右指针从大到小填充 $[1,n]$。遇到 o 时则换成另外一个指针，即：

$$A[]=\{k,k-1,\dots,p+1,\text{empty},\dots,\text{empty},p,k+1,k+2,\dots,n\}$$

。依此递推，只要是在倒序扫描 $S$ 的过程中出现 o，则变换扫描方向。如果是从左到右，变为从最右边开始往左扫描；如果是从右到左，变为从最左边开始往右扫描。

bool flag=0;int p=1,q=n; // flag = 0 移动右指针，= 1 移动左指针，p,q 分别代表左、右指针
PER(i,n,1){ // 记得倒序
	if(s[i]=='o')flag^=1; // 换一个指针
	if(flag)a[p++]=i; // 左指针从左到右填充值
	else a[q--]=i; // 右指针从右到左填充值
}

Window Records

来源：AT_awtf2026algo_b

难度：?

有趣的高维 DP 题，$\Theta(n^4)$ 做法，吊打 std。

钦定在区间 $[i,i+N-1]$ 内的 $p$ 有 $\max_{i\le k\le p}A_k\le A_p$ 为区间 $[i,i+N-1]$ 的关键点。考虑从右到左滑动窗口，此时只需要关注关键点的位置和数量即可。

具体地，当滑动窗口 $[i+1,i+N]$ 到窗口 $[i,i+N-1]$ 时，设区间 $[k,k+N-1]$ 的集合为 $S(k)$，则 $S(i+1)$ 变换到 $S(i)$ 时会对原本的集合元素造成如下影响：

• 若 $S(i+1)$ 存在 $i+N$，则删去该元素；
• 接着会删除 $S(i+1)$ 的一段前缀（可能为空）；
• 加入元素 $i$。

不难发现，如果固定 $A_{[N+1\dots2N-1]}$ 以及 $|S(i)|$，则 $A_{[1,N]}$ 最多只有一种合法方案，即如果存在合法方案则摆设必然固定。所以我们把重点放在 $A_{[N+1\dots2N-1]}$ 上。关注到在 dp 转移时对于区间 $[N+1,2N-1]$ 只可能有删末尾和前缀。在删前缀的时候前缀具体的在 $A$ 上的位置我们并不关心，为了防止算重以及让后面填充前缀的自由度更高（即能有更多空间填充前缀），让当前前缀尽可能地往前填充，即填满 $[N+1,k]$。由于删前缀和删末尾元素是相对独立的两个操作，所以最好钦定一个删除顺序。发现让 $[i,N]$ 的关键点更多，后面的自由度更高，所以尽可能先删末尾元素，然后删前缀。

设计 dp 状态：

$$f_{i,j,k,p}$$

表示处理到 $S(i)$ 时在 $[i,N]$ 区间有 $j$ 个关键点，在 $[N+1,i+N-1]$ 区间有 $k$ 个关键点且填充部分前缀后还有 $p$ 的空间可以填充。转移的时候先考虑删除末尾元素，即 $k\to k-1,p\to p-1$。然后是删前缀。注意这里删前缀要先把 $j$ 删到 $1$ 才能开始同时减 $k,p$。所以分别对 $j,(k,p)$ 两维做前缀和优化。如果没有变化，只需 $p\to p-1$（因为被压缩了一个后缀空间）。

REP(k,0,a[n]-1)f[n][1][k][n-1]=1;
PER(i,n,2){
	memset(g,0,sizeof g); // 辅助转移数组
	REP(j,1,n-i+1)REP(k,1,i-1)REP(p,k,i-1){
		if(p-1>=k)add(f[i-1][j+1][k][p-1],f[i][j][k][p]); // 不需要做前缀和，即 S(i) 没有删除元素
		g[j+1][k-1][p-1]=f[i][j][k][p];
	}
	PER(j,n-i+1,1)REP(k,0,i-2)REP(p,k,i-2){ // 对 j 做前缀和
		add(g[j][k][p],g[j+1][k][p]);
	}
	PER(k,i-2,1)REP(p,k,i-2){ // 对 (k,p) 做前缀和
		add(g[1][k-1][p-1],g[1][k][p]);
	}
	REP(j,1,n-i+2)REP(k,0,i-2)REP(p,k,i-2){
		add(f[i-1][j][k][p],g[j][k][p]);
		if(j+k>a[i-1])f[i-1][j][k][p]=0; // j+k 为 |S(i)|，不能超过 a_i
	}
}
REP(p,0,n-1)add(dp[n][1],f[n][1][0][p]); // dp 为 [N+1,2N-1] 没有影响部分的转移
PER(i,n-1,1){
	REP(j,1,a[i+1])add(dp[i][j+1],dp[i+1][j]);
	PER(j,n,1)add(dp[i][j],dp[i][j+1]);
	REP(j,a[i]+1,n)dp[i][j]=0;
	REP(j,1,a[i])REP(p,0,i-1)add(dp[i][j],f[i][j][0][p]);
}
int res=0;
REP(j,1,a[1])add(res,dp[1][j]);