B. Array Sharpening

 

题意：给定一个非负数列，每次操作选一个正数-1，问任意次操作后能否变成一个单峰凸函数。

若有奇数个，从两端开始从零递增，判断每个数初始大于终值。

若有偶数个，判断完还要判断中间两个能否大于个数除2，否则没法出现峰值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int T;
int n;
int a[maxn];
int main() {
	cin >> T;
	while (T--) {
		cin >> n;
		bool flg = 1;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			if (a[i] == 0 && i != 1 && i != n)flg = 0;
		}
		if (!flg) {
			puts("No");
			continue;
		}
		for (int i = 1; i <= n; i++) {
			if (a[i] < min(n - i, i - 1)) {
				flg = 0; break;
			}
		}
		if (!flg) {
			puts("No");
			continue;
		}
		if (n & 1)puts("Yes");
		else {
			if (a[n / 2] >= n / 2 || a[n / 2 + 1] >= n / 2)puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

 

C. Mind Control

 

题意：n个人排队，你排在第m个，可以控制k个人，从前往后每个人选择拿走数值序列中第一个或最后一个，问你最大拿到多少。

似乎读错题了，但方法一样，枚举没法控制的人，再第二层循环枚举能控制得人，取最大值的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int N = 1E5 + 7;
int arr[N];
void solve()
{

	int n, m, k;
	cin >> n >> m >> k;
	k = min(k, m - 1);
	for (int i = 1; i <= n; i++) cin >> arr[i];
	int sum = 0;
	for (int i = 0; i <= k; i++) {
		int ans = INF;
		for (int j = i + 1; j <= m - k + i; j++)
		{
			ans = min(ans, max(arr[j], arr[j + n - m]));
		}
		sum = max(sum, ans);
	}
	cout << sum << endl;
}
int main() {
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}

 

D. Irreducible Anagrams

 

题意：定义两个重排后能相等得序列为相似序列，若两个相似序列存在大于2的整数k，分成k分，每一份都是相似序列，则它们是完全相似序列。给定一个字符串s，多次询问，每次问一个子串是否存在不完全相似序列。

构造

有三种情况存在不完全相似序列。

  1. 只有一个字符，自己和自己相似，且只有完全相似。
  2. 首尾字符不同。把所有和最后一个字符相同的字符都放到最前面，其他字符在后面随便排。构造完后若第一条分割线从全都与最后一个字符相同的部分分割，则前部分原串包含首字符，与尾字符不同，所以两者一定不同。若从后部分分割，则原串分割后的后半部分包含尾字符，而新串不含，所以也一定不等。
  3. 首尾字符相同，但有至少三种不同字符。同样要保证首尾不同，所以先把最后面不等于首尾字符的字符放到前面，然后放首尾字符，其他的随便排（每一步还是把相同的都放一起）。证明和第二种类似，讨论第一条分割线的位置，无论在哪里都不会有前缀相似的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
char s[maxn];
int q, l, r;
int sum[maxn][30];
int main() {
	scanf("%s", s + 1);
	for (int i = 1; s[i]; i++) {
		for (int j = 0; j < 26; j++)sum[i][j] = sum[i - 1][j];
		sum[i][s[i] - 'a']++;
	}
	cin >> q;
	while (q--) {
		scanf("%d%d", &l, &r);
		if (l == r)puts("Yes");
		else if (s[l] != s[r])puts("Yes");
		else {
			int cnt = 0;
			for (int i = 0; i < 26; i++) {
				if (sum[r][i] - sum[l - 1][i] > 0)cnt++;
			}
			puts(cnt >= 3 ? "Yes" : "No");
		}
	}
	return 0;
}