Codeforces Round #604 (Div. 2) 练习A,B题解

A题

思路分析：

因为只需要做到相邻的不相同，利用三个不同的字母是肯定可以实现的，

所以直接先将所有的问号进行替换，比如比前一个大1,如果与后面的冲突，则再加一
代码(写的很烂)：

#include <bits/stdc++.h>

using namespace std;

int check( string a)

{

	for (int i = 0; i < a.length(); ++i)

	{

		if (i==0)

		{

			if (a[i]==a[i+1])

			{

				return 0;

			}

		}

		else if (a[i]==a[i-1])

		{

			return 0;

		}

		else{

			if (a[i-1]==a[i]||a[i+1]==a[i])

			{

				return 0;

			}

		}

	}

	return 1;

}

int main(int argc, char const *argv[])

{

	int t;

	cin>>t;

	string a;

	while(t--)

		{

			cin>>a;

			for (int i = 0; i < a.length(); ++i)

			{

				if (i==0)

				{

					if (a[i]=='?')

					{

						a[i]=((a[i+1]+1)%97)%3 + 97;

						if (a[i]==a[i+1])

						{

							a[i] = ((a[i]+1)%97)%3+97;

						}

					}

				}

				else if (i==a.length()-1 )

				{

					if (a[i]=='?')

					{

						a[i]=((a[i-1]+1)%97)%3 + 97;

					}

				}

				else

				{

					if (a[i]=='?')

					{

						a[i]=((a[i-1]+1)%97)%3 +97;

						if (a[i] == a[i+1])

						{

							a[i]=((a[i]+1)%97)%3 +97;

						}

					}

			}

		}

		if (check(a))

		{

			cout<<a<<endl;

		}

		else

			cout<<"-1"<<endl;

	}

	return 0;

}

B题

链接

思路分析：

如果有1到m的一个排列，那么肯定1到m的所有的数的位置最大值减去最小值的差是m-1

所以可以利用一个数组将pos信息存起来，从小到大遍历就可以
代码：

#include <bits/stdc++.h>

using namespace std;

int  pos[200001];

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	int t;

	int n;

	cin>>t;

	int k;

	while(t--)

	{

		cin>>n;

		for (int i = 0; i < n; ++i)

		{

			cin>>k;

			pos[k-1] = i;

		}

		int maxpos = 0;

		int minpos = n-1;

		for (int i = 0; i < n; ++i)

		{

			minpos = min(minpos, pos[i]);

			maxpos = max(maxpos, pos[i]);

			cout<<(maxpos-minpos==i?1:0);

		}

		cout<<endl;

	}

	return 0;

}

巴特西

Codeforces Round #604 (Div. 2) 练习A,B题解

A题

B题

最新文章

热门文章