专题题解 - JOI 2020 Final

打完发现是最简单的 JOI Final。

---

A. 長いだけのネクタイ

难度：$\bigstar$

题目大意：

给定长度为 $n+1$ 的序列 $a_1,\ldots,a_{n+1}$ 和长度为 $n$ 的序列 $b_1,\ldots,b_n$，定义 $a_i$ 和 $b_j$ 匹配的代价为 $\max(0,a_i-b_j)$，对于每个 $a_i$ 求删除它后 $a$ 与 $b$ 完美匹配的最大代价的最小值。

$1\leq n\leq 2\times 10^5$

题目解法：

两个序列的最大代价最小的匹配一定是排序后按照顺序匹配，求出 $\max(0,a_i-b_i)$ 的前缀和以及 $\max(0,a_{i+1}-b_i)$ 的后缀和即可。

时间复杂度为 $O(n\log n)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
int n,a[MAXN],b[MAXN],ida[MAXN],idb[MAXN],pre[MAXN],suf[MAXN],ans[MAXN];
bool cmpa (int x,int y) {return a[x]<a[y];}
bool cmpb (int x,int y) {return b[x]<b[y];}
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n+1;i++) {
		scanf("%d",&a[i]);
		ida[i]=i;
	}
	for (int i=1;i<=n;i++) {
		scanf("%d",&b[i]);
		idb[i]=i;
	}
	sort(ida+1,ida+n+2,cmpa);
	sort(idb+1,idb+n+1,cmpb);
	for (int i=1;i<=n;i++) {
		pre[i]=max(pre[i-1],max(a[ida[i]]-b[idb[i]],0));
	}
	for (int i=n;i>=1;i--) {
		suf[i]=max(suf[i+1],max(a[ida[i+1]]-b[idb[i]],0));
	}
	for (int i=1;i<=n+1;i++) {
		ans[ida[i]]=max(suf[i],pre[i-1]);
	}
	for (int i=1;i<=n+1;i++) {printf("%d ",ans[i]);}
	printf("\n");
	return 0;
}

---

B. JJOOII 2

难度：$\bigstar$

题目大意：

给定长度为 $n$ 的由 $\texttt{J,O,I}$ 组成的字符串 $S$，你可以取其一个子串，然后删去子串中一些字符，使得得到的串为 $k$ 个 $\texttt{J}$，$k$ 个 $\texttt{O}$，$k$ 个 $\texttt{I}$ 依次拼接，求出删去字符的最小值，或报告无解。

$3\leq n\leq 2\times 10^5$

题目解法：

利用双指针求出每个位置后面第 $k$ 个 $\texttt{J,O,I}$ 分别在哪里，然后枚举子串的左端点，可以直接算出子串的最小右端点。

时间复杂度为 $O(n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int n,k,ans,cur[3],r[MAXN][3],sum[MAXN][3];
char c[MAXN];
int main () {
	scanf("%d%d%s",&n,&k,c+1);
	for (int i=1;i<=n;i++) {
		sum[i][0]=sum[i-1][0]+(c[i]=='J');
		sum[i][1]=sum[i-1][1]+(c[i]=='O');
		sum[i][2]=sum[i-1][2]+(c[i]=='I');
	}
	for (int i=1;i<=n+1;i++) {
		for (int j=0;j<=2;j++) {
			while (cur[j]<=n&&sum[cur[j]][j]-sum[i-1][j]<k) {cur[j]++;}
			r[i][j]=cur[j];
		}
	}
	ans=1e9;
	for (int i=1;i<=n;i++) {
		int tmp=r[r[r[i][0]][1]][2];
		if (tmp==n+1) {continue;}
		ans=min(ans,tmp-i+1-k-k-k);
	}
	printf("%d\n",(ans==1e9?-1:ans));
	return 0;
}

---

C. スタンプラリー 3

难度：$\bigstar$

题目大意：

有长度为 $L$ 的环，环上有 $n$ 个邮票，第 $i$ 个邮票在起始位置顺时针走 $x_i$ 的位置，如果要收集则必须在 $t_i$ 时刻前到达 $x_i$。

你的速度为 $1$，从起始位置出发，问最多能收集到多少邮票。

$1\leq n\leq 200, 2\leq L\leq 10^9$

题目解法：

区间 DP，设 $f(l,r,k,o)$ 表示将 $x_i$ 排序后，当前走过的区域覆盖了 $x_1,\ldots,x_l$ 以及 $x_r,\ldots,x_n$ 这些点，并且收集到了 $k$ 个邮票，$o=0$ 表示现在在 $x_l$，$o=1$ 表示现在在 $x_r$，其值为当前的最小时间。

时间复杂度为 $O(n^3)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=210;
int n,lt,ans,x[MAXN],t[MAXN];
ll dp[MAXN][MAXN][MAXN][2];
int main () {
	memset(dp,0x3f,sizeof(dp));
	scanf("%d%d",&n,&lt);
	for (int i=1;i<=n;i++) {scanf("%d",&x[i]);}
	for (int i=1;i<=n;i++) {scanf("%d",&t[i]);}
	x[0]=0,x[n+1]=lt;
	dp[0][n+1][0][0]=dp[0][n+1][0][1]=0;
	for (int l=0;l<=n;l++) {
		for (int r=n+1;r>l;r--) {
			if (l==0&&r==n+1) {continue;}
			for (int k=0;k<=l+(n-r+1);k++) {
				if (l>0) {
					ll tmp=dp[l-1][r][k-1][0]+x[l]-x[l-1];
					if (tmp<=t[l]) {dp[l][r][k][0]=min(dp[l][r][k][0],tmp);}
					else {dp[l][r][k][0]=min(dp[l][r][k][0],dp[l-1][r][k][0]+x[l]-x[l-1]);}
					tmp=dp[l-1][r][k-1][1]+lt-x[r]+x[l];
					if (tmp<=t[l]) {dp[l][r][k][0]=min(dp[l][r][k][0],tmp);}
					else {dp[l][r][k][0]=min(dp[l][r][k][0],dp[l-1][r][k][1]+lt-x[r]+x[l]);}
				}
				if (r<n+1) {
					ll tmp=dp[l][r+1][k-1][1]+x[r+1]-x[r];
					if (tmp<=t[r]) {dp[l][r][k][1]=min(dp[l][r][k][1],tmp);}
					else {dp[l][r][k][1]=min(dp[l][r][k][1],dp[l][r+1][k][1]+x[r+1]-x[r]);}
					tmp=dp[l][r+1][k-1][0]+lt-x[r]+x[l];
					if (tmp<=t[r]) {dp[l][r][k][1]=min(dp[l][r][k][1],tmp);}
					else {dp[l][r][k][1]=min(dp[l][r][k][1],dp[l][r+1][k][0]+lt-x[r]+x[l]);}
				}
				if (dp[l][r][k][0]<0x3f3f3f3f3f3f3f3f) {ans=max(ans,k);}
				if (dp[l][r][k][1]<0x3f3f3f3f3f3f3f3f) {ans=max(ans,k);}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

---

D. オリンピックバス

难度：$\bigstar\bigstar$

题目大意：

给定 $n$ 个点 $m$ 条边的无向图，每条边有长度 $c_i$ 和翻转代价 $d_i$，你可以选择至多一条边进行翻转，使得从 $1$ 走到 $n$ 再走回 $1$ 的最短路加上翻转的边的翻转代价最小。

$2\leq n\leq 200, 1\leq m\leq 50000$

题目解法：

求出 $1,n$ 在原图和反图的最短路，并各求最短路树，翻转一条边时：

• 如果这条边不在四个最短路树上的任何一个，那么可以 $O(1)$ 计算翻转后 $1\to n$ 和 $n\to 1$ 最短路（因为 $1,n$ 出发和到达的最短路都不会变大）；
• 否则，由于在最短路树上的边只有 $O(n)$ 条，每次暴力重新 dijkstra。

时间复杂度为 $O(n^3+nm)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=210,MAXM=50010;
int n,m,u[MAXM],v[MAXM],c[MAXM],d[MAXM],w[MAXN][MAXN],dis[MAXN],las[MAXN],vis[MAXN];
int d1[MAXN],d2[MAXN],d3[MAXN],d4[MAXN],f1[MAXN],f2[MAXN],f3[MAXN],f4[MAXN];
ll ans;
void dijk (int s) {
	memset(dis,0x3f,sizeof(dis));
	memset(las,0,sizeof(las));
	memset(vis,0,sizeof(vis));
	dis[s]=las[s]=0;
	for (int i=1;i<=n;i++) {
		int r=0;
		for (int j=1;j<=n;j++) {
			if (!vis[j]&&(r==0||dis[j]<dis[r])) {r=j;}
		}
		vis[r]=1;
		for (int j=1;j<=n;j++) {
			if (dis[j]>dis[r]+w[r][j]) {
				dis[j]=dis[r]+w[r][j];
				las[j]=r;
			}
		}
	}
	return;
}
bool chk (int i) {
	if (f1[v[i]]==u[i]&&d1[v[i]]==d1[u[i]]+c[i]) {return 1;}
	if (f2[v[i]]==u[i]&&d2[v[i]]==d2[u[i]]+c[i]) {return 1;}
	if (f3[v[i]]==u[i]&&d3[v[i]]==d3[u[i]]+c[i]) {return 1;}
	if (f4[v[i]]==u[i]&&d4[v[i]]==d4[u[i]]+c[i]) {return 1;}
	return 0;
}
int main () {
	scanf("%d%d",&n,&m);
	memset(w,0x3f,sizeof(w));
	for (int i=1;i<=n;i++) {w[i][i]=0;}
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d%d",&u[i],&v[i],&c[i],&d[i]);
		w[u[i]][v[i]]=min(w[u[i]][v[i]],c[i]);
	}
	dijk(1);
	for (int i=1;i<=n;i++) {f1[i]=las[i],d1[i]=dis[i];}
	dijk(n);
	for (int i=1;i<=n;i++) {f2[i]=las[i],d2[i]=dis[i];}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=i;j++) {swap(w[i][j],w[j][i]);}
	}
	dijk(1);
	for (int i=1;i<=n;i++) {f3[i]=las[i],d3[i]=dis[i];}
	dijk(n);
	for (int i=1;i<=n;i++) {f4[i]=las[i],d4[i]=dis[i];}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=i;j++) {swap(w[i][j],w[j][i]);}
	}
	ans=d1[n]+d2[1];
	for (int i=1;i<=m;i++) {
		if (chk(i)) {
			memset(w,0x3f,sizeof(w));
			swap(u[i],v[i]);
			for (int j=1;j<=m;j++) {w[u[j]][v[j]]=min(w[u[j]][v[j]],c[j]);}
			dijk(1);
			int tmp=dis[n];
			dijk(n);
			ans=min(ans,0ll+tmp+dis[1]+d[i]);
			swap(u[i],v[i]); 
		} else {
			ans=min(ans,0ll+min(d1[n],d1[v[i]]+d4[u[i]]+c[i])+min(d2[1],d2[v[i]]+d3[u[i]]+c[i])
			+d[i]);
		}
	}
	if (ans>=0x3f3f3f3f) {printf("-1\n");}
	else {printf("%lld\n",ans);}
	return 0;
}

---

E. 火事

难度：$\bigstar\bigstar$

题目大意：

给定长度为 $n$ 的序列 $S_1,\ldots,S_n$，初始时间为 $0$，每过一秒，所有 $S_i$ 会变成上一秒 $S_i$ 与 $S_{i-1}$ 的最大值（$S_1$ 不变）。

现在有 $q$ 个询问，每次询问第 $t$ 秒后 $S_l+\ldots+S_r$ 的值。

$1\leq n,q\leq 2\times 10^5$

题目解法：

不妨认为 $S_i$ 是排列（否则可以将相同的元素强制给定一个序），一个简单的结论是：任意时刻某个数出现的位置是一段连续区间（可能为空），并且不同的数出现的顺序等同于在初始序列中的顺序，这一点不难归纳证明。

同时，$t$ 时刻处在 $r$ 的数就是 $[r-t,r]$ 中的最大值，可以直接求出，不妨设为 $S_p$。

所以假设 $t$ 时刻 $S_i$ 出现的区间为 $[a_i,b_i]$，那么：

$$S_1+\ldots+S_r=\sum\limits_{i=1}^{p-1}\Big((b_i-a_i+1)\times S_i\Big)+(r-a_p+1)\times S_p$$

所以我们可以按时间扫描，对于所有 $i$ 维护 $a_i$ 和 $b_i$ 的变化，支持区间查询 $\sum (b_i-a_i+1)\times S_i$ 即可。

分析发现 $a_i$ 和 $b_i$ 只与 $i$ 之前第一个比 $S_i$ 大的数 $S_{L_i}$ 和 $i$ 之后第一个比 $S_i$ 大的数 $S_{R_i}$ 有关，可以表示成常数段分段线性函数，用线段树分别维护斜率之和以及截距之和即可。

时间复杂度为 $O((n+q)\log n)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
struct Query {
	int l,r,t,id;
	ll ans;
}q[MAXN];
struct Event {
	int pos,k,b,t;
	Event (int u=0,int v=0,int w=0,int z=0) {pos=u,k=v,b=w,t=z;}
}e[MAXN*4];
int n,qu,cnt,a[MAXN],lg[MAXN],pre[MAXN],nx[MAXN],st[MAXN][20];
ll sum[2][MAXN*4];
stack <int> s;
bool cmp1 (Query a,Query b) {return a.t<b.t;}
bool cmp2 (Query a,Query b) {return a.id<b.id;}
bool cmp3 (Event a,Event b) {return a.t<b.t;}
int query (int l,int r) {
	l=max(l,1);
	int k=lg[r-l+1];
	return (a[st[l][k]]>a[st[r-(1<<k)+1][k]]?st[l][k]:st[r-(1<<k)+1][k]);
}
void modify (int p,int l,int r,int pos,ll v,int k) {
	if (l==r) {sum[k][p]=v;return;}
	int mid=(l+r)>>1;
	if (pos<=mid) {modify(p<<1,l,mid,pos,v,k);}
	else {modify((p<<1)|1,mid+1,r,pos,v,k);}
	sum[k][p]=sum[k][p<<1]+sum[k][(p<<1)|1];
	return;
}
ll query (int p,int l,int r,int xl,int xr,int k) {
	if (xr<l||r<xl) {return 0;}
	if (xl<=l&&r<=xr) {return sum[k][p];}
	int mid=(l+r)>>1;
	return query(p<<1,l,mid,xl,xr,k)+query((p<<1)|1,mid+1,r,xl,xr,k);
}
int main () {
	scanf("%d%d",&n,&qu);
	lg[0]=-1;
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		lg[i]=lg[i>>1]+1,st[i][0]=i;
	}
	for (int i=1;i<=18;i++) {
		for (int j=1;j+(1<<i)-1<=n;j++) {st[j][i]=(a[st[j][i-1]]>a[st[j+(1<<(i-1))][i-1]]
												   ?st[j][i-1]:st[j+(1<<(i-1))][i-1]);
		}
	}
	for (int i=1;i<=n;i++) {
		while (s.size()&&a[i]>=a[s.top()]) {nx[s.top()]=i;s.pop();}
		pre[i]=(s.size()?s.top():0);
		s.push(i);
	}
	for (int i=1;i<=n;i++) {
		if (nx[i]==0) {nx[i]=n+1;}
		if (pre[i]==0) {
			e[++cnt]=Event(i,1,1,0);
			e[++cnt]=Event(i,0,nx[i]-i,nx[i]-i);
		} else {
			e[++cnt]=Event(i,1,1,0);
			if (i-pre[i]>nx[i]-i) {
				e[++cnt]=Event(i,0,nx[i]-i,nx[i]-i);
				e[++cnt]=Event(i,-1,nx[i]-pre[i]-1,i-pre[i]);
			} else if (i-pre[i]==nx[i]-i) {
				e[++cnt]=Event(i,-1,nx[i]-pre[i]-1,i-pre[i]);
			} else {
				e[++cnt]=Event(i,0,i-pre[i],i-pre[i]);
				e[++cnt]=Event(i,-1,nx[i]-pre[i]-1,nx[i]-i);
			}
			e[++cnt]=Event(i,0,0,nx[i]-pre[i]);
		}
	}
	for (int i=1;i<=qu;i++) {
		scanf("%d%d%d",&q[i].t,&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+qu+1,cmp1);
	sort(e+1,e+cnt+1,cmp3);
	int cura=1,curb=1;
	for (int i=0;i<=n;i++) {
		while (cura<=cnt&&e[cura].t==i) {
			int tmp=e[cura].pos;
			modify(1,1,n,tmp,1ll*e[cura].k*a[tmp],0);
			modify(1,1,n,tmp,1ll*e[cura].b*a[tmp],1);
			cura++;
		}
		while (curb<=qu&&q[curb].t==i) {
			int tmp=query(q[curb].r-i,q[curb].r);
			int nl=max(tmp,pre[tmp]==0?0:pre[tmp]+i+1);
			q[curb].ans+=1ll*(q[curb].r-nl+1)*a[tmp];
			q[curb].ans+=1ll*query(1,1,n,1,tmp-1,0)*i+query(1,1,n,1,tmp-1,1);
			if (q[curb].l==1) {curb++;continue;}
			q[curb].r=q[curb].l-1;
			tmp=query(q[curb].r-i,q[curb].r);
			nl=max(tmp,pre[tmp]==0?0:pre[tmp]+i+1);
			q[curb].ans-=1ll*(q[curb].r-nl+1)*a[tmp];
			q[curb].ans-=1ll*query(1,1,n,1,tmp-1,0)*i+query(1,1,n,1,tmp-1,1);
			curb++;
		}
	}
	sort(q+1,q+qu+1,cmp2);
	for (int i=1;i<=qu;i++) {printf("%lld\n",q[i].ans);}
	return 0;
}