前言
其实我也想直接上题解，但这会让不想颓的人无意间颓到个标签之类的尴尬事件发生。
所以，我的每篇题解还是会说些废话的……
这次不想说太多，只想提一句：
所有题全部#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）。
#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表中操作。
复杂度并不会证明，据说状态上界为$\sum\limits_{i=1}^{n+1}Fib(i)$。
我的代码double改成float是可以AC的，但有的代码AC不了。可能我是欧洲人？
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<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;
}