Codeforces Global Round 23

A. Maxmina

显然结果全为0时，结果为NO，若有1，我们通过操作1使长度变为k，里面包含至少1，通过操作2，结果即为YES

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2e5+10;
 4 int a[N];
 5 int main(){
 6     int t;
 7     cin>>t;
 8     while(t--){
 9         int n,k;
10         cin>>n>>k;
11         int flag=0;
12         for(int i=0;i<n;i++){
13             int x;
14             cin>>x;
15             if(x)flag=1;
16         }
17         if(flag)puts("YES");
18         else puts("NO");
19     }
20 }

B. Rebellion

简单的双指针算法，把操作想成交换两个数，每次从前面找到第一个1，从后面找到第一个0，然后交换，以此类推即可

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],ans;
void solve(int l,int r)
{
    while(a[l]==0&&l<r){
        l++;
    }
    while(a[r]==1&&r>l){
        r--;
    }
    if(l>=r)return;
    l++;
    r--;
    ans++;
    solve(l,r);
}
int main(){
    int t;
    cin>>t;
    while(t--){
       int n;
       cin>>n;
       for(int i=0;i<n;i++)a[i]=0;
       for(int i=0;i<n;i++)cin>>a[i];
       ans=0;
       solve(0,n-1);
       cout<<ans<<endl;
    }
}

C. Permutation Operations

我们可以发现最大差值不超过n，我们按照差值排序，差值大的在后面（意味着加的值（下标）的多，可以超过前面），然后输出下标即可

2022-10-16

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef pair<int,int> PII;
vector<PII> v;
int a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        v.clear();
        for(int i=1;i<=n;i++){
            cin>>a[i];
            v.push_back({a[i-1]-a[i],i});
        }
        sort(v.begin(),v.end());
        for(auto it:v)cout<<it.second<<' ';
        cout<<endl;
    }
}