Codeforces Round 987 (Div. 2) Summary
A
The common trope, the minimum number of values that need to be changed to change a sequence into a non-declining sequence, considers the maximum number that can be retained, and obviously seeks the longest ascending subsequence, which is given by the question\(a\) The sequence is guaranteed not to rise, so only a segment of the same length needs to be considered.
#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("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
B
Consider each number\(p_i\) Can you move to\(i\) Location.
The only values that can be exchanged in the first place are\(p_i-1\) cap (a poem)\(p_i+1\), obviously it can't be moved twice in a row, or else it's better than\(p_i\) Large or small\(1\) The number of numbers must not come to the position where it should. So swap at most once. Then see if you can swap to the position you want, if one of them can't, then it's not feasible.
#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("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
C
Constructed questions with still clearer ideas.
It's not hard to think of\(1,1,2,2,3,3,\dots\) Such is the case, so\(n\) must hold for even numbers.
Considering the odd numbers again, since the distance between any two identical fillings is if a perfect square number, consider three identical ones, with position\(x,y,z\)fulfillment\(y-x=a^2\)，\(z-y=b^2\)，\(z-x=c^2\)and\(a,b,c\) are positive integers, so there are\(c^2=a^2+b^2\)。
Consider the smallest collinear number\(3,4,5\)The make sth. happen\(x=1,y=10,z=26\), so that the remaining positions are even ones, which are better constructed. One construction scheme is given below:
Just pick up afterward at even numbers.
#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("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
D
Clean thoughts during the race.
The first two positions that can be jumped are found to be in inverse order pairs, so consider maintaining them with a concatenated set and record the maximum and minimum values within the set.
Consider again such an approach, traversing the array once, the maximum value encountered so far is\(x\)The subscripts are\(id\)Add a number to the list.\(a_i\)。
- as\(a_i>=x\) update\(x\) cap (a poem)\(id\)。
- as\(a_i<x\) Then merge.\(i\) cap (a poem)\(id\)。
Take the last set of samples as an example:
expense or outlay\(mx_i\) denote the set (math.)\(i\) largest\(a_i\)，\(mi_i\) Indicates the minimum value.
Then consider merging different sets, from back to front, if two different sets occur\(i,j\) both (... and...)\(i<j\)The It is easy to see from the previous process\(mx_i \le mx_j\)If\(mx_i>mi_j\), it is shown that the two sets can be merged.
So is it possible to have a merger of sets that are not adjacent? The answer is no, consider\(k,i,j\) Three sets.\(mx_k \le mx_i \le mx_j\)If\(i\) together with\(j\) Cannot be merged, then\(mx_i \le mi_j\)And there will be\(mx_k \le mx_i \le mi_j\)Obviously.\(k\) together with\(j\) cannot be merged. Therefore each set can only be merged with neighboring sets.
#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("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}