题解

本篇只用于记录自己的代码(补题B、C、D)
题解参考这里
或者参考这里

A. Reverse

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 550;

int a[N];

int main()
{
    int T;  cin >>T;
    while (T--)
    {
        int n, x = -1, y = -1;
        bool flag = false;

        cin >> n;
        for (int i = 1; i <= n; i++)    cin >> a[i];
        
        for (int i = 1; i <= n; i++)
        {
            if (a[i] != i && !flag)
            {
                x = i;
                flag = true;
            }
            if (a[i] == x)
            {
                y = i;
                break;
            }
        }

        if (x != -1 && y != -1) reverse(a + x, a + y + 1);

        for (int i = 1; i <= n; i++)  cout << a[i] << ' ';
        cout << endl;
    }
    return 0;
}

B. Odd Swap Sort(奇偶性)

Code

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

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        vector<int> odd, even;

        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            if (x % 2 == 1) odd.push_back(x);
            else even.push_back(x);
        }
        if (is_sorted(odd.begin(), odd.end()) && is_sorted(even.begin(), even.end()))   cout << "YES" << endl;
        else cout << "NO" << endl;  
    }
    return 0;
}

C. Inversion Graph(单调栈/贪心)

Code

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

void solve()
{
    int n; cin >> n;
    stack<int>q;

    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;

        if (q.empty() || x > q.top()) q.push(x);
        else 
        {
            int t = q.top();
            while (!q.empty() && q.top() > x) q.pop();
            q.push(t);
        }
    }
    cout << q.size() << endl;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

D. Big Brush(BFS)

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int,int> PII;
#define endl "\n"
int n, m, col[N][N];
int dx[4] = {0, 0, 1, 1}, dy[4] = {0, 1, 1, 0};
bool vis[N][N];
queue<PII> q;
struct node {int cx, cy, cc;};
 
void color(int x, int y)  // 染色为0(相当于通配符)
{
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        col[xx][yy] = 0;
    } 
}
 
int check(int x, int y)  // 检查四个格子颜色是否相同 
{
    if (x >= 1 && x < n && y >= 1 && y < m)
    {
        unordered_set<int>s;
        for (int i = 0; i < 4; i++)
            if (col[x + dx[i]][y + dy[i]])   s.insert(col[x + dx[i]][y + dy[i]]);  //前面的判断条件可以筛去通配
 
        if (s.size() == 1)  return *s.begin();  // 返回这个颜色
        else return 0;
    }
    else return 0;
}
 
void push(int x, int y)  // 将2 * 2 一共四个一起加入队列
{
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (!vis[xx][yy])
        {
            q.push({xx, yy});
            vis[xx][yy] = true;
        }
    } 
}       
 
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> col[i][j];
 
    vector<node> ans;
    for (int i = 1; i <= n; i++)   // 先找出最后完成的一笔
        for (int j = 1; j <= m; j++)
            if (check(i, j))
            {
                push(i, j);
                ans.push_back({i,j,check(i, j)});
                color(i, j);
                break;
            }
 
    while (q.size())  // 再倒着过去找剩下的
    {
        auto t = q.front();
        q.pop();
 
        for (int i = t.first - 1; i <= t.first + 1; i++)  // 遍历包含(x,y)的2*2网格，其实只有4个，i  = [x-1, y] j  = [y - 1,y] 即可
            for (int j = t.second - 1; j <= t.second + 1; j++)
            {
                if (check(i, j))    
                {
                    push(i, j);
					ans.push_back({i,j,check(i,j)});
                    color(i, j);  // 放入答案
                }
            }
    }
 
    bool fail = false;
    for (int i = 1; i <= n; i++)  // 查看是否还有点没被访问成功过，如果有，说明失败
        for (int j = 1; j <= m; j++)
            if (!vis[i][j])
            {
                fail = true;
                break;
            }
    
    if (fail)   cout << -1 << endl;
    else 
    {
        cout << ans.size() << endl;
 
        reverse(ans.begin(), ans.end());  // 因为是倒着加进去的， 所以也要倒过来输出
        for (auto x : ans)
            cout << x.cx << ' ' << x.cy << ' ' << x.cc << endl;
    }
}
 
int main()
{
    solve();
    return 0;
}