526互联

Pinely Round 2 (Div. 1 + Div. 2)

发布时间 2023-08-31 18:50:17作者: du463

Pinely Round 2 (Div. 1 + Div. 2)

比赛链接
因为第二天早上满课，所以这个比赛没有打，但是补题还是要有的。

A题Channel

A题链接
你是一个博主，有n个订阅者，当你发表了一篇博客时，会被订阅者看到，一开始有a名订阅者在线，随后给你q个指令，“+”代表有一个订阅者上线，“-”代表有一个订阅者下线，你想知道是否全部订阅者都阅读过你的文章，YES表示肯定，MAYBE表示也许，NO表示没有，

A思路：

一开始这个题会错意了，以为减号代表的有可能不是他的订阅者下线，但应该是都是订阅者的信息，接下来就是这个题的思路：如果是YES，那一定是有一段全部是+号，表示有这么一段序列全是加号，并且长度大于n个订阅者。如果是NO呢，就是即使我们下线的全是之前在线的，一开始在线的订阅者加上+号的数量还要小于n，这表明绝不可能出现全部查看的情况，其他情况均是MAYBE。

A代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
	int n,a,q;
	cin>>n>>a>>q;
	int m=a;
	int maxn=a;
	int ans=0;

	for(int i=1;i<=q;i++){
		char b;
		cin>>b;
		if(b=='+'){
			m++;
			maxn=max(maxn,m);
			ans++;

		}
		else{
			m--;

		}
	}
	if(maxn>=n){
		cout<<"YES"<<endl;
	}
	else{
		if(a+ans>=n){
			cout<<"MAYBE"<<endl;
		}
		else{
			cout<<"NO"<<endl;
			
		}
	}
}
int main(){
	int t;
	cin>>t;
	// cout<<t<<endl;
	while(t--){
		solve();
	}
	return 0;
}

B. Split Sort

题目链接
给定一个序列a，你可以进行操作：选择一个数 x ，将所有 比 x 小的数按照序列中的顺序放到 x 前面 ， 将所有大于等于 x 的数 按照序列中的顺序放到 x 后面。求整个序列满足单增的最小操作数。

B思路：

一开始我以为只需要找到一个位置他的前一个数比当前数的位置大，那这个点就是需要交换的，但这样想是错的，倒不是思路错，只是无法满足是最小操作数，看样例发现，当我们改变一个数的位置的时候，有些数的位置也会改变，事实上这个题的操作于逆序对有关，操作数为整个序列中 i 和 i + 1 位置的逆序对数量。

B代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
bool cmp(PII a,PII b){
	return a.first<b.first;

}

void solve(){
	int n;
	cin>>n;
	int ans1=0;

	std::vector<PII> v(n+1);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;

		v[i].first=x;
		v[i].second=i;
		if(x<v[i-1].first){
			ans1++;

		}
	}
	sort(v.begin(),v.end(),cmp);
	int ans=0;
	if(n==1){
		cout<<0<<endl;
	}
	else{
		for(int i=2;i<=n;i++){
			if(v[i].second<v[i-1].second){
				ans++;
			}
		}
		cout<<ans<<" "<<ans1<<endl;
		
	}
}
int main(){
	int t;
	cin>>t;
	// cout<<t<<endl;
	while(t--){
		solve();
	}
	return 0;
}

C. MEX Repetition

题目链接
给定一个长度为n，大小在[0,n]的没有相同元素的序列，总共进行k轮操作，每轮操作将按照顺序从i=1~n，使得ai=MEX(a1,a2,a3,...)。其中MEX函数代表了所有数当中没有出现的最小非负整数。例如：MEX(1,1,2)=0,MEX(0,1,2)=3。求k轮操作后序列变成了什么样子，

C思路：

一开始我竟然没有读懂这个题是在说什么，果然中午没睡觉太困啦影响脑子转动，睡醒一觉醒来发现这个题还是比较简单的，但是如果只是简单的模拟的话其实是会超时的，我们不妨将这n+1个数字按照他规定的方式进行展开，这样说可能不太明显，画个图就比较易懂了。
image

C代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
bool cmp(PII a,PII b){
	return a.first<b.first;

}

void solve(){
	int n,k;
	cin>>n>>k;
	std::vector<int> v;
	std::map<int, int> mp;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		mp[x]=1;
		v.push_back(x);

	}
	for(int i=0;i<=n;i++){
		if(mp[i]!=1){
			v.push_back(i);

		}
	}
	//y因为是0-n有n+1个数字
	n+=1;
	int t=k%n;//看看是取到了哪个位置
	int st=n-t;
	for(int i=1;i<n;i++){
		cout<<v[st%n]<<" ";
		st++;

	}
	cout<<endl;

}
int main(){
	int t;
	cin>>t;
	// cout<<t<<endl;
	while(t--){
		solve();
	}
	return 0;
}

D. Two-Colored Dominoes

原题链接
有一个n * m 的网格。其中有若干个1 * 2的多米诺骨牌横着放或者竖着放在其中，你需要将其一格涂成黑色，一格涂成白色。需要满足一行当中白色的格子等于黑色的格子，一列当中白色的格子等于黑色的格子。问能否涂成每行和每列黑白颜色数目相等的样子，可以输出画法，不可以输出-1；

D思路：

这个题也并不是很难，你想如果横着放是不是影响到的就是两列，竖着放影响到的就是两行，基于这个的基础上，我们可以对这些按照一黑一白和一白一黑插着放，这样就保证了颜色相等，所以我们只需要统计一下对应行列中横竖放着的个数就可以。

D代码：

#include<bits/stdc++.h>
using namespace std;
const int N=510;
typedef long long ll;
typedef pair<int,int> PII;
bool cmp(PII a,PII b){
	return a.first<b.first;

}
char a[N][N];

void solve() 
{
	int n , m;
	cin>>n>>m;
	vector<int>row[m] , column[n];
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < m  ; j ++){
			cin>>a[i][j];
			if(a[i][j] == 'L'){
				row[j].push_back(i);
			}
			if(a[i][j] == 'U'){
				column[i].push_back(j);
			}
		}
	}
	for(int i = 0; i < m ; i++){
		if(row[i].size() % 2 == 1){
			cout<<"-1\n";
			return;
		}
		else{
			int t = row[i].size();
			int flag = 1;
			for(int j = 0 ; j < t ; j ++){
				int r = row[i][j];
				if(flag == 1){
					a[r][i] = 'W';
					a[r][i + 1] = 'B';
					flag *= -1;
				}
				else{
					a[r][i] = 'B';
					a[r][i + 1] = 'W';
					flag *= -1;
				}
			}
		}
	}
	for(int i = 0 ; i < n ; i ++){
		if(column[i].size() % 2 == 1){
			cout<<"-1\n";
			return;
		}
		else{
			int t = column[i].size();
			int flag = 1;
			for(int j = 0 ; j < t ; j ++){
				int c = column[i][j];
				if(flag == 1){
					a[i][c] = 'W';
					a[i + 1][c] = 'B';
					flag*=-1;
				}
				else{
					a[i][c] = 'B';
					a[i + 1][c] = 'W';
					flag*= -1;
				}
			}
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 0;  j < m ; j ++){
			cout<<a[i][j];
		}
		cout<<endl;
	}
}     
int main(){
	int t;
	cin>>t;
	// cout<<t<<endl;
	while(t--){
		solve();
	}
	return 0;
}