前言
读题仔细再仔细。
第一题
题目： Beautiful String
题意：
给我们一个字符串，字符串由 ‘a’,‘b’,‘c’,‘?’ 四种字符组成，我们可以将 ‘?’ 改成另外三种字符之一，问是否可以通过修改字符串使得整个字符串没有任意的两个相同的相邻字符。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
接下来第二行到第n+1行是n个样例，每个样例是一个字符串。
输出格式
如果可以，输出修改后的字符串；否则输出 -1 。
数据范围
1 ≤ t ≤ 1000
所有字符串长度总和不会大于105。
输入样例：
3
a???cb
a??bbc
a?b?c输出样例：
ababcb
-1
acbac思路：
- 我们可以遍历一次字符串，因为每个问号可以修改为另外三种之一，所以我们只要保证，当前所修改的字符与其两边的字符不同即可。
- 最后不要忘记判断一次是否符合条件。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3 + 10;
#define LL long long
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == '?')
{
int j = i;
for (; s[j] == '?'; j++)
{
s[j] = 'a';
//判断两次，防止在遇到b?a这种情况时出错
if (s[j] == s[j - 1] || s[j] == s[j + 1])s[j]++;
if (s[j] == s[j - 1] || s[j] == s[j + 1])s[j]++;
}
i = j;
}
}
int res = 0;
//判断是否符合条件
for (int i = 1; i < s.size(); ++i)
if (s[i] == s[i - 1])res = 1;
res ? cout << -1 << endl: cout << s << endl;
}
return 0;
}第二题
题目：Beautiful Numbers
题意：
给我们一个长度为n的数列，如果我们能找到一个长度为m的区间，这个区间中的序列由 1 ~ m 这m个数组成，那么m就是美丽数。求解 1~n 中有多少美丽数。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例共有两行，第一行是一个整数n。
每个样例第二行是n个整数。
输出格式
每个样例占一行，对于每个数，如果是美丽数用1表示，不是用0表示。不需要空格隔开。
数据范围
1 ≤ t ≤ 1000
1 ≤ n ≤ 2 × 105
对于每个样例，一定是由n个1~n的不同的数组成的。
所有样例的n总和不超过2 × 105。
输入样例：
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2输出样例：
101011
11111
1001思路：
- 乍一看会觉得这个题很麻烦，但是因为n的范围很大，所以不会是暴力。
- 直接考虑什么时候是美丽数不太好判断。考虑什么时候不是美丽数？我们会发现，如果一个长度为m的数，区间的长度如果是大于m的，那么一定不是美丽数（区间是指1到m所有数中最靠后的数的位置减去最靠前的数的位置）。
- 怎么判断一个长度为m的区间是美丽数？如果直接暴力判断会超时，考虑用前缀和。只要这m个数的和是1~m的和，那么一定是美丽数。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 2e5 + 10;
#define LL long long
LL a[N],b[N];
LL c[N];
LL s[N];
int main()
{
LL t;
cin >> t;
while (t--)
{
LL n;
cin >> n;
LL f=0;
for (LL i = 1; i <= n; ++i)
{
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];
c[a[i]] = i;
}
//1和n一定是美丽数
b[1] = b[n] = 1;
LL l = c[1], r = c[1];//l表示长度为i的区间中最小位置
for (LL i = 2; i < n; ++i)
{
if (l > c[i])l = c[i];
if (r < c[i])r = c[i];
if ((l - r) > i)
{
b[i] = 0;
continue;
}
if ((s[r] - s[l - 1]) == (1 + i) * i / 2)b[i] = 1;
else b[i] = 0;
}
for (LL i = 1; i <= n; ++i)printf("%lld",b[i]);
printf("\n");
}
return 0;
}第三题
题目： Beautiful Regional Contest
题意：
已知有n个人各自的做题数，根据他们的做题数给他们颁奖。有金银铜三种奖牌，要求奖牌总和不超过总人数的一半，向下取整。金牌的数量必须最少。在要求范围内尽量多颁奖。金牌做题要比银牌多，银牌要比铜牌多。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例有两行，第一行是一个整数n，表示有n个人。
第二行是n个整数p1，p2，…，pn，表示每个人的做题数。
每个样例在一行上输出三个整数，用空格隔开，依次表示金银铜牌的数量。
数据范围
1 ≤ t ≤ 10000
1 ≤ n ≤ 4×105
0 ≤ pi ≤ 106
所有样例的总人数不会超过4×105。
输入样例：
5
12
5 4 4 3 2 2 1 1 1 1 1 1
4
4 3 2 1
1
1000000
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
32
64 64 63 58 58 58 58 58 37 37 37 37 34 34 28 28 28 28 28 28 24 24 19 17 17 17 17 16 16 16 16 11输出样例：
1 2 3
0 0 0
0 0 0
2 5 3
2 6 6思路：
- 首先我们看三种奖牌的要求：
- 三种奖牌总和不超过总人数的一半，向下取整。
- 金牌的数量必须是最少的。银牌可以比铜牌多。
- 金牌，银牌，铜牌的做题数必须是严格减少的。
- 在可能范围内，尽量多颁奖。
- 因为尽量多颁奖且颁奖人数不超过总人数一半，所以我们可以遍历前n/2个人。因为三种奖牌的做题数必须严格递减，我们可以记录前n/2个人有多少不同的解题数。
- 只要前n/2个人的不同解题数大于3，就说明有解，同时金牌的最少人数是解题最多的人数。最后判断一下银牌和铜牌的数量即可。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 4e5 + 10;
#define LL long long
int a[N];
int b[N];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
int cnt = 0, k = n / 2;
//因为最多只给前一半的人颁奖，所以只需要遍历到n/2即可
for (int i = 1; i <= k; ++i)
{
if (a[i] != a[i + 1])
{
cnt++;
b[cnt] = i;
}
}
//x,y,z分别是金牌，银牌，铜牌的人数。金牌至少要有b[1]个人。
int x = b[1], y = 0, z = 0;
int i;
for (i = 2; i <= cnt; ++i)
{
y += b[i] - b[i - 1];
if (y > x)break;
}
z = b[cnt] - b[i];
if (x && x < y && x < z) cout << x << " " << y << " " << z << endl;
else cout << "0 0 0" << endl;
}
return 0;
}
