题解:AT_arc187_a [ARC187A] Add and Swap

AK_400

2024-11-18 08:36:47

Solution

首先掏出一张草稿纸,随便写几种情况,发现可以对 i 进行两次操作后可以将 a_i,a_{i+1} 都加上 k

i i+1
a_i a_{i+1}
a_{i+1}+k a_i
a_i+k a_{i+1}+k

于是有了这样一个思路:枚举 i\in(1,n),如果 a_i<a_{i-1},那么反复增加 a_i,a_{i+1},直到 a_i\ge a_{i-1}

看上去很对,但是问题来了,没有办法对 n 操作,如果最后 a_{n-1}>a_n,是没有办法解决的。

继续手玩,发现对于长度为 len 的区间 [l,r] 可以通过 lenl,l+1,l+2,\cdots,r-2,r-1 操作对区间加 (len-1)\cdot k

一次 l,l+1,l+2,\cdots,r-2,r-1 操作的过程。 l l+1 \cdots r
a_l a_{l+1} \cdots a_r
a_{l+1}+k a_l \cdots a_r
\vdots \vdots \ddots \vdots
a_{l+1}+k a_{l+2}+k \cdots a_1
|$l$|$l+1$|$\cdots$|$r$| |:-:|:-:|:-:|:-:| |$a_l$|$a_{l+1}$|$\cdots$|$a_r$| |$a_{l+1}+k$|$a_{l+2}+k$|$\cdots$|$a_l$| |$a_{l+2}+2\times k$|$a_{l+3}+2\times k$|$\cdots$|$a_{l+1}+k$| |$\vdots$|$\vdots$|$\ddots$|$\vdots$| |$a_{l}+(len-1)\cdot k$|$a_{l+1}+(len-1)\cdot k$|$\cdots$|$a_r+(len-1)\cdot k$| 于是我们可以枚举 $i\in(1,n)$,如果 $a_i<a_{i-1}$,那么反复增加 $a_i,a_{i+1},\cdots,a_n$,直到 $a_i\ge a_{i-1}$,这样就解决了原本 $a_{n-1}\le a_n$,但因为一些操作导致 $a_{n-1}>a_n$ 的问题,因为 $a_{n-1}$ 和 $a_n$ 总是一起增加,所以相对大小关系不变。 如果刚开始就有 $a_{n-1}>a_n$ 怎么办? 显然,如果无法让它俩有序就无解。 当 $n>2$ 时一定有解,反复对 $n-1$ 操作直到 $a_n\ge a_{n-2}$,然后对 $n-2$ 操作,这样就有 $a_n\ge a_{n-1}$。 否则只需要对 $1$ 做一次操作,如果 $a_n\ge a_{n-1}$ 则有解,否则无解。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int n,k,a[100]; vector<int>ans; void add(int pos){//后缀加 int len=n-pos+1; for(int i=1;i<=len;i++){ for(int j=pos;j<n;j++)ans.push_back(j); } for(int i=pos;i<=n;i++)a[i]+=k*(len-1); } void slv(){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; if(a[n-1]>a[n]){ if(n==2){ swap(a[n],a[n-1]);//对1做一次操作 a[n-1]+=k; if(a[n-1]<=a[n])cout<<"Yes\n1\n1";//不降则有解 else cout<<"No";//下降则无解 return; } while(a[n]<a[n-2]){ a[n]+=k; a[n-1]+=k; ans.push_back(n-1),ans.push_back(n-1); } swap(a[n-1],a[n-2]); a[n-2]+=k; ans.push_back(n-2); } for(int i=2;i<n;i++){ while(a[i]<a[i-1])add(i);//后缀加直到比上一个大 } cout<<"Yes"<<endl; cout<<ans.size()<<endl; for(int x:ans)cout<<x<<" "; } signed main(){ slv(); return 0; } ```