Codeforces Round #771 (Div. 2) A B C D

A. Reverse

• Tip：greedy

思路： 字典序最小，显然如果从$1$到$n$扫描，如果遇到$a[i]!=i$，在后面找到$i$所在位置，将其翻转过来即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=510;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int l=0;int r=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        if(n==1){
            cout<<a[1]<<endl;
            continue;
        }
        for(int i=1;i<=n;i++){
            if(a[i]!=i){
                l=i;
                for(int j=l+1;j<=n;j++){
                    if(a[j]==i){
                        r=j;
                        goto GG;
                    }
                }
            }
        }
        GG:;
        if(l){
            for(int i=1;i<l;i++)cout<<a[i]<<' ';
            for(int i=r;i>=l;i--){
                cout<<a[i]<<' ';
            }
            for(int i=r+1;i<=n;i++)cout<<a[i]<<' ';
            cout<<endl;
        }
        else{
            for(int i=1;i<=n;i++)cout<<a[i]<<' ';
            cout<<endl;
        }
    }
    return 0;
}

B. Odd Swap Sort

• Tip：math

思路： 因为只能两数和是奇数才能交换所以必然只有奇数的相邻数是偶数或者偶数的相邻数是奇数才可以交换，那么我们只需要$O(n)$扫描，不断更新前面出现的最大的奇数和偶数。如果在后面碰到当前的奇数或者偶数小于前面统计过的最大的奇数或者偶数。那么注定通过不断交换之后两数相邻，但无法交换。那么最终必然无法形成一个非递减序列。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int ma1,ma2;
    ma1=ma2=0;
    for(int i=1;i<=n;i++){
        if(a[i]%2){
            if(a[i]<ma1){
                cout<<"NO"<<endl;
                return ;
            }
            else ma1=a[i];
        }
        else if(a[i]%2==0){
            if(a[i]<ma2){
                cout<<"NO"<<endl;
                return ;
            }
            else ma2=a[i];
        }
    }
    cout<<"YES"<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C. Inversion Graph

• Tip：math、graphs、dsu

思路： 本题第一眼会以为是dsu，但实则没有必要，一样就一个性质题。$O(n)$扫描，如何判断当前数有没有在之前已经加入一个块？是否需要新建一个块来存放？有两点：1.如果前面出现数中最大的数比当前数大说明当前数一定在块中了，无需新起块。2.如果前面有比前面最大数小的数跑到当前数后面去了，那么一定可以间接的将当前数与前面最大的数链接起来。这个其实也很简单，只需要判断是否$n-1==max$(前面最大数)即可，因为如果$n-1==max$说明$1$~$n-1$的全排列在前面出现过了，那么没有小的数漏到后面去，那么此时就要另起块。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
void solve(){
    int n;
    cin>>n;
    int ma=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    int res=0;
    for(int i=1;i<=n;i++){
        if(ma>a[i])continue;
        else if(ma==i-1){
            res++;
        }
        ma=max(ma,a[i]);
    }
    cout<<res<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D. Big Brush

• Tip：constructive algorithms、greedy

思路： 从后往前$dfs$，官方题解讲的还是比较清楚的，我大致翻译一下。首先去找四个数字相同的块，如果没有说明必定无解。否则就不断进行$dfs$，因为颜色块从头开始会不断被覆盖，所以我们从后往前做，确定了的块把它标记为一个特殊的块，它可以是任意颜色，因为必然在后面会被覆盖掉，所以啥颜色都无所谓。 因为标记过了的块不会重复搜索，所以复杂度是$O(nm)$。代码通俗易懂+注释。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
int n,m;
const int N=1010;
int a[N][N];
int res;
struct Node{
    int x,y,val;
}nodes[N*N];
void dfs(int x,int y){
    if(x<1||y<1||x>=n||y>=m)return ;
    int val=0;
    for(int i=x;i<=x+1;i++)
        for(int j=y;j<=y+1;j++){
            if(a[i][j]){
                if(val&&val!=a[i][j])return ;
                val=a[i][j];
            }
        }
    if(val){
        nodes[++res]={x,y,val};
        for(int i=x;i<=x+1;i++)
            for(int j=y;j<=y+1;j++)a[i][j]=0;
        for(int i=x-1;i<=x+1;i++)
            for(int j=y-1;j<=y+1;j++)dfs(i,j);
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>a[i][j];
    for(int i=1;i<n;i++)//搜索
        for(int j=1;j<m;j++)dfs(i,j);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(a[i][j]){//如果还有a[i][j]!=0说明无法实现
            cout<<"-1"<<endl;
            return 0;
        }
    cout<<res<<endl;//所有情况输出
    for(int i=res;i>=1;i--){
        cout<<nodes[i].x<<' '<<nodes[i].y<<' '<<nodes[i].val<<endl;
    }
    return 0;
}