Codeforces Round ＃771 (Div. 2) ABCD|E

A.Reverse

Ideas

Give a $[1,n]$ Permutation , It is required to flip the interval once , Minimize dictionary order . The dictionary order of one operation is the smallest , Then the sequence length from the beginning after the operation should be $+1$.

So it is obviously to find the first misplaced position , The current point number of this position must be greater than its coordinates ( Prove slightly ). Then find the number position that should be placed on this position , Just reverse the interval , This ensures that the sequence is incremented by a number , Minimize dictionary order .

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 600;
int a[N];

inline void solve(){
    
    int n = 0; cin >> n;
    int minpos = 0, maxpos = 0, minn = 10000000, maxx = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = 0;
    for(int i = 1; i <= n; i++){
    
        if(!l){
     if(a[i] != i) l = i; }
        else{
     if(a[i] == l) r = i; }
    }
    reverse(a + l, a + r + 1);
    for(int i = 1; i <= n; i++) cout << a[i] << ' ';
    cout << endl;
    
}

signed main(){
    
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

B.Odd Swap Sort

Ideas

Adding to an odd number allows exchange , So let's discuss it by parity , If there are inverse pairs in odd and even sequences , Then it must not be successful ( Unable to swap locations ).

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

#define yes puts("YES")
#define no puts("NO")

const int N = 100005;
int a[N];

inline void solve(){
    
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int book1 = 0, book2 = 0;
    for(int i = 1; i <= n; i++){
    
        if(a[i] & 1){
    
            if(a[i] < book1){
     no; return; }
            book1 = a[i];            
        }
        else{
    
            if(a[i] < book2){
     no; return; }
            book2 = a[i];
        }
    }
    yes;
}

signed main(){
    
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

C.Inversion Graph

Ideas

The connection between pairs in reverse order , Check the number of connected blocks .

You can do this by maintaining the monotone stack . But there are better ways to write ：

For two connected blocks , The merging condition is that there is at least one reverse order pair in two connected blocks , That is to say, the large node in front will contain the small node in the back . So we just need to sort the entire sequence , Then find the largest $id$ The number of homing times is enough .

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

struct node{
    
    int id, val;
    const bool operator< (const node &aa){
     return val < aa.val; }
}a[N];
//int a[N];

inline void solve(){
    
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].val, a[i].id = i;
    sort(a + 1, a + 1 + n);
    int maxx = 0, cnt = 0;
    for(int i = 1; i <= n; i++){
    
        maxx = max(maxx, a[i].id);
        if(maxx == i) cnt++, maxx = a[i + 1].id;
    }
    cout << cnt << endl;
}

signed main(){
    
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

D.Big Brush

Ideas

The title requires the steps of vat dyeing ... It looks like a simulation .

First, traverse the whole graph , Find the starting point , Then start from the starting point and delete backwards , Get the operation sequence and then output it backwards , It's operation. .

The deletion process can BFS perhaps DFS( Not written ).

Accepted Code

#include <bits/stdc++.h>
#define endl "\n"
const int dxy[] = {
    0, 1}, N = 1010;
int g[N][N];


inline void solve(){
    
    int n, m, cnt = 0; std::cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) std::cin >> g[i][j];
    
    auto check = [&](int x, int y, int res = 0){
    
        if(x >=n || x < 1 || y >= m || y < 1) return 0;
        for(auto i : dxy) for(auto j : dxy){
    
            if(g[x + i][y + j]) res = g[x + i][y + j]; 
        }
        for(auto i : dxy) for(auto j : dxy){
    
            if(g[x + i][y + j] && g[x + i][y + j] != res) return 0; 
        }
        return res;
    };
    
    auto reset = [&](int x, int y){
     
        for(auto i : dxy) for(auto j : dxy) g[x + i][y + j] = 0;
    };

    struct node {
     int x, y, c; };
    std::stack<node> ans;
    std::queue<node> q;

    for(int i = 1; i < n; i++){
    
        for(int j = 1; j < m; j++){
    
            int res = check(i, j);
            if(res){
     q.emplace(node{
    i, j, res}); break; }
        }
    }
    
    while(q.size()){
    
        node now = q.front(); q.pop();
        if(check(now.x, now.y) == now.c){
    
            ans.emplace(now);
            reset(now.x, now.y);
            for(int i = -1; i <= 1; i++){
    
                for(int j = -1; j <= 1; j++){
    
                    int nx = now.x + i, ny = now.y + j, res = check(nx, ny);
                    if(res) q.emplace(node{
    nx, ny, res});
                }
            }
        }
        
    }
    for(int i = 1; i <= n; i++){
    
        for(int j = 1; j <= m; j++){
    
            if(g[i][j]){
     puts("-1"); return; }
        }
    }
    std::cout << ans.size() << endl;
    while(ans.size()){
    
        auto now = ans.top(); ans.pop();
        std::cout << now.x << ' ' << now.y << ' ' << now.c << endl;
    }
}

signed main(){
    
    std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    solve();
    return 0;
}

E.Colorful Operations

Kodori tree + Differential tree array , See blog for details ： CF1638E. Colorful Operations Kodori tree + Differential tree array _HeartFireY The blog of -CSDN Blog