~~~↵
A↵
纯暴力，数据量太小↵
https://codeforces.me/contest/2272/problem/A↵
↵
~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
int f[101];↵
int n,k;↵
int ff(vector<int>& a)↵
{↵
int seen[105];↵
memset(seen,0,sizeof seen);↵
int mex=0;↵
for(int i=1;i<=n;i++)↵
{↵
seen[a[i-1]]=1;↵
while(seen[mex])mex++;↵
f[i]=mex;↵
}↵
sort(f+1,f+1+n,greater<int>());↵
return f[k];↵
}↵
void solve()↵
{↵
cin>>n>>k;↵
vector<int>a(n);↵
for(int i=0;i<n;i++)↵
{↵
cin>>a[i];↵
}↵
int t=ff(a);↵
int best=t,ai=-1,aj=-1;↵
for(int i=0;i<n;i++)↵
{↵
for(int j=i+1;j<n;j++)↵
{↵
swap(a[i],a[j]);↵
int tt=ff(a);↵
swap(a[i],a[j]);↵
if(tt>best)↵
{↵
best=tt;↵
ai=i;aj=j;↵
}↵
}↵
}↵
if(ai==-1)↵
{↵
cout<<-1<<endl;↵
}↵
else cout<<ai+1<<" "<<aj+1<<endl;↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~↵
B↵
就是两行都有就不用考虑，偶数个奇数列也不需要考虑，ff/oo||fo/of都可以↵
就是奇数个不可以↵
fff↵
ofo↵
↵
f ff o↵
o o f（奇偶奇也可以）↵
奇偶性的问题考虑小数据就可以了，3个奇，2个奇ok↵
https://codeforces.me/contest/2272/problem/B↵
C↵
一眼二分，比较有思考难度的是就是找到坏格，要看这个有没有被之前新增格包围！！！！！！！！！！！！！！↵
新增格范围a[i]+mid*2!!!!!!!!!!!!!!!!!!!!!!!↵
不要重复加格子↵
https://codeforces.me/contest/2272/problem/C↵
↵
~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
bool check(int mid,vector<int>&a,int x,int n)↵
{↵
int num=0,reach=-1;↵
for(int i=0;i<n;i++)↵
{↵
if((i&&a[i]-a[i-1]<=mid)||(i<n-1&&a[i+1]-a[i]<=mid))continue;↵
if(a[i]>reach)↵
{↵
num++;↵
reach=a[i]+mid*2;↵
if(num>x)return false;↵
}↵
}↵
return true;↵
}↵
void solve()↵
{↵
int n,x;cin>>n>>x;↵
vector<int>a(n);↵
for(int i=0;i<n;i++)↵
{↵
cin>>a[i];↵
}↵
int l=0,r=a[n-1]-a[0]+1;↵
while(l+1<r)↵
{↵
int mid=l+(r-l)/2;↵
if(check(mid,a,x,n))r=mid;↵
else l=mid;↵
}↵
cout<<r<<endl;↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~
A↵
纯暴力，数据量太小↵
https://codeforces.me/contest/2272/problem/A↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
int f[101];↵
int n,k;↵
int ff(vector<int>& a)↵
{↵
int seen[105];↵
memset(seen,0,sizeof seen);↵
int mex=0;↵
for(int i=1;i<=n;i++)↵
{↵
seen[a[i-1]]=1;↵
while(seen[mex])mex++;↵
f[i]=mex;↵
}↵
sort(f+1,f+1+n,greater<int>());↵
return f[k];↵
}↵
void solve()↵
{↵
cin>>n>>k;↵
vector<int>a(n);↵
for(int i=0;i<n;i++)↵
{↵
cin>>a[i];↵
}↵
int t=ff(a);↵
int best=t,ai=-1,aj=-1;↵
for(int i=0;i<n;i++)↵
{↵
for(int j=i+1;j<n;j++)↵
{↵
swap(a[i],a[j]);↵
int tt=ff(a);↵
swap(a[i],a[j]);↵
if(tt>best)↵
{↵
best=tt;↵
ai=i;aj=j;↵
}↵
}↵
}↵
if(ai==-1)↵
{↵
cout<<-1<<endl;↵
}↵
else cout<<ai+1<<" "<<aj+1<<endl;↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
B↵
就是两行都有就不用考虑，偶数个奇数列也不需要考虑，ff/oo||fo/of都可以↵
就是奇数个不可以↵
fff↵
ofo↵
↵
f ff o↵
o o f（奇偶奇也可以）↵
奇偶性的问题考虑小数据就可以了，3个奇，2个奇ok↵
https://codeforces.me/contest/2272/problem/B↵
C↵
一眼二分，比较有思考难度的是就是找到坏格，要看这个有没有被之前新增格包围！！！！！！！！！！！！！！↵
新增格范围a[i]+mid*2!!!!!!!!!!!!!!!!!!!!!!!↵
不要重复加格子↵
https://codeforces.me/contest/2272/problem/C↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
bool check(int mid,vector<int>&a,int x,int n)↵
{↵
int num=0,reach=-1;↵
for(int i=0;i<n;i++)↵
{↵
if((i&&a[i]-a[i-1]<=mid)||(i<n-1&&a[i+1]-a[i]<=mid))continue;↵
if(a[i]>reach)↵
{↵
num++;↵
reach=a[i]+mid*2;↵
if(num>x)return false;↵
}↵
}↵
return true;↵
}↵
void solve()↵
{↵
int n,x;cin>>n>>x;↵
vector<int>a(n);↵
for(int i=0;i<n;i++)↵
{↵
cin>>a[i];↵
}↵
int l=0,r=a[n-1]-a[0]+1;↵
while(l+1<r)↵
{↵
int mid=l+(r-l)/2;↵
if(check(mid,a,x,n))r=mid;↵
else l=mid;↵
}↵
cout<<r<<endl;↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~
