Codeforces Round #768 (Div. 2)
又是卡在D上面了....之后直接跳过去做E还做假了，血亏，当然，肯定是又掉分了....
A. Min Max Swapr
考虑a，b中的最大的数一定是会被max出来，考虑让另一个数小，那么直接将相同位置下大的数都放到一个序列中，小的数放到另一个序列中，保证了另一个数足够小即可。
B. Fun with Even Subarrays
首先可以发现由于都是让前面的数变成后面的数，所以最后一个数是没法改变的。那么也就是说我们只需要考虑将整个序列全部变成最后一个数即可。发现这个操作就是一个倍增的操作，直接枚举就行。同时倍增之后，我们还需要将原本序列中与最后一个数相等的数联合起来即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,a[N];
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
int j=n;
while(j>1&&a[j-1]==a[j]) --j;
if(j==1) {puts("0");continue;}
for(int i=1;i<=20;++i)
{
if((n-j+1)*2>n) {printf("%d\n",i);break;}
j=n-2*(n-j+1)+1;
a[j]=a[n];
while(j>1&&a[j-1]==a[j]) --j;
if(j==1) {printf("%d\n",i);break;}
}
}
return 0;
}
C. And Matching
(像这种构造题，想到啥就直接莽就对了....)
考虑他给的数字，0,1,...,2^k-1，这样的数对于二进制下，就是0,1,10,11,.....,11111.11都凑齐了。首先可以想到的就是如果k是0的话我们完全可以搞，每个数和他对应的取反为一组，这样的话和就是0。(也就是x与n-1-x一组).同时我们发现n-1这个数字很特殊，因为任何数和它相与答案都是本身。那么我们考虑0<=k<n-1的情况，我们可以先让k与n-1一组，得到k，之后剩下的两两组合，使得每一组的答案都是0.如果不想动脑筋的话，可以直接爆搜，发现越小的数越优，就从大到小搜即可。(我比赛时就是这样考虑的。)可现在发现完全没有必要。我们发现在原先的配对中是k与n-1-k一组，0与n-1一组，这里我们是让k与n-1一组，那么让0与n-1-k一组，他们值也为0，剩下的还是按照刚才的准则即可。到这就完了吗？不要完忘了k=n-1的情况。按照刚才的策略，我们考虑怎么快速的凑出来n-1，由于n-1与任何数一组都不是n-1，所以我们选择n-1与n-2一组，这样的话值为n-2，还差1，剩下一个1，怎么凑都行，我是想着优先消耗大数，就指定n-3与一个数与起来为1.剩下的继续爆搜即可。但考虑一下确定性的做法，(爆搜终究不是正道，虽然能过...)，还是考虑他们原本的配对，现在剩下的是0,1，我们考虑让1,3相与他们的值是1，那么剩下的就是0，n-4，他们相与的值是0，剩下的还是按照原本的策略考虑即可。
这里就放下我爆搜的代码吧。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,vis[N],T,k;
vector<pair<int,int> >ve;
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i) vis[i]=0;
ve.clear();
if(k==n-1)
{
vis[n-2]=1;vis[n-1]=1;
ve.push_back({n-2,n-1});
for(int i=n-4;i>=0;--i) if((i&(n-3))==1)
{
vis[i]=1;
vis[n-3]=1;
ve.push_back({i,n-3});
break;
}
if(!vis[n-3]) {puts("-1");continue;}
}
else
{
vis[k]=1;vis[n-1]=1;
ve.push_back({k,n-1});
}
bool flag=true;
for(int i=n-1;i>=0;--i)
{
if(vis[i]) continue;
for(int j=i-1;j>=0;--j) if(!vis[j]&&(i&j)==0)
{
vis[j]=1;vis[i]=1;
ve.push_back({i,j});
break;
}
if(!vis[i]) {flag=false;break;}
}
if(!flag) {puts("-1");continue;}
for(auto x:ve) printf("%d %d\n",x.first,x.second);
}
return 0;
}
D. Range and Partition
又是一道劝退题，当时写到D时还有一个小时，真的是吓到了...（人真的是不能怂啊...）
首先我们考虑如果规定值域[x,y]的情况下，我们怎么划分区间。
比较直观的想法就是我们直接从左到右扫一遍，一旦当前的区间内，值域内的数字大于非值域内数字时，我们就在当前区间为划分。虽然可能划分到最后可能区间不合法，可我们可以考虑合并，因为任意一个合法的区间都是值域内的数字大于非值域内的数字，所以我们将一个合法的区间并入不合法到区间只会使得它更可能合法。按照这种划分方法的话，可以发现每个划分区间内的值域内的数-非值域内的数都为1.这样的话，就得保证这个序列在值域内的数字的个数p-q不在值域内的数字个数>=k.那我们反过来，对不对？就是只要保证了上述条件，一定会有合法的划分的方案。考虑我们每个合法区间的p-q=1.所以我们能够划分的区间数就是整个序列的p-q。只要保证了这个，我们划分的区间个数就一定>=k。如果>k的话，我们直接合并区间即可。
现在我们知道了给定值域下什么情况是可以的，什么情况不可以。我们可以枚举x，对于y而言，发现y越大，显然p是越多的，也更满足题意。可以二分，二分y用前缀和快速判断即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,k,a[N],sum[N],num;
pair<int,int>b[N];
inline bool check(int x,int y)
{
int d=sum[y]-sum[x-1];
if(2*d-n>=k) return true;
return false;
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum[i]=0;
for(int i=1;i<=n;++i) sum[a[i]]++;
for(int i=1;i<=n;++i) sum[i]+=sum[i-1];
pair<int,int>ans;
ans={1,n};
for(int x=1;x<=n;++x)
{
int l=x,r=n;
while(l<r)
{
int mid=l+r>>1;
if(check(x,mid)) r=mid;
else l=mid+1;
}
if(check(x,l))
{
if(l-x<ans.second-ans.first)
ans={x,l};
}
}
num=0;
int x=ans.first,y=ans.second,l=1,sum=0;
for(int i=1;i<=n;++i)
{
if(a[i]>=x&&a[i]<=y) sum++;
else sum--;
if(sum>0)
{
b[++num]={l,i};
sum=0;l=i+1;
}
}
printf("%d %d\n",x,y);
for(int i=1;i<k;++i) printf("%d %d\n",b[i].first,b[i].second);
printf("%d %d\n",b[k-1].second+1,n);
}
return 0;
}