题外话
为什么不更ZJOI day1的游记呢。。。。
因为考挂自闭了不想更。等day2考完再说咕咕咕
还是更个SHOI旅游记吧！反正不是自家省选，玩得真开心~~~
day0
SH好热好热啊，感觉到夏天了
day1
考场是一个奇怪的科技中心什么的，早上很早去本来以为要试机，后来发现考场都进不去。
进去了竟然说随便坐。。。我原来那个位置键盘贼难受，后来换了一个鼠标很诡异的位置，不过键盘还挺好用的。
SH还是发了面包，比ZJ优秀（？？？）午饭感觉也还不错的说
暴力60+40+?
T1是送的，T2是个后缀树模板，T3是个没意思的找规律。
T1其实不用“超级钢琴”也能做，二分出第k大的值顺便暴力枚举>k的求异或和。至于多log的话，把二分改成逐位确定就可以省掉那个log。在下代码力弱得没调出来，结果60分排序比较器写成了greater<int>()，于是就爆零了，哭（赛后loj快榜上目前还是rk1 upd:好吧xj大佬们切掉这题以后我瞬间被打爆了。。）；我一开始题还读错了，读成了不相交区间，据说有人按照这个写拿了60。。。
T2大概认真学习过后缀树相关肯定能做出来，大概用到了后缀树上倍增定位+拆点建图。我大概没有学好后缀树，暴力又写挂了。
T3考脑洞和打表功底（出题人被喷了）。我玩了25，类型2根本看不出来，赛后恍然大悟QAQ
得分0+10+25，垫底了
讲课期间：
zjc: 我T2第三个大样例没过，拿了50分；刚刚有人说他三个样例都过了，他几分啊？我看看。。。（翻榜）诶他怎么0分啊
day2
暴力70+60+?
T1是dp，70是暴力dp加k=0的部分分，k=0是两部分分开dp（互相独立）。正解大概就是再优化一下，有限制的情况暴力跑，无限制的用k=0的方法跑。听说km^2会被卡常。
T2是贪心，感觉也是送的？大家好像都会做（只有我拿不到送的分）。链的部分分是个简单贪心，提示正解，正解就是套用链的做法把子树合并起来即可。
T3融合了很多知识点，包括树上连通块边数-点数=1算贡献，树形dp，长链剖分，数据结构等等，现在还没有搞太懂，据说其中一份std写了908行。反正十分毒瘤就是了。我写了大暴力加L=n,k=1的部分分得了20。
得分70+60+20，其实T3估分是24。。。不过挂4分也不想管他了。
upd: 丢失4分原因竟是数组开小。。。。。哭了。
讲课期间：
讲课人：我也是刚刚拿到ppt……（陷入僵局）
（过了一会儿）
讲课人：我们请AC的选手上来讲一下吧！
（过了一会儿，讲T3）
讲课人：我们请最高分选手上来讲一下吧！
（然后放了几页ppt，莫名其妙就结束了讲课）
总结
这个分数尤其day1的得分，总觉得是不太符合自己水平的分数。
虽然一次次考试结果证明自己真的很弱，根本跟不上大家的脚步，每次考试都是那种，总想要飞上天反而摔得粉身碎骨的感觉，正解不会写暴力还统统写挂。
不过自我安慰一下这次就是来玩玩的，反正考挂也没有什么影响，还是非常开心地浪了两天半~~~ QAQ
可惜的是noip实在太烂了连去北京浪的机会都没有，thupc感觉也审不过的吧。
noip。。。真的是一时疏忽，如今算是尝到恶果了。感觉真的只能滚去准备学考了啊。ZJOI二试，可能也要变成旅游了。
等明年吧。不甘心。
upd：放一下我AC的代码
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long using namespace std; const int N=5e5+;
int n,m,c[N*][],w[N*],leaf[N*],p[N],tot=; ll a[N],sum[N],num[N],ans; void ins(ll x){
int now=;
for (int i=;~i;i--){
int b=x>>i&;
if (!c[now][b]) c[now][b]=++tot;
now=c[now][b],w[now]++;
}
leaf[now]++;
} void dfs(int u,int i,ll x,ll y){
if (!u||i<||!w[u]) return;
if (leaf[u]) ans+=leaf[u]*(x^y);
dfs(c[u][],i-,x,y);
dfs(c[u][],i-,x|(<<i-),y);
} int main(){
scanf("%d%d",&n,&m);
rep (i,,n) scanf("%lld",&a[i]),sum[i]=sum[i-]^a[i];
rep (i,,n) ins(sum[i]),p[i]=;
m*=; ll res=;
for (int i=;~i;i--){
ll s=;
rep (j,,n){
ll b=sum[j]>>i&; s+=w[c[p[j]][b^]];
}
if (s<m){
m-=s;
rep (j,,n){
ll b=sum[j]>>i&;
dfs(c[p[j]][b^],i,num[j]|((b^)<<i),sum[j]);
p[j]=c[p[j]][b],num[j]|=b<<i;
}
} else{
res|=1ll<<i;
rep (j,,n){
ll b=sum[j]>>i&; p[j]=c[p[j]][b^],num[j]|=(b^)<<i;
}
}
}
ans+=(ll)m*res;
printf("%lld\n",ans>>);
return ;
}
day1 T1 异或粽子
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define pii pair<int,int>
#define fi first
#define se second
#define Vp vector<pii>
#define ll long long using namespace std; const int N=;
int n,na,nb,Q,fa[N],ch[N][],len[N],pos[N],tot,las,f[N][],id[N]; Vp V[N];
int cnt,head[N],val[N],num,q[N],rd[N];
ll dp[N],ans; char s[N];
struct edge{int to,nxt;}e[N<<]; void adde(int x,int y){
e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt; rd[y]++;
} void sam_init(){
rep (i,,tot){
memset(ch[i],,sizeof(ch[i])),
memset(f[i],,sizeof(f[i])),fa[i]=len[i]=;
}
tot=las=;
}
void extend(int c,int i){
int p=las,np=las=++tot,q,nq;
len[np]=len[p]+,pos[i]=np;
for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if (!p){fa[np]=; return;}
q=ch[p][c];
if (len[p]+==len[q]) fa[np]=q;
else{
nq=++tot; len[nq]=len[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q]; fa[q]=fa[np]=nq;
for (;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
void tree_build(){
rep (i,,tot) f[i][]=fa[i];
rep (j,,) rep (i,,tot) f[i][j]=f[f[i][j-]][j-];
} void get_node(int l,int r,int id){
int x=pos[l];
for (int i=;~i;i--)
if (f[x][i]&&len[f[x][i]]>=r-l+) x=f[x][i];
V[x].push_back(pii(r-l+,id));
} const bool cmp(pii x,pii y){
return x.fi!=y.fi?x.fi<y.fi:x.se>y.se;
}
void graph_build(){
rep (i,,tot){
sort(V[i].begin(),V[i].end(),cmp);
int sz=V[i].size();
rep (j,,sz-){
int x=V[i][j].se+*tot; id[x-*tot]=x;
if (!j) adde(i,x);
if (j<sz-) adde(x,V[i][j+].se+*tot); else adde(x,i+tot);
if (x<=na+*tot){ //A类点有贡献
id[x-*tot]=++num;
adde(x,num),val[num]=V[i][j].fi;
}
}
if (!sz) adde(i,i+tot);
if (fa[i]) adde(fa[i]+tot,i);
}
}
void topo(){
int h=,t=;
rep (i,,num) if (!rd[i]) q[++t]=i,dp[i]=val[i];
ans=;
int tmp=;
while (h<=t){
int u=q[h++]; tmp++;
if (u>*tot+na+nb) ans=max(ans,dp[u]);
for (int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if (!--rd[v]) q[++t]=v;
dp[v]=max(dp[v],dp[u]+val[v]);
}
}
if (t!=num) puts("-1"); else printf("%lld\n",ans);
} int Main(){
scanf("%s",s+),n=strlen(s+); sam_init();
for (int i=n;i;i--) extend(s[i]-'a',i); tree_build();
scanf("%d",&na);
rep (i,,na){int l,r; scanf("%d%d",&l,&r),get_node(l,r,i);}
scanf("%d",&nb);
rep (i,,nb){int l,r; scanf("%d%d",&l,&r),get_node(l,r,i+na);}
num=na+nb+*tot;
graph_build();
scanf("%d",&Q);
rep (i,,Q){int x,y; scanf("%d%d",&x,&y),adde(id[x],id[y+na]);}
topo();
rep (i,,tot) V[i].clear();
rep (i,,num) head[i]=dp[i]=val[i]=rd[i]=; cnt=;
return ;
} int main(){
int T; scanf("%d",&T); while (T--) Main();
return ;
}
day1 T2 字符串问题
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define Vi vector<int>
#define ll long long using namespace std; const int N=,M=,mod=;
int n,m,Q,c0,c1,d0,d1,a[N],bl[N],sum[N],ban[N],ban_c[N],all,lx,rx,ly,ry,Sz,Nowsz;
int f[][M][M],g[N][M],ans,fx[M],fy[M],dp0[M][M],dp1[M][M]; Vi v[N]; void upd(int &x,int y){x+=y; x-=x>=mod?mod:;} void dp(int x,int st){
int sz=v[x].size(),tmp,nowsz=;
rep (i,,sz) rep (j,,Nowsz) g[i][j]=; g[][]=;
rep (i,,sz-){
int y=v[x][i];
if (!ban[y]){
rep (j,,nowsz) g[i+][j]=g[i][j];
continue;
}
rep (j,,nowsz)
if (tmp=g[i][j]){
if (ban[y]!=st&&j+a[y]<=d0) upd(g[i+][j+a[y]],tmp);
if (ban[y]!=st+) upd(g[i+][j],tmp);
}
nowsz+=a[y]; nowsz=min(nowsz,d0);
}
} int Main(){
scanf("%d%d%d%d%d%d",&n,&m,&c0,&c1,&d0,&d1); all=;
rep (i,,n){
int x,y; scanf("%d%d",&x,&y);
v[x].push_back(i),sum[x]+=y,a[i]=y,all+=y,bl[i]=x;
} scanf("%d",&Q);
rep (i,,Q){
int x,y; scanf("%d%d",&x,&y);
ban[x]=y+,ban_c[bl[x]]=;
}
lx=all-c1,rx=c0,ly=all-d1,ry=d0;
if (lx>rx||ly>ry){
rep (i,,m) v[i].clear(),sum[i]=;
rep (i,,n) ban[i]=a[i]=;
return puts(""),;
}
memset(fx,,sizeof(fx)),memset(fy,,sizeof(fy));
fx[]=fy[]=;
rep (i,,m)
if (!ban_c[i]&&sum[i])
for (int j=c0;j>=sum[i];j--) upd(fx[j],fx[j-sum[i]]);
rep (i,,n)
if (!ban[i])
for (int j=d0;j>=a[i];j--) upd(fy[j],fy[j-a[i]]);
rep (i,,c0) rep (j,,d0) dp0[i][j]=(ll)fx[i]*fy[j]%mod;
int now=;
memset(f[now],,sizeof(f[now]));
f[][][]=;
rep (i,,m-) if (ban_c[i+]){
now^=; rep (j,,c0) rep (k,,Sz) f[now][j][k]=;
int sz=v[i+].size();
if (!sz){
rep (j,,c0) rep (k,,Sz) f[now][j][k]=f[now^][j][k];
continue;
}
int nowsz=;
rep (j,,sz-) if (ban[v[i+][j]]) nowsz+=a[v[i+][j]];
nowsz=min(nowsz,d0); Nowsz=nowsz;
rep (j,,c0){
if (j+sum[i+]<=c0){
dp(i+,);
rep (k,,Sz) if (f[now^][j][k])
rep (l,,min(d0-k,nowsz)) if (g[sz][l])
upd(f[now][j+sum[i+]][k+l],(ll)f[now^][j][k]*g[sz][l]%mod);
}
dp(i+,);
rep (k,,Sz) if (f[now^][j][k])
rep (l,,min(d0-k,nowsz)) if (g[sz][l])
upd(f[now][j][k+l],(ll)f[now^][j][k]*g[sz][l]%mod);
}
Sz+=nowsz,Sz=min(Sz,d0);
}
rep (i,,c0) rep (j,,d0){
dp1[i][j]=f[now][i][j];
if (i) upd(dp1[i][j],dp1[i-][j]);
if (j) upd(dp1[i][j],dp1[i][j-]);
if (i&&j) upd(dp1[i][j],mod-dp1[i-][j-]);
}
ans=;
rep (i,,c0) rep (j,,d0){
int Lx=max(lx-i,),Rx=rx-i;
int Ly=max(ly-j,),Ry=ry-j;
if (Lx>Rx||Ly>Ry) continue;
int s=dp1[Rx][Ry];
if (Lx) upd(s,mod-dp1[Lx-][Ry]);
if (Ly) upd(s,mod-dp1[Rx][Ly-]);
if (Lx&&Ly) upd(s,dp1[Lx-][Ly-]);
upd(ans,(ll)s*dp0[i][j]%mod);
}
printf("%d\n",ans);
rep (i,,m) v[i].clear(),sum[i]=;
rep (i,,n) ban[i]=a[i]=;
return ;
} int main(){
int T; scanf("%d",&T); while (T--) Main();
return ;
}
day2 T1 皮配
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define Vi vector<int>
#define ll long long using namespace std; const int N=2e5+;
int n,cnt,head[N],a[N],fa[N],id[N]; ll ans; priority_queue<int> q[N];
struct edge{int to,nxt;}e[N<<]; void adde(int x,int y){
e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt;
} priority_queue<int> c;
void merge(priority_queue<int> &a,priority_queue<int> &b){
if (a.size()<b.size()) swap(a,b);
while (!c.empty()) c.pop();
while (!b.empty()){
int x=max(a.top(),b.top());
a.pop(),b.pop(),c.push(x);
}
while (!c.empty()) a.push(c.top()),c.pop();
} void dfs(int u){
for (int i=head[u];i;i=e[i].nxt) dfs(e[i].to);
for (int i=head[u];i;i=e[i].nxt) merge(q[u],q[e[i].to]);
q[u].push(a[u]);
} int main(){
scanf("%d",&n);
rep (i,,n) scanf("%d",&a[i]);
rep (i,,n) scanf("%d",&fa[i]),adde(fa[i],i);
dfs();
while (!q[].empty()) ans+=q[].top(),q[].pop();
printf("%lld\n",ans);
return ;
}
day2 T2 春节十二响