Pinely Round 2 (Div. 1 + Div. 2)(A-D)

qbning / 2023-08-31 / 原文

Dashboard - Pinely Round 2 (Div. 1 + Div. 2) - Codeforces

A.题意是一共有n个用户，当前有a个用户在线，然后有m个用户上/下线通知，问是否有一时刻所有用户都在线。

简单的模拟，按照+-统计最大的和n的关系，和上线用户数量的关系判断下就行。

当时代码有点小乱。

查看代码


#pragma GCC optimize(2)
#include<iostream>
using namespace std;
typedef long long ll;
void solve()
{
	int n,q,m;
	cin>>n>>q>>m;
	int add=0,sub=0,tmp=q,suc=q;
	for(int i=0;i<m;i++)
	{
		char c;
		cin>>c;
		if(c=='+')add++,tmp++;
		else sub++,tmp--;
		suc=max(suc,tmp);
	}
	if(suc==n)
	{
		cout<<"YES\n";
		return;
	}
	if(suc<n&&q+add<n)
	{
		cout<<"NO\n";
	}
	else cout<<"MAYBE\n";
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

B。题意是给你一个(1-n)的某个排列，每次可以选择一个数，让小于它的数按照原来的相对位置排到它前面，大于它的按照原来的相对位置排在它后面，然后问最少多少次操作把序列变成1-n

最坏可能是n-1次(毕竟最后一个不用动嘛)。

我们想一种情况，如果x+1在x后面的话，我们动x+1的时候就把x,x+1有序化了，相当于少操作一次。

我们存一下每个数的下标，判断下它加1在不在后面即可

然后

查看代码

 #pragma GCC optimize(2)
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll a[100005],b[100005],n;
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[a[i]]=i;
	}
	int ans=n-1;
	for(int i=1;i<n;i++)
		if(b[a[i]+1]>b[a[i]]&&a[i]<n)ans--;
	cout<<ans<<"\n";
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

C.给一个大小为n的数组，里面是0-n缺了一个数。然后每次操作都把a[i]换成mex{a1....an}，问k次操作后数组变成什么样。

既然是0-n这n+1个数缺少的那个数，那么每次操作都会让第一个数变成缺的数，然后第二个等于原来的第一个，第三个等于原来的第二个。。。。直到最后一个变成原来的倒数第二个。

那么再执行n-1次，缺的那个数到了最后一位，再执行一次，发现回到了原来的数组。即n+1次循环。

我们先将k%(n+1)，统计下缺的数和剩下的k，那么n-k+1这一位的数会在k轮操作后消失，它后面的加上此时缺的数再加上它前面的构成k轮后的数列。

查看代码

 #pragma GCC optimize(2)
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
int a[100005],b[100005],n,k;
void solve()
{
	cin>>n>>k;
	for(int i=0;i<=n;i++)b[i]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[a[i]]=1;
	}
	k%=(n+1);
	if(k==0)
	{
		for(int i=1;i<=n;i++)
		cout<<a[i]<<' ';
		cout<<"\n";
		return;
	}
	int mex=0;
	for(int i=0;i<=n;i++)
	{
		if(b[i]==0)
		{
			mex=i;
			break;
		}
	}
	int ft=n-k+1;
	vector<int>ans;
	for(int i=ft+1;i<=n;i++)
	{
		ans.push_back(a[i]);
	}
	ans.push_back(mex);
	for(int i=1;i<ft;i++)ans.push_back(a[i]);
	for(auto x:ans)
	cout<<x<<' ';
	cout<<"\n";
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

D.题意是给一个n*m的格子，然后有两种特殊的占两块的格子，横着的LR,竖着的U,D，现在要求在两块的格子上涂黑白两种颜色，同一块L,R颜色相异，同一块U,D颜色相异，问是否能让每一行每一列的两种颜色格子相等。

L,R横着放，对于一行的黑白两色的个数平衡不会影响，那么我们来找U,D的数目，如果这一行U,D的数目为奇数，那么肯定不行。如果为偶数，那么

。。。太困了，明天再补，先把代码放这吧。

查看代码

#pragma GCC optimize(2)
#include<iostream>
using namespace std;
typedef long long ll;
char mp[505][505];
int f[505][505],g[505][505];
void solve()
{
	int n,m,fail=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(int j=1;j<=m;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]=='U'||mp[i][j]=='D')cnt++;
			f[i][j]=0;
			g[i][j]=0;
		}
		if(cnt%2)
			fail=1;
	}
	for(int i=1;i<=m;i++)
	{
		int cnt=0;
		for(int j=1;j<=n;j++)
			if(mp[j][i]=='L'||mp[j][i]=='R')cnt++;
		if(cnt%2)
			fail=1;
	}
	if(fail)
	{
		cout<<-1<<"\n";
		return;
	}
	for(int i=1;i<=n;i++)
	{
		int la=0;
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]=='U')
			{
				if(f[i][f[i][j]]==j)continue;
				if(la)
				{
					f[i][j]=la;
					f[i][la]=j;
					f[i+1][j]=la;
					f[i+1][la]=j;
					la=0;
				}
				else la=j;
			}
		}
		if(la)
		{
			cout<<-1<<'\n';
			return;
		}
	}
	for(int i=1;i<=m;i++)
	{
		int la=0;
		for(int j=1;j<=n;j++)
		{
			if(mp[j][i]=='L')
			{
				if(g[g[j][i]][i]==j)continue;
				if(la)
				{
					g[j][i]=la;
					g[la][i]=j;
					g[j][i+1]=la;
					g[la][i+1]=la;
					la=0;
				}
				else la=j;
			}
		}
		if(la)
		{
			cout<<-1<<'\n';
			return;
		}
	}
	char ans[505][505];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]=='.')
			{
				ans[i][j]='.';
			}
			else if(mp[i][j]=='L')
			{
				ans[i][j]='W';
				ans[g[i][j]][j]='B';
			}
			else if(mp[i][j]=='U')
			{
				ans[i][j]='W';
				ans[i][f[i][j]]='B';
			}
			else if(mp[i][j]=='R')
			{
				ans[g[i][j]][j]=ans[i][j-1];
				if(ans[i][j-1]=='W')
					ans[i][j]='B';
				else
					ans[i][j]='W';
			}
			else if(mp[i][j]=='D')
			{
				ans[i][f[i][j]]=ans[i-1][j];
				if(ans[i-1][j]=='B')
					ans[i][j]='W';
				else ans[i][j]='B';
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<ans[i][j];
		cout<<'\n';
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}