A. Diverse Substring
找普遍性（特殊解即可）。
最简单的便是存在一个区间([i, i + 1] (1 <= i < n))，且$str[i] $ $ != str[i + 1]$，就满足题意了。
对于其他的有可能满足的序列，必须存在：
这个字母的出现次数 $ <= $ 除这个字母之外的出现次数总和。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;
int n;
char str[N];
int main(){
cin >> n >> (str + 1);
for(int i = 1; i < n; i++){
if(str[i] != str[i + 1]){
printf("YES
%c%c
", str[i], str[i + 1]);
return 0;
}
}
puts("NO");
return 0;
}
B. Vasya and Books
设 (dep) 为已知取出的层数，初始化为(0)，(cnt[i])代表i数字出现的位置
每次处理一个数字(x)：
1、若$cnt[x] <= dep $，意味着这个数已经被清理了，直接输出(0)即可
2、否则，则将(x - dep)的数全部清理。
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 200010;
int n, a[N];
int main(){
scanf("%d", &n);
for(int i = 1, x; i <= n; i++)
scanf("%d", &x), a[x] = i;
int dep = 0;
for(int i = 1; i <= n; i++){
int x; scanf("%d", &x);
if(a[x] <= dep) printf("0 ");
else printf("%d ", a[x] - dep), dep = a[x];
}
return 0;
}
C. Vasya and Robot
显然，如果修改长度为(len)可以成功，那么修改长度$ > len$的也都可以成功。
（可以让修改的那部分不变，剩下的照搬）
满足单调性，既可二分。
可以处理前缀和，来预处理除了([l ,l + len - 1])区间外另外的部分走到的部分。
因为符合交换律（先走$[1, l - 1] 与 [l + len, n] (的路径，再走)[l ,l + len - 1]$ 结果不变），所以一次前缀和即可完成任务。
(check())函数的书写需要注意，不单单需要曼哈顿距离（即从$(nx, ny) -> (tx, ty) (的最短路径 ）) >= len$，而且哈密尔路径的奇偶性必须和曼哈顿距离一样，否则无论怎样都到不了。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 200010;
int n, tx, ty, x[N], y[N];
char str[N];
bool inline check(int len){
for(int l = 1, r = len; r <= n; l++, r++){
int nx = x[n] - (x[r] - x[l - 1]);
int ny = y[n] - (y[r] - y[l - 1]);
int dist = abs(tx - nx) + abs(ty - ny);
if(len >= dist && (dist & 1) == (len & 1)) return true;
}
return false;
}
int main(){
scanf("%d%s%d%d", &n, str + 1, &tx, &ty);
for(int i = 1; i <= n; i++){
x[i] = x[i - 1], y[i] = y[i - 1];
if(str[i] == 'U') y[i]++;
else if(str[i] == 'D') y[i]--;
else if(str[i] == 'L') x[i]--;
else if(str[i] == 'R') x[i]++;
}
if(!check(n)) puts("-1");
else{
int l = 0, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d", r);
}
return 0;
}
D. Berland Fair
可以预处理每次(m)对应的买的糖果，对其取模，因为这几次的行为是相同的，可以加快速度。
存在两数(a)、(b)且吗满足(a >= b)，则一定满足$a % b <= a / 2 $。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, a[N], cnt;
LL T, s = 2, ans = 0;
int main(){
cin >> n >> T;
for(int i = 1; i <= n; i++) scanf("%d", a + i);
while(s){
s = cnt = 0;
for(int i = 1; i <= n; i++)
if(s + a[i] <= T) s += a[i], cnt++;
ans += (T / s) * cnt;
T %= s;
}
return 0;
}