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[][],b[][];
ll read()
{
ll aa=,bb=;char cc=getchar();
while(cc>''||cc<''){if(cc=='-') bb=-;cc=getchar();}
while(cc>=''&&cc<=''){aa=(aa<<)+(aa<<)+(cc^'');cc=getchar();}
return aa*bb;
}
int main()
{
n=read();m=read();
ll r,c,l,s;
for(int i=;i<=m;i++){
r=read();c=read();l=read();s=read();
a[r][c]+=s;a[min(r+l,n+)][c]-=s;
b[min(r+l,n+)][c+]-=s;b[min(r+l,n+)][min(c+l+,n+)]+=s;
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
a[i][j]+=a[i-][j];
b[i][j]+=b[i][j-];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
a[i][j]+=b[i][j];
a[i][j]+=a[i-][j-];
ans^=a[i][j];
}
}
printf("%lld\n",ans);
return ;
}
u
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[(<<)+];
char s[];
cc_hash_table<int,double>g;
double dfs(int now,int num)
{
if(n-num>=m) return ;
if(num<=&&f[now]!=-) return f[now];
if(num>&&g.find(now)!=g.end()) return g[now];
double sum=;
for(int i=;i<=num>>;i++){
int c1=(now>>(num-i))&,c2=(now>>(i-))&;
int las1=now&((<<num-i)-),las2=now&((<<i-)-);
int st1=(now>>num-i+<<num-i)+las1,st2=(now>>i<<i-)+las2;
sum+=*max(dfs(st1,num-)+c1,dfs(st2,num-)+c2);
}
if(num&){
int nn=num>>;
int c=(now>>nn)&;
int las=now&((<<nn)-);
int st=(now>>nn+<<nn)+las;
sum+=dfs(st,num-)+c;
}
sum=(double)sum/num;
if(num<=) f[now]=sum;
else g[now]=sum;
return sum;
}
int main()
{
scanf("%d%d%s",&n,&m,s+);
for(int i=;i<=(<<);i++) f[i]=-;
sta=;
for(int i=;i<=n;i++){
sta<<=;
if(s[i]=='W') sta|=;
}
printf("%.7lf\n",dfs(sta,n));
return ;
}
v
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[];
int n,tot,nxt[];
pair<int,int>f[][];
int read()
{
int aa=,bb=;char cc=getchar();
while(cc>''||cc<''){if(cc=='-') bb=-;cc=getchar();}
while(cc>=''&&cc<=''){aa=(aa<<)+(aa<<)+(cc^'');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(,);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][]),cal(w2,f[y][]));
pair<int,int>tmp2=min(cal(w1,f[y][]),cal(w2,f[y][]));
w1=tmp1;w2=tmp2;
}
if(tpy==){
f[x][]=min(w1,make_pair(w2.first+,w2.second));
f[x][]=min(make_pair(w1.first+,w1.second+),make_pair(w2.first,w2.second+));
}
else if(tpy==){
f[x][]=make_pair(inf,inf);
f[x][]=min(make_pair(w1.first+,w1.second+),make_pair(w2.first,w2.second+));
}
else if(tpy==){
f[x][]=min(w1,make_pair(w2.first+,w2.second));
f[x][]=make_pair(inf,inf);
}
}
int main()
{
n=read();
int u,v,c,cc;
for(int i=;i<n;i++){
u=read();v=read();c=read();cc=read();
if(cc==) add(u,v,),add(v,u,);
else add(u,v,c^cc),add(v,u,c^cc);
}
dfs(,,);
printf("%d %d\n",f[][].first/,f[][].second);
return ;
}
w