题面：https://www.cnblogs.com/Juve/articles/11602450.html
u：
用差分优化修改
二维差分：给(x1,y1)，(x2,y2)加上s：
$d[x1][y1]+=s,d[x1][y2+1]-=s,d[x2+1][y1]-=s,d[x2+1][y2+1]+=s$
定义2个差分数组d1，d2，分别记录竖列和斜边的差分
$d1[r][c]+=s,d1[r+l-1][c]-=s,d2[r][c+1]-=s,d2[r+l-1][c+l-1]+=s$
统计是求2个前缀和
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int MAXN=1e3+5;
int n,q,a[MAXN][MAXN],b[MAXN][MAXN],c[MAXN][MAXN],d[MAXN][MAXN],ans=0;
int d1[MAXN][MAXN],d2[MAXN][MAXN];
signed main(){
scanf("%lld%lld",&n,&q);
while(q--){
int r,c,l,s;
scanf("%lld%lld%lld%lld",&r,&c,&l,&s);
int N=min(n,r+l-1),M=min(n,c+l-1);
d1[r][c]+=s,d1[N+1][c]-=s;
d2[r][c+1]-=s,d2[N+1][M+2]+=s;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
a[i][j]=(a[i-1][j]+d1[i][j]);
b[i][j]=(b[i-1][j-1]+d2[i][j]);
c[i][j]=a[i][j]+b[i][j];
d[i][j]=d[i][j-1]+c[i][j];
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
ans^=d[i][j];
}
printf("%lld\n",ans);
return 0;
}
v：
搜索每一个情况，对于重复的用map记忆化一下
注意判断长度为奇数的情况，map超时可以用hash表
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
int n,k,sta=0;
char ch[35];
struct hash_map{
int pre[40000000],cnt;
struct node{
int nxt,to,w;
double v;
}e[6000000];
double &operator[](int sta){
int key=1LL*sta%30000019;
for(int i=pre[key];i;i=e[i].nxt)
if(e[i].to==sta) return e[i].v;
e[++cnt].nxt=pre[key];e[cnt].to=sta;;e[cnt].v=-1.0;
pre[key]=cnt;
return e[cnt].v;
}
}mp;
inline double dfs(re int x,re int st){
if(x==n-k) return 0.0;
if(mp[st]!=-1) return mp[st];
mp[st]=0;
re double sum=0.0;
for(re int i=1;i<=x>>1;i++){
re int con1=st>>i-1&1,con2=st>>x-i&1;
re int to1=st>>1&~((1<<i-1)-1)|st&(1<<i-1)-1;
re int to2=st>>1&~((1<<x-i)-1)|st&((1<<x-i)-1);
sum+=2.0*max(dfs(x-1,to1)+con1,dfs(x-1,to2)+con2)/x;
}
if(x&1){
re int i=x+1>>1;
re int to=st>>1&~((1<<i-1)-1)|st&(1<<i-1)-1;
re int con=st>>i-1&1;
sum+=(dfs(x-1,to)+con)/x;
}
return mp[st]=sum;
}
signed main(){
scanf("%d%d",&n,&k);
scanf("%s",ch+1);
for(re int i=1;i<=n;i++)
sta|=(ch[i]==‘W‘)<<n-i;
sta|=1<<n;
printf("%0.7lf\n",dfs(n,sta));
return 0;
}
w：
如果我们选出一条边，就给边两端的点度数加一，那么第一个答案就是度数为奇数的点个数除以2
我们定义dp[i][0/1]表示i节点，没有/有向父亲的反转i边的两个答案
接下来我们考虑更新：
在更新时我们使用两个参量：p和q，作为更新dp的中间步骤，用p代表不以i为端点做链，q代表以i为端点做链，设i的某个子节点为to，于是有：
p=min(p+dp[to][0],q+dp[to][1])
q=min(p+dp[to][1],q+dp[to][0])
其中p初始化为（0,0），q初始化为（INF，INF）
解释一下：这里pair的add就是对应元素相加（手写！非内置！）
而min操作表示先按pair第一关键字比较，再按第二关键字比较
那么这一步就是一个合并的过程：
首先，i不作为链的端点：分两类来合并：如果子节点与i的边翻转了，那么就要累在以i为端点的链里（因为i与父亲的边不翻转，那么i就将是个端点），如果子节点与i的边没有翻转，那么仅针对这棵子树而言，i并没有作为路径的端点，所以更新没有以i为端点链的代价
如果i作为链的端点，同样分两类来合并：如果子节点与i的边翻转了，那么i显然可以成为链的端点，前提是在此之前i并不是链的端点，所以用之前i不是链的端点的代价来更新；反之，如果子节点与i的边没有翻转，那么就此而言i并不是端点，可要求i是链的一个端点，这样就必须用i原先就是链的端点的代价来更新
遍历根节点所有子节点后，更新dp：
如果i与父亲的边没有翻转。即状态dp[i][0]：
首先，i不作为链的端点肯定是一种可能性，直接比较
接着，如果i是链的一个端点，i和父节点的边还没有翻转，那么说明在这个状态下i是真正的奇度点，所以将状态q的first+1后更新
如果i与父亲的边翻转了，同样分两类更新：
首先，i本身作为了链的端点，而由于i本身就是奇度点，所以仅需将q.second+1来更新即可
还有，如果i本身在下面并没有作为链的端点，而i却与父节点的边发生了翻转，所以i就成为了新的奇度点，同时链长还增加了，所以p.first,p.second均增加即可
最后答案即为dp[1][0].first/2,dp[1][0].second
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=5e5+5;
const int inf=0x3f3f3f3f;
int n;
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],flag[MAXN<<1],cnt=0;
void add(int u,int v,int val){
++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt,flag[cnt]=val;
}
struct node{
int tim,len;
friend node operator + (node a,node b){
return (node){a.tim+b.tim,a.len+b.len};
}
friend bool operator < (node a,node b){
return a.tim==b.tim?a.len<b.len:a.tim<b.tim;
}
}dp[MAXN][2];
node min(node a,node b){
return a<b?a:b;
}
void dfs(int x,int fa,int fl){
node p={0,0},q={inf,inf};
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
dfs(y,x,flag[i]);
node a=p,b=q;
p=min(a+dp[y][0],b+dp[y][1]);
q=min(b+dp[y][0],a+dp[y][1]);
}
if(fl==2){
dp[x][0]=min(p,q+(node){1,0});
dp[x][1]=min(p+(node){1,1},q+(node){0,1});
}
if(fl==1){
dp[x][0]=(node){inf,inf};
dp[x][1]=min(p+(node){1,1},q+(node){0,1});
}
if(fl==0){
dp[x][0]=min(p,q+(node){1,0});
dp[x][1]=(node){inf,inf};
}
}
signed main(){
scanf("%d",&n);
for(int i=1,a,b,c,d;i<n;++i){
scanf("%d%d%d%d",&a,&b,&c,&d);
if(d==2){
add(a,b,2),add(b,a,2);
}else{
if(c==d) add(a,b,0),add(b,a,0);
else add(a,b,1),add(b,a,1);
}
}
dfs(1,0,0);
printf("%d %d\n",dp[1][0].tim/2,dp[1][0].len);
return 0;
}