题解：简单题
#include<bits/stdc++.h>
using namespace std;
int n,m,r,Min = 2147483647,Max;
int main(){
scanf("%d %d %d",&n,&m,&r);
int x;
for(int i = 1;i <= n;++i){
scanf("%d",&x);
Min = min(x,Min);
}
for(int i = 1;i <= m;++i){
scanf("%d",&x);
Max = max(x,Max);
}
if(Max < Min){
printf("%d\n",r);
}
else {
int tmp = r / Min;
r = r % Min;
r += Max*tmp;
printf("%d\n",r);
}
return 0;
}题解：直接从左往右能填就填，然后判断是不是全部被填了。(QAQ考试没写FST了，我的分TAT)
#include <bits/stdc++.h>
using namespace std;
int n;
char s[55][3];
bool flag;
inline bool check(int x,int y)
{
if(s[x][y] == '.' && s[x+1][y] == '.' && s[x][y+1] =='.'&&s[x-1][y]=='.'&&s[x][y-1]=='.') return true;
else return false;
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i++) scanf("%s",s[i]);
bool flag = true;
for(int i = 1;i < n-1;i++)
{
for(int j = 1;j < n-1;j++)
{
if(check(i,j)){
s[i][j] = '#';
s[i+1][j] = '#';
s[i][j+1] = '#';
s[i-1][j] = '#';
s[i][j-1] = '#';
}
}
}
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
if(s[i][j] == '.')
flag = false;
if(flag) printf("YES");
else printf("NO");
return 0;
}Div2.C|Div1.A:Prefix Sum Primes
题意：给你N个数，每个数都是1或者2.现在让你求一个排列，使得这个排列的前缀和数组 拥有最多的素数。
题解：考虑除了2以外所有的质数都是奇数，所以我先把2放在第一个，而且是从3开始有奇质数，这样我后面放奇数个1可以产生尽量多的质数，并且这样的话前缀和是奇数，并且是从3开始产生，然后最后放2，也可以保证前缀和是奇数，可以产生尽量多的质数，最后放1
#include <bits/stdc++.h>
const int MAXN = 2000005;
using namespace std;
int n,a[MAXN],cnt[3];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
++cnt[a[i]];
}
if(cnt[2] != 0) {
printf("2 ");
--cnt[2];
}
int tmp = 0;
if(cnt[1]%2) tmp = cnt[1];
else tmp = cnt[1] - 1;
for(int i = 1;i <= tmp;i++) printf("1 ");
if(cnt[1]) cnt[1] -= tmp;
for(int i = 1;i <= cnt[2];i++) printf("2 ");
if(cnt[1]) printf("1 ");
return 0;
}题意：给你一个长度为N的T字符串(N<=10W),然后有$S_1,S_2,S_3$三个字符串，每次操作为添加或者删除一个S字符串末尾字符，问你能不能在T字符串中找出不相交的三个子序列等于$S_1,S_2,S_3$三个字符串(字符串长度短于250)
题解：设fi[k]：$S_1字符串匹配i个字符S_2字符串匹配j个字符S_3字符串匹配k个字符最后一个使用的T字符串中字符的位置$，然后每次删除字符就直接把对应S字符串长度减短就好了。添加字符则需要使用nxt数组[来自序列自动机]，设nxti表示在大于等于i位置j字符出现的第一个位置。
#include <bits/stdc++.h>
const int MAXN = 1000000,MAXM = 260;
using namespace std;
int n,m,a,b,c;
int f[MAXM][MAXM][MAXM],nxt[MAXN][6],A[MAXN],B[MAXN],C[MAXN];
char s[MAXN];
inline void init()
{
scanf("%d %d",&n,&m);
scanf("%s",s+1);
for(int i = 0;i < 26;i++)
nxt[n+1][i] = nxt[n+2][i] = n + 1;
for(int i = n;i >= 0;i--){
for(int j = 0;j < 26;j++) nxt[i][j] = nxt[i+1][j];
if(i) nxt[i][s[i]-'a'] = i;
}
}
int main()
{
freopen("1.in","r",stdin);
init();
int x;char opt[5];
while(m--)
{
scanf("%s",opt);
if(opt[0] == '+')
{
scanf("%d",&x);
scanf("%s",opt);
if(x == 1){
A[++a] = opt[0] - 'a';
for(int i = 0;i <= b;i++)
for(int j = 0;j <= c;j++){
f[a][i][j] = nxt[f[a-1][i][j]+1][A[a]];
if(i) f[a][i][j] = min(f[a][i][j],nxt[f[a][i-1][j]+1][B[i]]);
if(j) f[a][i][j] = min(f[a][i][j],nxt[f[a][i][j-1]+1][C[j]]);
}
}
if(x == 2){
B[++b] = opt[0] - 'a';
for(int i = 0;i <= a;i++)
for(int j = 0;j <= c;j++){
f[i][b][j] = nxt[f[i][b-1][j]+1][B[b]];
if(i) f[i][b][j] = min(f[i][b][j],nxt[f[i-1][b][j]+1][A[i]]);
if(j) f[i][b][j] = min(f[i][b][j],nxt[f[i][b][j-1]+1][C[j]]);
}
}
if(x == 3){
C[++c] = opt[0] - 'a';
for(int i = 0;i <= a;i++)
for(int j = 0;j <= b;j++){
f[i][j][c] = nxt[f[i][j][c-1]+1][C[c]];
if(i) f[i][j][c] = min(f[i][j][c],nxt[f[i-1][j][c]+1][A[i]]);
if(j) f[i][j][c] = min(f[i][j][c],nxt[f[i][j-1][c]+1][B[j]]);
}
}
if(f[a][b][c] <= n) printf("YES\n");
else printf("NO\n");
}
else {
scanf("%d",&x);
if(x == 1) a--;
if(x == 2) b--;
if(x == 3) c--;
if(f[a][b][c] <= n) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}Div2.E|Div1.C:Tree Generator™
题意：给你一颗括号表达式树，问你这颗树的直径为多大，然后每次操作交换括号表达式中两个括号的位置，问你改变以后的括号表达式树的直径
题解：根据dfs的性质可以知道每有一个'('则树的深度+1，每有一个')'则树的深度-1,设d[x]为序列第x位置的深度，显然d[x]=sumx，所以树的直径问题就被巧妙的转化为max{d[z]+d[x]-2*d[y]}(x<=y<=z)至于怎么求取则需要用线段树来维护
数组含义：
sum[o]:区间和
T[o][0]:区间max(sum[z]+sum[x]-2*sum[y])
T[o][1]:区间max(sum[x])
T[o][2]:区间min(sum[x])
T[o][3]:区间max(sum[x]-2sum[y])
T[o][4]:区间max(sum[z]-2sum[y])数组初始化：
sum[o] = d[x]
T[o][1] = T[o][2] = d[x];
T[o][3] = T[o][4] = -d[x];//d[x]-2*d[x]=-d[x]
T[o][0] = 0;数组维护：
int l = o<<1,r = o<<1|1;
sum[o] = sum[l] + sum[r];
T[o][0] = max(
T[l][0],X,Y,Z均在左区间
T[r][0] X,Y,Z均在右区间
);
T[o][0] = max(T[o][0],
max(
T[l][3]+sum[l]+T[r][1],X,Y在左区间,Z在右区间
T[l][1]-sum[l]+T[r][4] X在左区间,Y,Z在右区间
));
T[o][1] = max(T[l][1],sum[l]+T[r][1]);
T[o][2] = min(T[l][2],sum[l]+T[r][2]);
T[o][3] = max(T[l][3], sum[x]-2sum[y]均在左区间
max(
T[r][3]-sum[l], sum[x]-2sum[y]均在右区间但是需要加上前缀和+sum[l]-2sum[l] =-sum[l]
T[l][1]-2*(T[r][2]+sum[l] sum[x]在左区间sum[y]在右区间
)));
T[o][4] = max(T[l][4], sum[z]-2sum[y]均在左区间
max(
T[r][4]-sum[l], sum[z]-2sum[y]均在右区间但是需要加上前缀和+sum[l]-2sum[l] =-sum[l]
T[r][1]+sum[l]-2*T[l][2] sum[z]在左区间sum[y]在右区间
));#include <bits/stdc++.h>
const int MAXN = 1000000;
using namespace std;
int n,q,cx;
int T[MAXN][5],sum[MAXN],d[MAXN];
char s[MAXN];
inline void init(int o,int x){
sum[o] = T[o][1] = T[o][2] = d[x];
T[o][3] = T[o][4] = -d[x];
T[o][0] = 0;
}
inline void update(int o){
int l = o<<1,r = o<<1|1;
sum[o] = sum[l] + sum[r];
T[o][0] = max(T[l][0],T[r][0]);
T[o][0] = max(T[o][0],max(
T[l][3] + sum[l] + T[r][1],//X Y/Z
T[l][1] - sum[l] + T[r][4] //X/Y Z
)
);
T[o][1] = max(T[l][1],sum[l]+T[r][1]);
T[o][2] = min(T[l][2],sum[l]+T[r][2]);
T[o][3] = max(T[l][3],max( T[r][3]-sum[l] , T[l][1]-2*(T[r][2]+sum[l]) ));
T[o][4] = max(T[l][4],max( T[r][4]-sum[l] , T[r][1]+sum[l]-2*T[l][2] ) );
}
void build(int o,int l,int r){
if(l == r){init(o,l);return;}
int m = l + r >> 1;
build(o<<1,l,m);
build(o<<1|1,m+1,r);
update(o);
}
void modify(int o,int l,int r){
if(l == r){init(o,l);return;}
int m = l + r >> 1;
if(cx <= m) modify(o<<1,l,m);
else modify(o<<1|1,m+1,r);
update(o);
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%d %d",&n,&q);
n = 2*(n-1);
scanf("%s",s+1);
for(int i = 1;i <= n;i++)
if(s[i] == '(') d[i] = 1;
else d[i] = -1;
build(1,1,n);
printf("%d\n",T[1][0]);
int x,y;
while(q--){
scanf("%d %d",&x,&y);
swap(d[x],d[y]);
cx = x;modify(1,1,n);
cx = y;modify(1,1,n);
printf("%d\n",T[1][0]);
}
return 0;
}
