T1 u
拿到题感觉他很水，但到死没想到正解，只会骗部分分（我太弱了）
考虑用两个差分数组维护，不同的是最后更新答案是$a[i][j]+=a[i-1][j-1]$，首先考虑在斜着加的起点，就是竖着的直角边，在这些地方打上标记，可以竖着差分，n^2扫一遍就得到了需要所有的标记。但下边有一部分加多了，那就在第$r+l$行的$c+1~c+l+1$的地方减去该贡献，所以再用一个差分数组横着记录哪些地方需要减。最后把两个差分数组相加，就是最后的差分数组，利用$a[i][j]+=a[i-1][j-1]$转移过来就是最后的表，直接暴力统计答案即可
记得开$long long$，不然炸成0分
#include<iostream> #include<cstdio> #define ll long long using namespace std; ll n,m,ans,a[1010][1010],b[1010][1010]; ll read() { ll aa=0,bb=1;char cc=getchar(); while(cc>'9'||cc<'0'){if(cc=='-') bb=-1;cc=getchar();} while(cc>='0'&&cc<='9'){aa=(aa<<3)+(aa<<1)+(cc^'0');cc=getchar();} return aa*bb; } int main() { n=read();m=read(); ll r,c,l,s; for(int i=1;i<=m;i++){ r=read();c=read();l=read();s=read(); a[r][c]+=s;a[min(r+l,n+1)][c]-=s; b[min(r+l,n+1)][c+1]-=s;b[min(r+l,n+1)][min(c+l+1,n+1)]+=s; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]+=a[i-1][j]; b[i][j]+=b[i][j-1]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]+=b[i][j]; a[i][j]+=a[i-1][j-1]; ans^=a[i][j]; } } printf("%lld\n",ans); return 0; }
T2 v
$n$的范围很小，只有30，考虑状压，倒着转移就行了（我太菜了，这都没想到）
如果记录每个球是否在剩余的序列里，会有很多冗余状态（剩下的球不同但颜色排列相同），所以改变状态，改为记录剩余的序列颜色顺序为sta的期望。$0$表示$B$，$1$表示$W$。最初始的状态就是原序列里的$01$状态。记忆化搜索用$dfs$转移。在当前状态为$now$，剩余$num$个球，抽到$i（i<=num/2）$的时候（正着和倒着的期望+是否是白色）$*2/num$，$*2$是因为抽到对称的数的时候贡献一样。如果当前$num$是奇数，特殊转移一下中间那一位就行。拿掉这个地方的球后剩下的状态可以用二进制搞（稍恶心），最后记忆化$f[i][sta]$表示还剩$i$个球的时候，颜色状态为$sta$的期望。
由于$n$太大，数组开不下，所以可以用$map$，小的用数组记，大的用$map$（全用$map$会$T$的很惨）
但这样仍然不能过最后一个点（毒瘤出题人）
我们发现每个状态都是$2^i$，所以第一维可以省掉，在每个状态的$i+1$为打上标记，就代表了第一维。这样我们就可以愉快的用$hash$表优化了，你也可以用一些奇技淫巧，比如$pbds$库中自带的$hash$表
#include<iostream> #include<cstdio> #include<cstring> #include<unordered_map> #include<ext/pb_ds/tree_policy.hpp> #include<ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; int n,m,sta; double f[(1<<21)+5]; char s[35]; cc_hash_table<int,double>g; double dfs(int now,int num) { if(n-num>=m) return 0; if(num<=20&&f[now]!=-1) return f[now]; if(num>20&&g.find(now)!=g.end()) return g[now]; double sum=0; for(int i=1;i<=num>>1;i++){ int c1=(now>>(num-i))&1,c2=(now>>(i-1))&1; int las1=now&((1<<num-i)-1),las2=now&((1<<i-1)-1); int st1=(now>>num-i+1<<num-i)+las1,st2=(now>>i<<i-1)+las2; sum+=2*max(dfs(st1,num-1)+c1,dfs(st2,num-1)+c2); } if(num&1){ int nn=num>>1; int c=(now>>nn)&1; int las=now&((1<<nn)-1); int st=(now>>nn+1<<nn)+las; sum+=dfs(st,num-1)+c; } sum=(double)sum/num; if(num<=20) f[now]=sum; else g[now]=sum; return sum; } int main() { scanf("%d%d%s",&n,&m,s+1); for(int i=0;i<=(1<<21);i++) f[i]=-1; sta=1; for(int i=1;i<=n;i++){ sta<<=1; if(s[i]=='W') sta|=1; } printf("%.7lf\n",dfs(sta,n)); return 0; }
T3 w
树上$dp$，在最小化操作次数的前提下最小化路径长度，最方便的就是用二元组将两个捆绑
设$f[x][0/1]$表示x与x的父亲的连边是否翻转，$0$不翻转，$1$翻转，$first$表示度为奇数的点的个数，$second$表示路径长度
$1.$一条边最优情况下只会被翻转一次
$2.$如果翻转一条边的同时在他的两个端点处$+1$，那么最后操作此时就是度为奇数的点的个数$/2$
设$w1$为当前$x$不作为一条翻转链的端点的最优情况，$w2$为$x$作为一条翻转链的端点，$y$为$x$的儿子（$x$肯定最多只会作为一条链的端点）
$w1=min（w1'+f[y][0],w2'+f[y][1]）$
$w2=min(w1'+f[y][1],w2'+f[y][0])$
如果x不作为端点$w1$：他儿子跟他的连边不翻转，那么需要他本身就不是端点;他儿子跟他的连边翻转了，那就需要$x$本身是端点，然后两条链并起来
如果x是端点$w2$：他儿子跟他的连边翻转了，那他需要他以前不是端点，然后新翻的这一条边使$x$成为端点;他儿子跟他的连边不翻转，那么他应该本来就已经是端点
更新$x$：
$1.x$与父亲的边必须翻：首先$f[x][0]=(inf,inf)$，如果$x$不是端点，那么再连出去一条边就多了一个奇数点，那么度为奇数的点$+1$,路径$+1$;如果$x$是端点（$fa$直接跟$x$连上就行，奇数点不变）只需要路径$+1$，;两者中取$min$，
即$f[x][1]=min(make$_$pair(w1.first+1,w1.second+1),make$_$pair(w2.first,w2.second+1));$
$2.x$与父亲的边不能翻：首先$f[x][1]=(inf,inf)$;如果$x$不是端点，度为奇数的点不变，路径长度不变，所以就是$w1$;如果x是端点，度为奇数的点$+1$,路径长度不变;两者取$min$，
即$f[x][0]=min(w1,make$_$pair(w2.first+1,w2.second))$;
$3.x$与父亲的边可翻可不翻：就是$1,2$的结合
$f[x][0]=min(w1,make$_$pair(w2.first+1,w2.second));$
$f[x][1]=min(make$_$pair(w1.first+1,w1.second+1),make$_$pair(w2.first,w2.second+1));$
每次都要传参传过来$x$与父亲的边的情况，而且建树的时候也可以直接记录这条边是否需要翻转。
#include<iostream> #include<cstdio> #define inf 0x7ffff using namespace std; struct node { int to,nxt,tpy; }h[200100]; int n,tot,nxt[200100]; pair<int,int>f[100100][2]; int read() { int aa=0,bb=1;char cc=getchar(); while(cc>'9'||cc<'0'){if(cc=='-') bb=-1;cc=getchar();} while(cc>='0'&&cc<='9'){aa=(aa<<3)+(aa<<1)+(cc^'0');cc=getchar();} return aa*bb; } int add(int x,int y,int tpy) { h[++tot].to=y; h[tot].tpy=tpy; h[tot].nxt=nxt[x]; nxt[x]=tot; } pair<int,int> cal(pair<int,int> a,pair<int,int> b) { return make_pair(a.first+b.first,a.second+b.second); } void dfs(int x,int fa,int tpy) { pair<int,int>w1,w2;//w1:不以x作为端点 w2：以x作为端点 w1=make_pair(0,0);w2=make_pair(inf,inf); for(int i=nxt[x];i;i=h[i].nxt){ int y=h[i].to; if(y==fa) continue; dfs(y,x,h[i].tpy); pair<int,int>tmp1=min(cal(w1,f[y][0]),cal(w2,f[y][1])); pair<int,int>tmp2=min(cal(w1,f[y][1]),cal(w2,f[y][0])); w1=tmp1;w2=tmp2; } if(tpy==2){ f[x][0]=min(w1,make_pair(w2.first+1,w2.second)); f[x][1]=min(make_pair(w1.first+1,w1.second+1),make_pair(w2.first,w2.second+1)); } else if(tpy==1){ f[x][0]=make_pair(inf,inf); f[x][1]=min(make_pair(w1.first+1,w1.second+1),make_pair(w2.first,w2.second+1)); } else if(tpy==0){ f[x][0]=min(w1,make_pair(w2.first+1,w2.second)); f[x][1]=make_pair(inf,inf); } } int main() { n=read(); int u,v,c,cc; for(int i=1;i<n;i++){ u=read();v=read();c=read();cc=read(); if(cc==2) add(u,v,2),add(v,u,2); else add(u,v,c^cc),add(v,u,c^cc); } dfs(1,0,2); printf("%d %d\n",f[1][0].first/2,f[1][0].second); return 0; }