下午5点的时候，突然想起来有这个比赛，看看还有一个小时，打算来AK一下，结果因为最近智商越来越低，翻车了，我还是太菜了。上来10分钟先切掉了C和A，结果卡在了B题，唉。
A.砍树
一眼题，两遍树形DP分黑的多还是白的多
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
inline int read(){char c,p=0;int w;
while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();
for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;
}
template<typename T,typename U>inline char smin(T&x,const U&y){return x>y?x=y,1:0;}
template<typename T,typename U>inline char smax(T&x,const U&y){return x<y?x=y,1:0;}
const int N=1e5+5;
int n,f[N],c[N],ans;
vector<int>g[N];
void dfs(int x,int fa){
f[x]=c[x]==1?1:-1;
for(int y:g[x])if(y!=fa){
dfs(y,x);
smax(f[x],f[x]+f[y]);
}
smax(ans,f[x]);
}
int main(){
n=read();
REP(i,1,n)c[i]=read();
REP(i,2,n){
#define pb push_back
int x=read(),y=read();
g[x].pb(y),g[y].pb(x);
}
dfs(1,0);
REP(i,1,n)c[i]^=1;
memset(f,0,sizeof f);
dfs(1,0);
cout<<ans;
return 0;
}
B.奇怪的回文串
发现满足条件需要每隔一个都相等，two pointers直接扫，线段树维护区间众数即可
考场上想了个二分答案，写了个假队列T了2个点，最近智商真是越来越低了。。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
inline int read(){char c,p=0;int w;
while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();
for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;
}
template<typename T,typename U>inline char smin(T&x,const U&y){return x>y?x=y,1:0;}
template<typename T,typename U>inline char smax(T&x,const U&y){return x<y?x=y,1:0;}
const int N=5e5+7;
int k,n,a[N];
struct hash_table{
int head[N],to[N],ne[N],T;
inline int get(int x){
int p=x%N;
for(int i=head[p];i;i=ne[i])if(to[i]==x)return i;
to[++T]=x,ne[T]=head[p],head[p]=T;return T;
}
}mp;
struct SGT{
struct node{int ls,rs,w;}t[N<<2];
int rt,cnt;
inline void clr(){rt=cnt=0;}
inline void add(int x,int v,int&o,int l=1,int r=mp.T){
if(!o)t[o=++cnt]=(node){0,0,0};
if(l==r)return (void)(t[o].w+=v);
int mid=l+r>>1;
x<=mid?add(x,v,t[o].ls,l,mid):add(x,v,t[o].rs,mid+1,r);
t[o].w=max(t[t[o].ls].w,t[t[o].rs].w);
}
inline int gmax(){return t[1].w;}
}t[2];
void solve(){
int ans=0;
t[0].clr(),t[1].clr();
int l=1;
REP(i,1,n){
t[i&1].add(a[i],1,t[i&1].rt);
while(l<=i){
int x=t[0].gmax(),y=t[1].gmax();
int c0=i/2-(l-1)/2,c1=i/2-(l-1)/2+(i&1)-(l-1&1);
if(c0-x+c1-y<=k)break;
t[l&1].add(a[l],-1,t[l&1].rt);++l;
}
smax(ans,i-l+1);
}
cout<<ans;
}
int main(){
k=read(),n=read();
REP(i,1,n)a[i]=mp.get(read());
solve();
return 0;
}
C.范围查询
经典分块题，按照模数分块，小的存下来，大的暴力
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
inline int read(){char c,p=0;int w;
while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();
for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;
}
template<typename T,typename U>inline char smin(T&x,const U&y){return x>y?x=y,1:0;}
template<typename T,typename U>inline char smax(T&x,const U&y){return x<y?x=y,1:0;}
const int N=40005;
int n,q,a[N];
vector<int>g[402][402],h[N];
int main(){
n=read(),q=read();int mxx=0;
REP(i,1,n)a[i]=read(),h[a[i]].push_back(i),smax(mxx,a[i]);
int B=sqrt(mxx);
REP(i,1,B)REP(j,1,n)g[i][a[j]%i].push_back(j);
while(q--){
#define Q(a) upper_bound(a.begin(),a.end(),r)-lower_bound(a.begin(),a.end(),l)
int l=read()+1,r=read()+1,x=read(),y=read();
if(x<=B)printf("%d\n",Q(g[x][y]));
else{
int ans=0;
for(int i=y;i<=mxx;i+=x)ans+=Q(h[i]);
printf("%d\n",ans);
}
}
return 0;
}