Codeforces Round 987 (Div. 2) 总结
A
常见的套路，将一个序列变为不下降序列所需要改变的值的最小数量，考虑最大能保留多少个，显然是求最长上升子序列，而这题给出的 \(a\) 序列保证不上升，所以只需要考虑相同长度的一段。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=55;
int n;
int a[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0,len=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=a[i-1]) ans=max(ans,len),len=1;
else len++;
}
ans=max(ans,len);
cout<<n-ans<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
B
考虑每个数 \(p_i\) 能否移动到 \(i\) 位置。
首先能交换的值只有 \(p_i-1\) 和 \(p_i+1\)，显然不能连续移动两次，不然比 \(p_i\) 大或小 \(1\) 的数一定不会到该到的位置。因此最多交换一次。再看是否能交换到自己想要的位置，如果有一个不能，那就不可行。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int st=1;
for(int i=1;i<=n;i++)
{
if(a[i]<i&&!(i-a[i]==1&&a[a[i]]==a[i]+1)) st=0;
else if(a[i]>i&&!(a[i]-i==1&&a[a[i]]==a[i]-1)) st=0;
}
if(st) cout<<"Yes\n";
else cout<<"No\n";
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
C
构造题，思路还是比较清晰的。
首先不难想到 \(1,1,2,2,3,3,\dots\) 这样的情况，所以 \(n\) 为偶数时一定成立。
再考虑奇数，由于任意两个相同的馅料之间的距离都要是完全平方数，考虑三个相同的，位置为 \(x,y,z\)，满足 \(y-x=a^2\)，\(z-y=b^2\)，\(z-x=c^2\)，且 \(a,b,c\) 都为正整数，因此有 \(c^2=a^2+b^2\)。
考虑最小的勾股数 \(3,4,5\)。令 \(x=1,y=10,z=26\)，这样剩下的位置就是偶数个，比较好构造了。下面给出一种构造方案：
后面就按偶数的接下去就行了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N];
void solve()
{
cin>>n;
if(n%2==0)
{
int cnt=1;
for(int i=1;i<=n;i+=2) a[i]=a[i+1]=++cnt;
}
else
{
if(n>=27)
{
a[1]=a[10]=a[26]=1;
int cnt=1;
for(int i=2;i<=8;i+=2) a[i]=a[i+1]=++cnt;
for(int i=11;i<=21;i+=2) a[i]=a[i+1]=++cnt;
a[23]=a[27]=++cnt;
a[24]=a[25]=++cnt;
for(int i=28;i<=n;i+=2) a[i]=a[i+1]=++cnt;
}
else
{
cout<<-1<<'\n';
return ;
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
cout<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
D
赛时的清奇想法。
首先发现能跳跃的两个位置是逆序对，因此考虑用并查集维护，并记录集合内最大值与最小值。
再考虑这样一种做法，先遍历一遍数组，目前遇到的最大值为 \(x\)，下标为 \(id\)，加入一个数 \(a_i\)。
- 若 \(a_i>=x\) 更新 \(x\) 和 \(id\)。
- 若 \(a_i<x\) 那么就合并 \(i\) 和 \(id\)。
以最后一组样例为例：
用 \(mx_i\) 表示集合 \(i\) 中最大的 \(a_i\)，\(mi_i\) 表示最小值。
然后考虑合并不同集合，从后往前，如果出现两个不同集合 \(i,j\) 且 \(i<j\)。由前面的过程易知 \(mx_i \le mx_j\)，如果 \(mx_i>mi_j\)，就说明这两个集合可以合并。
那有没有可能出现不是相邻的集合合并呢？答案是否定的，考虑 \(k,i,j\) 三个集合，\(mx_k \le mx_i \le mx_j\)，如果 \(i\) 与 \(j\) 不能合并，则 \(mx_i \le mi_j\)，就会有 \(mx_k \le mx_i \le mi_j\)，显然 \(k\) 与 \(j\) 不能合并。因此每个集合都只能和相邻的集合合并。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int n;
int a[N],ans[N];
int fa[N],mi[N],mx[N];
int find(int x)
{
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
x=fa[x],y=fa[y];
fa[y]=x;
mi[x]=min(mi[x],mi[y]);
mx[x]=max(mx[x],mx[y]);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
fa[i]=i;
mi[i]=mx[i]=a[i];
}
int x=a[1],id=1;
for(int i=2;i<=n;i++)
{
if(a[i]<x) merge(id,i);
else x=a[i],id=i;
}
for(int i=n-1;i>=1;i--)
if(find(i)!=find(i+1)&&mi[find(i+1)]<mx[find(i)])
merge(i,i+1);
for(int i=1;i<=n;i++) cout<<mx[find(i)]<<' ';
cout<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}