A. Stickers and Toys
考虑尽量先买(max(s, t))个里面单独的。那么如果(s + t > n)那么(s + t - n)的部分就该把(min(s, t))踢出来，这些多的只能合并到另外一个上面去，所以答案就是：$ max(s, t) - (s + t - n) + 1$。
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int n, s, t;
int main(){
int T; scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &s, &t);
printf("%d
", max(s, t) - (s + t - n) + 1);
}
return 0;
}
B. Letters Shop
二分答案。答案符合区间包括性（单调性），若([1, x])可行，那么([1, y] (x <= y <= n))必然也可行。
预处理前缀和，(check())的时间复杂度可以降到(O(26))，那么总共程序的时间复杂度为(O(mlogn))。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200010, M = 50010;
char s[N], t[N];
int n, m, sum[N][26], g[26], len;
//[1, x]这段可不可行
bool inline check(int x){
for(int i = 0; i < 26; i++)
if(sum[x][i] < g[i]) return false;
return true;
}
int main(){
scanf("%d%s%d", &n, s + 1, &m);
for(int i = 1; i <= n; i++){
for(int j = 0; j < 26; j++) sum[i][j] = sum[i - 1][j];
sum[i][s[i] - 'a']++;
}
for(int i = 1; i <= m; i++) {
for(int j = 0; j < 26; j++) g[j] = 0;
scanf("%s", t + 1);
len = strlen(t + 1);
for(int i = 1; i <= len; i++) g[t[i] - 'a']++;
int l = 1, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d
", r);
}
return 0;
}
C. Vasya And Array
由于发现在线做法需要分类讨论，懒癌晚期就把信息进行了排序(qwq)。
不难发现，(NO)的情况就是(0)的信息属于(1)的子序列。但是如果直接处理，就有多种冲突可能，(check)就需要分类讨论了。先处理(1)的数据，再处理(0)的数据，就只需要检查(0)是不是子区间就可以了。
关于方案，设(f[i])为(i)和(i + 1)的关系（不变还是递减），这样只需要顺次维护即可。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = 1010;
int n, m, f[N];
//f[i] 表示 i 和 i + 1 的关系
struct Node{
int l, r, t;
}e[M];
bool inline cmp(Node x, Node y){
return x.t > y.t;
}
bool inline check(int l, int r, int t){
for(int i = l; i < r; i++)
if(f[i] == -1 || f[i] == t) return true;
return false;
}
int main(){
memset(f, -1, sizeof f);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
int t, l, r; scanf("%d%d%d", &t, &l, &r);
e[i] = (Node){l, r, t};
}
sort(e + 1, e + 1 + m, cmp);
for(int i = 1; i <= m; i++){
int l = e[i].l, r = e[i].r, t = e[i].t;
if((!check(l, r, t))) { puts("NO"); return 0; }
else for(int i = l; i < r; i++)
if(f[i] == -1)f[i] = t;
}
int last = n; printf("YES
%d ", n);
for(int i = 1; i < n; i++)
if(f[i]) printf("%d ", last);
else printf("%d ", --last);
return 0;
}
E. Tree Painting
换根法。发现是一颗树。每次扩展的时候，假设时间倒流，发现是一个逐层逆推递进的过程。
对于任意两点((u, v))，除了他们的路径上的贡献外，所有外面的扩展是相同的。
设
-
(f[u][0])为该点向下扩展的花费，包括(u)的花费
-
(f[u][1])为改点向上扩展的花费，不包括(u)的花费
-
(size[u])为以(u)为子树的大小
状态转移方程：
(f[u][0] = size[u] + sum_{(u , v)} f[v][0])
(f[v][1] = (n - size[v]) + f[u][1] + (f[u][0] - size[u] - f[v][0]) (u , v))
答案：
(max{f[i][0] + f[i][1] + (n - size[i])} (1 <= i <= n))
这里可以理解为两者均是时间倒流的产物，第一次扩展是先扩展下面的，所以需要计算首次合并。
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 200010, M = N << 1;
typedef long long LL;
int n, head[N], numE = 0;
LL f[N][2], size[N];
struct Edge{
int next, to;
}e[M];
void addEdge(int from, int to){
e[++numE].next = head[from];
e[numE].to = to;
head[from] = numE;
}
void dfs_(int u, int fa){
size[u] = 1;
for(int i = head[u]; i; i = e[i].next){
int v = e[i].to;
if(v == fa) continue;
dfs_(v, u);
size[u] += size[v];
f[u][0] += f[v][0];
}
f[u][0] += size[u];
}
void dfs(int u, int fa){
for(int i = head[u]; i; i = e[i].next){
int v = e[i].to;
if(v == fa) continue;
f[v][1] = (n - size[v]) + f[u][1] + (f[u][0] - size[u] - f[v][0]);
dfs(v, u);
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i < n; i++){
int u, v; scanf("%d%d", &u, &v);
addEdge(u, v); addEdge(v, u);
}
dfs_(1, 0);
dfs(1, 0);
LL ans = -1;
for(int i = 1; i <= n; i++)
ans = max(ans, f[i][0] + f[i][1] + (n - size[i]));
printf("%lld
", ans);
return 0;
}