Codeforces Round ＃771 (Div. 2)---A-D

A. Reverse— thinking

The question ：
Give me a 1 ~ n An array of full permutations , Find any left endpoint l And right endpoint r, take l ~ r Reverse the number of the interval , Find the new array with the smallest dictionary order

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
#define int long long

int a[510];
void solve()
{
    
	int n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)cin>>a[i];
	int l=1,r=1;
	for(int i=1;i<=n;i++)
	{
    
		if(a[i]>i)
		{
    
			l=i;
			break;
		}
	}
	for(int i=1;i<=n;i++)
	{
    
		if(a[i]==l)
		{
    
			r=i;
			break;
		}
	}
	
	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;
}
signed main()
{
    
   int T;
   scanf("%lld",&T);
   while(T--)solve();
}

B. Odd Swap Sort— thinking

The question ：
Give a set of numbers , When the sum of two adjacent numbers is odd, it can be exchanged , Ask if you can operate several times , Make the original array into a non descending sequence
Ideas ：
Parity can be judged , If there is something bigger in the front than in the back, you must switch to the back , But both are even numbers or odd numbers , Cannot exchange , So the array is divided into odd and even sequences , If both odd and even numbers do not fall, the requirements are met

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 100010;

int a[N];
void solve()
{
    
	int n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	bool f=true;
	
	int maxv1=0,maxv2=0;
	for(int i=1;i<=n;i++)
	{
    
		if(a[i]&1)
		{
    
			if(maxv1>a[i])
			{
    
				f=false;
				break;
			}
			maxv1=a[i];
		}
		else
		{
    
			if(maxv2>a[i])
			{
    
				f=false;
				break;
			}
			maxv2=a[i];
		}
	}
	
	if(f)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
signed main()
{
    
   int T;
   scanf("%lld",&T);
   while(T--)solve();
}

C. Inversion Graph— greedy

The question ：
One by 1~n An array of full permutations p
If meet $i<jAndpi>pj$ be i and j One side , Ask how many connected blocks there are at last
Ideas ：
It is easy to find a property ：
If a number has a larger number in front of it, it must be in the connected block of that larger number
And because it is full arrangement , Let's just traverse

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

int a[N];
int n;
void solve()
{
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	int res=0;
	int maxv=0;
	for(int i=1;i<=n;i++)
	{
    
		if(maxv<i)res++;
		maxv=max(maxv,a[i]);
	}
	cout<<res<<endl;
}
signed main()
{
    
   int T;
   scanf("%d",&T);
   while(T--)solve();
}

D. Big Brush—bfs

The idea is very simple, and the key is to realize

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
void solve()
{
    
	int n,m;
	cin>>n>>m;
	vector<vector<int>>a(n+1);
	for(int i=1;i<=n;i++)
	{
    
	 	a[i].resize(m+1);
	 	for(int j=1;j<=m;j++)cin>>a[i][j];
	}
	auto equal = [&](int x,int y)
	{
    
	 	int col=0;
	 	if(x<=0||x>=n||y<=0||y>=m)return make_pair(false,col);
	 	set<int>s;
	 	for(auto it:{
    a[x][y],a[x+1][y],a[x][y+1],a[x+1][y+1]})
	 		if(it!=-1)s.insert(it),col=it;
	 		return make_pair(s.size()==1,col);
	};
	
	auto paint = [&](int x,int y,int col)
	{
    
		a[x][y]=a[x+1][y]=a[x][y+1]=a[x+1][y+1]=col;
	};
	
	queue<tuple<int,int,int>>q;
	vector<tuple<int,int,int>>path;
	
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++)
		{
    
			auto [res,col] = equal(i,j);
			if(res)
			{
    
				q.push({
    i,j,col});
				path.push_back({
    i,j,col});
				paint(i,j,-1);
			}
		}
	while(q.size())
	{
    
		auto [x,y,val] = q.front();
		q.pop();
		for(int i=x-1;i<=x+1;i++)
			for(int j=y-1;j<=y+1;j++)
			{
    
				auto [res,col] = equal(i,j);
				if(res)
				{
    
					q.push({
    i,j,col});
					paint(i,j,-1);
					path.push_back({
    i,j,col});
				}
			}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]!=-1)
			{
    
				cout<<-1<<'\n';
				return ;
			}
	reverse(path.begin(),path.end());
	cout<<path.size()<<'\n';
	for(auto [x,y,col] : path)
		cout<<x<<" "<<y<<" "<<col<<'\n';
}
signed main()
{
    
   int T;
   T=1;
   while(T--)solve();
}