Codeforces Round #768 (Div. 2)
Stuck on D again After that, I jumped directly to do E and made a fake. I lost blood. Of course, I must have lost points again
A. Min Max Swapr
Consider that the largest number in a and b must be max. consider making the other number small. Then directly put the large number in the same position into one sequence and the small number into another sequence to ensure that the other number is small enough.
B. Fun with Even Subarrays
First of all, it can be found that the last number cannot be changed because the previous number is changed into the following number. In other words, we only need to consider turning the whole sequence into the last number. It is found that this operation is a multiplication operation. Just enumerate directly. At the same time, after multiplication, we also need to combine the numbers equal to the last number in the original sequence.
Click to view the code#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
(for structural problems like this, it's right to think directly...)
Consider the number he gave, 0,1, 2 ^ k-1, such a number for binary is 0,1,10,11, 11111.11 is all together. The first thing we can think of is that if K is 0, we can do it. Each number and its corresponding inverse are a group. In this case, the sum is 0. (that is, X and n-1-x are a group) At the same time, we find that the number n-1 is very special, because any number and its phase and the answer are itself. Then we consider the case of 0 < = k < n-1. We can first set K and N-1 to get k, and then combine the rest in pairs so that the answer of each group is 0 If you don't want to use your brain, you can directly explode the search. The smaller the number, the better. You can search from large to small. That's what I thought when I played But now I find it completely unnecessary. We found that in the original pairing, K and n-1-k are a group, and 0 and N-1 are a group. Here, let K and N-1 be a group, then let 0 and n-1-k be a group, and their values are also 0. The rest can be according to the criteria just now. Is it over here? Don't forget the case of k=n-1. According to the strategy just now, we consider how to quickly sum up n-1. Since n-1 and any number are not n-1, we choose n-1 and n-2. In this way, the value is n-2, there is still a difference of 1, and the remaining 1 can be summed up. I want to give priority to consuming large numbers, so I specify that the sum of n-3 and a number is 1 The rest can continue to search. But consider the deterministic approach, (explosive search is not the right way after all, although it can pass...), Or consider their original pairing. Now the rest is 0,1. Let's consider that the value of 1,3 and their value is 1, then the rest is 0, n-4, and their value is 0. The rest can be considered according to the original strategy.
Let's put down my explosive search code here.
#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
It's another persuasion question. There was an hour left when I wrote D. I was really scared (people really can't be counselled...)
First, we consider how to divide the interval if the value range [x,y] is specified.
The more intuitive idea is that we scan it directly from left to right. Once the number in the value domain is greater than that in the non value domain in the current interval, we will divide it into two parts in the current interval. Although it may be illegal to divide into the last possible interval, we can consider merging, because the number in any legal interval is greater than that in the non value domain, so merging a legal interval into an illegal interval will only make it more likely to be legal. According to this division method, it can be found that the number in the value domain - the number in the non value domain in each division interval is 1 In this way, we have to ensure that the number of numbers in the value range of this sequence, p-q, and the number of numbers not in the value range > = K. then we turn it around, right? That is, as long as the above conditions are guaranteed, there will be a legal division scheme. Consider p-q=1 for each legal interval So the interval number we can divide is the p-q of the whole sequence. As long as this is guaranteed, the number of intervals we divide must be > = K. If > k, we can directly merge the intervals.
Now we know what is possible and what is not in a given range of values. We can enumerate x. for y, it is found that the larger y is, the more p is obviously, which is more satisfying. It can be divided into two parts, and the two parts y can be determined by prefix and quick judgment.
#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;
}