A
当一个"_ "的右边没有“^”时，答案增加，发现这对于中间的序列是充分必要的。
当位置 \(1\) 为 "_"时，我们必须在其前面加一个"^"；当整个字符串为 "^"时，特判一下答案。
B
发现给定01串当全是“1”时，我们直接输出 \(n*n\)。考虑一般的情况，我们发现将面积表示出来
\(S=a+b,a+b=x\)，\(x\)为定值，即连续的“1”的最大个数。那么我们就由均值不等式可知当 \(a=b\)时，面积最大。
考虑实际，当 \(x=2*k+1\)，即为奇数时，不能使 \(a=b\)，那么我们让 \(a=b-1\)，此时面积最大。
由于题目的性质，我们需要将首尾连成圈来确定这个 \(x\) 的值。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int T, n;
char s[N << 1];
int main(){
cin >> T;
while(T --){
cin >> (s + 1);
n = strlen(s + 1);
bool flag = true;
LL ans = 0;
int maxn = 0, cnt = 0;
for(int i = 1; i <= n; i++)
if(s[i] == '0')
flag = false, maxn = max(maxn, cnt), cnt = 0;
else cnt ++;
for(int i = 1; i <= n; i++)
if(s[i] == '0')
flag = false, maxn = max(maxn, cnt), cnt = 0;
else cnt ++;
maxn = max(cnt, maxn);
if(flag) ans = (LL)n * n;
else {
if(maxn % 2 == 0) ans = (LL)maxn / 2 * (LL)(maxn / 2 + 1);
else ans = (LL) (maxn + 1) / 2 * (maxn + 1) / 2;
}
cout << ans << endl;
}
return 0;
}
C
首先，我们考虑这样一个问题：若使得这个改变后的序列的 \(mex\) 值比原来大 \(1\) ,需要满足什么条件。
我们进行一次操作后，设原来的 \(mex\) 值为 \(M\) 不难发现：
- 1 要让新序列有 \(1~M\) 的至少一个元素。
- 2 要使新序列中不含有 \(M+1\) 的元素，否则新的 \(mex\) 值不可能为 \(M+1\)。
那么我们同时明确了这次操作的目的，我们采取这样的方式来模拟操作。
由于第二点的必要性且我们只有一次操作，我们将序列中的所有 \(M+1\) 给赋值为 \(M\) ，若新序列不符合要求，那一定无解。
对于剩下的情况，我们还需要特判一下该序列是不是一个 \(1~M-1\) 的排列（这也是不合法的）。
其他情况均合法，且此方案可行。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, n, a[N], A[N];
int main(){
cin >> T;
while(T --){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]), A[i] = a[i];
sort(A + 1, A + n + 1);
int cnt = 0;
bool flag = true;
for(int i = 1; i <= n; i++)
if(A[i] == cnt) cnt ++;
else flag = false;
if(flag){
puts("NO");
continue;
}
int l = 0, r = n + 1;
for(int i = 1; i <= n; i++)
if(a[i] == cnt + 1){
l = i;
break;
}
for(int i = n; i; i--)
if(a[i] == cnt + 1){
r = i;
break;
}
for(int i = l; i <= r; i++)
a[i] = cnt;
sort(a + 1, a + n + 1);
int cntt = 0;
for(int i = 1; i <= n; i++)
if(a[i] == cntt) cntt ++;
if(cnt == cntt - 1 || l == 0) puts("YES");
else puts("NO");
}
return 0;
}