专栏文章

题解：CF2053H Delicate Anti-monotonous Operations

IIvanZhang2009
CF2053H题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqmi3f2
此快照首次捕获于
2025/12/04 07:13
3 个月前
此快照最后确认于
2025/12/04 07:13
3 个月前
查看原文
本题本来可以出构造方案但是最后只要最小化步数，很良心吧！
就是样例给的有点少。
先特判初始不能操作和初始已经全部是 ww 的情况。手玩一下，发现大多数情况都有最大值为 nw−1nw-1。可以发现 w=2w=2 是一个特殊的情况，所有 1,21,2 的连续段在最优策略下都不会改变，因为不可能删掉两个连续段之间的间隔，最终最大值为 2n2n 减去 11 的段数，最小操作次数就是第一问答案减掉原来的和，因为每个 11 都要操作一次变成 22，一次只能操作一个。
注意到剩下的情况都有答案为 nw−1nw-1。考虑一个简单的构造：找到任意一个操作的起点，先把它扩展到边上，即每次把 a a b ... 改成 a b b ... 然后继续下去。此时得到一个边上的可操作点，我们按相同的方式拓展即可。例如当前的连续段 a a b，在 b≠wb\neq w 的时候我们直接把两个 aa 改成 w,bw,b 即可；否则可以先改成 w−1,ww-1,w，然后把后两个 ww 改成 w−1,w−2w-1,w-2，然后把两个 w−1w-1 改成 w,w−2w,w-2。注意到此时用到了第三个数，所以 w=2w=2 的时候不能如此操作。
这样已经构造出一个合法解，且可以发现一般来说都可以让最后的 w−1w-1 放在末尾，除非后面有一个长的 ww 连续段。考虑证明的话就是如果 w−1w-1 在中间，需要把两个连续段向两边扩展再合并，分析发现操作次数远远更劣。我们考虑枚举它放在哪个边上，然后做法变成取离开头最近的连续段移动到边上，然后再扩展。这里有一个小细节，如果枚举到的一边上有若干个 ww，可以将其视作连续段，也可以将其直接忽略。
接下来是一些小细节。
  • 我们考虑一段较长的 ww 怎么处理。例如 w=9w=9，序列为 1191199，11991199，119991199，11999991199。只有一个 ww 的时候可以 119，899，877，887，977；有两个 ww 的时候可以先处理掉这两个，然后按朴素做法做；有更多 ww 的时候发现若有偶数个则两两消掉，否则 11999，11199 来处理掉第一个，后面照旧。
  • 更令人难受的细节是在一开始把相同段推到边缘时，把后面的不用的元素改成什么。可以发现不改成 ww 一般是更优的，但是如果起点的附近又是一个 ww 的连续段，可以考虑把奇数变成偶数减小后续的次数。
  • 上面说的一个细节：两侧都有 ww 连续段。一个细节是如果边上有两个 ww 可以视其为相同数，使得次数进一步减小。
关于如何具体证明这是最小步数，其实手玩各个 case 的时候已经可以感受到了。更具体地，写个优秀的拍子就可以对拍证明了！优秀的暴力写法在文章最下面。
提供一个我花了两个小时写的代码。
CPP
#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define speMOD      2933256077ll
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
int n,w,N;
int a[200005],b[200005];
int solve(){
	int x=0,ans=0;
	REP(i,1,n)if(b[i]==b[i-1]){
		x=i-1;break;
	}
	int m=n;while(b[m-1]==w-1)--m;//>=m 的都是 w
	//先把 same 推到最边上
	ans+=x;//x x+1 m
	int f=m<=x+2,g=0,h=0;
	if(m<=x)return 1e18;
	if(!f&&x){
		int len=x+2;
		while(len<n&&b[len]==w-1)++len;
		if(len==x+3)g=1;
		else g=0;
	}
	if(g){
		if(b[x-1]!=w-1)b[x+1]=w-1,b[x]=b[x-1],--x;
		else ans+=2,b[x+2]=b[x]? b[x]-1:1;
	}
	for(int i=x-1;i>=0;--i){
		if(!i&&b[i]==w-1){--ans;h=1;break;}
		if(b[i]==w-1)f=0;
		if(!f)b[i+2]=b[i]? b[i]-1:1;
		else b[i+2]=w-1;
		b[i+1]=b[i];
	}
	if(h)x=1;
	else{
		x=0;
		if(b[0]==w-1){while(x+2<n&&b[x+2]==b[x+1])++x;if(x+3<n&&b[x+2]==b[x+3])x+=2;}
	}
	//b[x]=b[x+1], 目标推进 b[x+2]
	while(x+1<m){
		if(x+2==m)return ++ans;
		if(b[x]==w-1&&b[x+1]==w-1&&b[x+2]==w-1){++x;continue;}
		if(b[x+2]!=w-1){
			b[x]=w-1;b[x+1]=b[x+2];++ans;++x;
			continue;
		}
		//9119
		// x  
		if(b[x+3]==w-1){
			if(x+4<n&&b[x+4]==w-1&&(x+5>=n||b[x+5]!=w-1)){
				//911999 911199 991199
				ans+=2;swap(b[x],b[x+2]);++x;
			}else{
				//91199 91188 99888 99988
				ans+=3;
				b[x]=b[x+1]=w-1;b[x+2]=b[x+3]=w-2;
				x+=2;
			}
		}else{
			//91191 92991 92211 99111 99911
			ans+=4;b[x]=b[x+1]=w-1;b[x+2]=b[x+3];
			x+=2;
		}
	}
	return ans;
}
int spesolve(){
	N=n;
	REP(i,0,n)b[i]=a[i];
	if(b[0]==w-1&&b[1]==w-1){
		int x=0,y=n-1;
		while(b[x]==w-1)++x;
		while(b[y]==w-1)--y;
		int f=0;
		REP(i,x+1,y+1)if(b[i]==b[i-1])f=1;
		if(!f){
			n=y+1;
		}else{
			f=0;
			REP(i,x+1,n)if(b[i]==b[i-1])f=1;
			if(f){
				int cur=solve();
				REP(i,0,n)b[i]=a[i];
				n-=x;
				REP(i,0,n)b[i]=b[i+x];
				return min(cur,solve());
			}
		}
	}
	return solve();
}
void Main() {
	cin>>n>>w;
	REP(i,0,n)cin>>a[i];
	if(w==2){
		int ans=0;
		REP(i,1,n){
			if(a[i]==1&&a[i-1]==1)a[i-1]=2,++ans;
		}
		int res=0;
		REP(i,0,n)res+=a[i];
		cout<<res<<' '<<ans<<endl;
		return;
	}
	bool f=1;int s=0;
	REP(i,1,n)if(a[i]==a[i-1])f=0;
	REP(i,0,n)s+=a[i];
	if(f||s>=n*w-1){
		cout<<s<<' '<<0<<endl;
		return;
	}
	cout<<n*w-1<<' ';
	if(w>4){
		int lst=-1,op=1;
		REP(i,0,n)if(a[i]<w-1){
			if(lst!=a[i])op^=3,lst=a[i];
			a[i]=op;
		}else a[i]-=w-4;
		w=4;
	}
	REP(i,0,n)--a[i];
	if(n==2)over(1)
	int cans=spesolve();n=N;
	reverse(a,a+n);
	cans=min(cans,spesolve());
	over(cans)
}
void TC() {
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
注意到本题细节超级多。我们考虑一个优秀的暴力方便我们对拍调试。注意到我们只关心 =w=w，=w−1=w-1 和更小的数以及其中的相等关系。我们保留 w,w−1w,w-1，把剩下的数标为 1,21,2，其中第一个数标为 11，后面的数根据“和前一个数是否相等”来决定是 11 或 22。这样可以得到一个 O(4npolyn)O(4^n\mathrm{poly}n) 做法，可以很方便的对拍！这个东西在上面的代码里也实现了。
实际上在特判掉很多 corner case 之后 w−1w-1 也是不重要的，可以变成 w=3w=3，但是需要更多特判细节，容易写错。时间复杂度 O(3npolyn)O(3^n\mathrm{poly}n)。具体实现可以用 33 进制数记录状态，用 bfs 实现最小步数。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...