SDTBU-ACM集训队暑期集训---个人赛 9

前言

做题的时候不要死磕一种思路，如果当前思路交不上去可以考虑换一种想法。改错有时比想新的解法更难。

第一题

题目： Problem - 1632A - Codeforces

题意：

给我们一个由0和1构成的字符串，问是否可以通过调整字符串的组成方式，使得整个串中没有长度大于1的回文子串。

输入格式

输入包含多个样例，第一行是一个整数t，表示有t个样例。

每个样例第一行是一个整数，表示字符串的长度。

每个样例第二行是一个字符串。

输出格式

输出 YES 或 NO 。

数据范围

1 ≤ t ≤ 100

1 ≤ n ≤ 100

输入样例：

4
1
1
2
10
2
01
4
1010

输出样例：

YES
YES
YES
NO

思路：

• 思维题。直接判断当前字符串的长度，如果长度为2，那么只有当两个字符相同时才会有大于1的回文串。
• 如果长度大于2，因为字符串只会由0和1构成，那么一定会有大于1的回文串。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_map>

using namespace std;

#define ll long long

ll gcd(ll a, ll b)
{
	if (a == 0)return b;
	return gcd(b % a, a);
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		if (n > 2)cout << "NO" << endl;
		else if (s[0] == s[1])
		{
			cout << "NO" << endl;
		}
		else cout << "YES" << endl;
	}
	return 0;
}

第二题

题目： Problem - 1632B - Codeforces

题意：

给我们 0~n-1 共n个数字，可以任意组合它们位置，在排好位置后会将相邻的两个数字进行或操作，给出或操作后所有数字中最大值最小的排列方式。

输入格式

输入包含多个样例，第一行是一个整数t，代表有t个样例。

每个样例是一个整数n，表示有 0~n-1 共n个数。

输出格式

对于每个样例，输出一个由 0~n-1 组成的序列。

数据范围

1 ≤ t ≤ 10⁴

2 ≤ n ≤ 2×10⁵

保证所有的n之和不会大于2×10⁵

输入样例：

4
2
3
5
10

输出样例：

0 1
2 0 1
3 2 1 0 4
4 6 3 2 0 8 9 1 7 5

思路：

• 我们会发现 0~n-1 这n个数中，有一个数字除了和0进行或操作外，无论和谁进行或操作都会变大，这个数字就是二进制只有1个1且在最高位的数字。显然无论怎么组合，都不能将其变的更小。
• 那么我们可以先将这个数字求出来和0配对，然后只要剩下的数字在进行或操作时不会变大就可以了。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_map>

using namespace std;

#define ll long long

ll gcd(ll a, ll b)
{
	if (a == 0)return b;
	return gcd(b % a, a);
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		
		int k = 1;
		while (k < n)k *= 2;
		k /= 2;
		for (int i = 1; i < k; ++i)cout << i << " ";
		cout << 0 << " " << k << " "; 
		for (int i = k + 1; i < n; ++i)cout << i << " ";
		cout << endl;

	}
	return 0;
}

第三题-赛后补题

题目： Problem - 1632C - Codeforces

题意:

给我们两个整数a和b，每次可以选择三种操作之一进行操作：

1. 将a的值加1。
2. 将b的值加1。
3. 将a的值替换为a|b。

问最少几次操作可以使得a==b。

输入格式

输入包含多个样例，第一行是一个整数t，表示有t个样例。

每个样例包含两个整数a和b。

输出格式

输出一个整数，表示最少操作次数。

数据范围

1 ≤ t ≤ 10⁴

1 ≤ a < b ≤ 10⁶

保证b的所有总和不超过10⁶。

输入样例：

5
1 3
5 8
2 5
3 19
56678 164422

输出样例：

1
3
2
1
23329

思路：

• 因为b的总和不会超过10⁶，所以可以直接暴力(比赛的时候我人傻了，没看到b的范围，一直在考虑怎么优化时间)。
• 如果a和b直接或操作后结果为b，那么操作次数为1。
• 否则可以从a开始遍历，不断让a+1，直到a和b或操作后结果为b。
• 如果a和b或操作完结果大于b，那么我们就可以从b开始遍历，不断让b+1，直到b和a或操作后结果为b。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_map>
#include<cmath>

using namespace std;

#define ll long long

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int a, b;
		cin >> a >> b;
		
		if ((a | b) == b)
		{
			cout << 1 << endl;
			continue;
		}

		int res = b - a;

		for (int i = a; i < b; ++i)
			if ((i | b) == b)res =min(res, i - a + 1);//此时i代表a
		for (int i = b; i <= (a | b); ++i)//先让a=a|b
			if ((i | a) == i)res = min(res, i - b + 1);//此时改变b，i代表b
		cout << res<<endl;
	}
	return 0;
}