题解：CF2053H Delicate Anti-monotonous Operations
IvanZhang2009 · · 题解
本题本来可以出构造方案但是最后只要最小化步数，很良心吧！
就是样例给的有点少。
先特判初始不能操作和初始已经全部是
注意到剩下的情况都有答案为 a a b ... 改成 a b b ... 然后继续下去。此时得到一个边上的可操作点，我们按相同的方式拓展即可。例如当前的连续段 a a b，在
这样已经构造出一个合法解，且可以发现一般来说都可以让最后的
接下来是一些小细节。
- 我们考虑一段较长的
w 怎么处理。例如w=9 ，序列为1191199，11991199，119991199，11999991199。只有一个w 的时候可以119，899，877，887，977；有两个w 的时候可以先处理掉这两个，然后按朴素做法做；有更多w 的时候发现若有偶数个则两两消掉，否则11999，11199来处理掉第一个，后面照旧。 - 更令人难受的细节是在一开始把相同段推到边缘时，把后面的不用的元素改成什么。可以发现不改成
w 一般是更优的，但是如果起点的附近又是一个w 的连续段，可以考虑把奇数变成偶数减小后续的次数。 - 上面说的一个细节：两侧都有
w 连续段。一个细节是如果边上有两个w 可以视其为相同数，使得次数进一步减小。
关于如何具体证明这是最小步数，其实手玩各个 case 的时候已经可以感受到了。更具体地，写个优秀的拍子就可以对拍证明了！优秀的暴力写法在文章最下面。
提供一个我花了两个小时写的代码。
#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;
}注意到本题细节超级多。我们考虑一个优秀的暴力方便我们对拍调试。注意到我们只关心
实际上在特判掉很多 corner case 之后