前言
其实我也想直接上题解，但这会让不想颓的人无意间颓到个标签之类的尴尬事件发生。
所以，我的每篇题解还是会说些废话的……
这次不想说太多，只想提一句：
所有题全部#define int long long！！！
内存允许的话能开long long就开long long！！！
一定考虑要不要开long long！！！
T1
正解是差分。
然而我打了一颗线段树（事实上我只是拿线段树将差分$Theta(1)$标记的过程生硬的改成$Theta(logN)$的区间加……）。
我们建n棵线段树。
假设要修改（r,c）,长度为l，增加的权值是s。
我们先将第r行所对应的线段树的[r,c]都加上s，然后在c-1的位置累加上-s的标记1，c的位置累加上s的标记2。
标记1和2是不同的标记，标记1下传到下一行的同一位置，标记2下传到下一行的下一位置，即min(c+1,n)。
每次下传标记时进行一次1到目标位置的区间加法，例如第x行第y个位置下传标记1时需要进行一次第x+1行[1,y]的区间加。
标记1最初赋值为-s，所以是区间加不是区间减。
因为长度只有l，所以需要对第r+l-1行c-1的位置的标记1累加s，第r+l-1行min(c+l-1,n)的位置的标记2累加-s进行抵消。
最后遍历每一行所对应的线段树，将区间加的懒标记全部下传以确保单点权值的正确。
遍历到单点时权值与ans进行异或操作即可。
注意打标记是$Theta(1)$的，因为相同纵坐标的位置在每棵线段树的位置（即数组下标）相同。
总时空复杂度$Theta(N^2logN)$。
然而我按这个思路交上去的代码爆零了……
这……q=0我都没过，why？
！！！
……
然而还是WA。
我百思不得其解，在调了半个小时后听从Joe神的劝告#define int long long，结果：
？？？
在我认真调试后发现我的线段树add函数传参中增量的值开成了int，然而它要开longlong（因为下传标记时进行区间加的增量是longlong）。
#include<cstdio> #define ll long long #define L k<<1 #define R k<<1|1 using namespace std; int const N=1003; inline int read(){ int ss=0;char bb=getchar(); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } int n,q,id[N]; ll ans; inline int min(int x,int y){ return x<y?x:y; } struct S_tree{ struct node{ ll w,f,mf,cf; }a[N<<2]; inline void down(int k,int x,int y){ if(!a[k].f || x==y)return ; ll z=a[k].f; int mid=x+y>>1; a[k].f=0; a[L].w+=z*(mid-x+1),a[L].f+=z; a[R].w+=z*(y-mid),a[R].f+=z; return ; } inline void update(int k){ a[k].w=a[L].w+a[R].w; return ; } void add(int l,int r,int x,int y,ll p,int k){ if(l>=x && r<=y){a[k].w+=p*(r-l+1),a[k].f+=p;return ;} down(k,l,r); int mid=l+r>>1; if(x<=mid)add(l,mid,x,y,p,L); if(y>mid)add(mid+1,r,x,y,p,R); return update(k); } void qj(int l,int r,int k){ if(l==r){ans^=a[k].w;return ;} down(k,l,r); int mid=l+r>>1; qj(l,mid,L),qj(mid+1,r,R); return ; } }tr[N]; void dfs(int now,int x,int y,int k){ if(x==y){ ll z; if(tr[now].a[k].mf){ z=tr[now].a[k].mf; tr[now+1].add(1,n,1,min(x+1,n),z,1); tr[now+1].a[id[min(x+1,n)]].mf+=z; } if(tr[now].a[k].cf){ z=tr[now].a[k].cf; tr[now+1].add(1,n,1,x,z,1); tr[now+1].a[id[x]].cf+=z; } ans^=tr[now].a[k].w; return ; } tr[now].down(k,x,y); int mid=x+y>>1; dfs(now,x,mid,L),dfs(now,mid+1,y,R); return ; } void get(int x,int y,int k){ if(x==y){id[x]=k;return ;} int mid=x+y>>1; get(x,mid,L),get(mid+1,y,R); return ; } signed main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read(),q=read(); if(!q)return puts("0"),0; get(1,n,1); while(q--){ int r=read(),c=read(),l=read(); ll s=read(); tr[r].add(1,n,c,c,s,1); tr[r].a[id[c]].mf+=s; if(c^1){ tr[r].a[id[c-1]].cf-=s; if(r+l-1<=n)tr[r+l-1].a[id[c-1]].cf+=s; } if(r+l-1<=n)tr[r+l-1].a[id[min(c+l-1,n)]].mf-=s; } for(register int i=1;i<n;++i) dfs(i,1,n,1); tr[n].qj(1,n,1); printf("%lld",ans); return 0; }
T2
相当于记忆化搜索。
记录状态（st，x）下的搜索答案，再次搜到直接回溯。
其中st是剩余球的状态，x是进行到第几次操作。
注意位运算的运用可大大缩短运行时间。
还有搜索第x次操作时对于长度为n-x+1的可行域我们只搜一半即可，另一半是一样的。
对（st，x）的状态记录需要用Hash表。
一般都记录了点对，但因为x值域只有[1,30]，所以我直接开了30个Hash表，插入和查询状态（st，x）时直接在第x个Hash表中操作。
复杂度并不会证明，据说状态上界为$sumlimits_{i=1}^{n+1}Fib(i)$。
upd.大神skyh的证明：
我的代码double改成float是可以AC的，但有的代码AC不了。可能我是欧洲人？
#include<cstdio> using namespace std; int const N=31,MOD=7e5+1,M=7e5+1; int n,k,ct,cc,lt; struct node{ int head[MOD],Next[M],to[M],t; double ww[M]; inline int find(int x){ for(register int i=head[x%MOD];i;i=Next[i]) if(to[i]==x)return i; return 0; } inline void ins(int x,double z){ int now=x%MOD; to[++t]=x,ww[t]=z; Next[t]=head[now],head[now]=t; return ; } }Hash[N]; inline double max(double x,double y){ return x>y?x:y; } inline int del(int x,int y){ return ((x&(lt-1<<y))>>1)|(x&((1<<y-1)-1)); } double dfs(int x,int ak,int rm){ if(x>k)return rm; int r=n-x+1,lit=r>>1,lp=1,rp=n,cp,now=ak&((1<<r)-1); if((cp=Hash[x].find(ak)))return Hash[x].ww[cp]; double ans(0); for(int i=1;i<=lit;++i) ans+=2*max(dfs(x+1,del(ak,i),rm+((now>>i-1)&1)), dfs(x+1,del(ak,r-i+1),rm+((now>>r-i)&1))); if(r&1)ans+=dfs(x+1,del(ak,lit+1),rm+((now>>lit)&1)); ans/=(double)r; Hash[x].ins(ak,ans); return ans; } int main(){ scanf("%d%d",&n,&k),lt=1<<n; int st=0; char bb=getchar(); while(bb^'W'&&bb^'B')bb=getchar(); for(register int i=1;i<=n;++i,bb=getchar()) if(bb=='W')++ct,st|=1<<i-1; else ++cc; if(!k || cc==n)return puts("0.0000000000"),0; if(k==n){ printf("%d",ct); return puts(".0000000000"),0; } if(ct==n)return printf("%d.0000000000",k),0; printf("%.10lf",dfs(1,st,0)); return 0; }
T3
大神级题目，思路很不错。
题解请参考露迭月大神的博客。
注意dp[i][0]是不向上伸出翻转边，dp[i][1]是伸出。
时间复杂度$Theta(N)$。
放一下我的代码：
#include<cstdio> #include<iostream> #define mk make_pair #define fr first #define sc second using namespace std; typedef pair<int,int> pi; int const N=1e5+5,lar=1e9+7; const pi lp=mk(lar,lar),rp=mk(0,0); inline int read(){ int ss=0;char bb=getchar(); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } int n,ans,tot; int head[N],Next[N<<1],to[N<<1],lt[N<<1],t; pi f[N][2]; inline void add(int x,int y,int z,int p){ to[++t]=y,lt[t]=p==2?2:(z^p); Next[t]=head[x],head[x]=t; return ; } pi operator + (pi x,pi y){ return mk(x.fr+y.fr,x.sc+y.sc); } void dfs(int x,int fa,int z){ pi a=lp,b=rp,c,d; for(int i=head[x],y;i;i=Next[i]) if((y=to[i])^fa){ dfs(y,x,lt[i]); c=min(a+f[y][0],b+f[y][1]),d=min(a+f[y][1],b+f[y][0]); a=c,b=d; } f[x][0]=z==1?lp:min(mk(a.fr+1,a.sc),b); f[x][1]=z?min(mk(a.fr,a.sc+1),mk(b.fr+1,b.sc+1)):lp; return ; } int main(){ n=read(); for(register int i=1,ff,tt,zz,pp;i<n;++i) ff=read(),tt=read(),zz=read(),pp=read(), add(ff,tt,zz,pp),add(tt,ff,zz,pp); dfs(1,0,0); printf("%d %d",f[1][0].fr>>1,f[1][0].sc); return 0; }