u，v，w。

这场考过。

---

T1 u

差分裸题

#include
using namespace std;
const int N=5000;
int n,m;
long long a[N][N],b[N][N],f[N][N];
long long ans=0;
int _max(int a,int b)
{
return a>b?a:b;
}
int _min(int a,int b)
{
return a'9'){if(ch=='-')w=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
return s*w;
}
int main()
{
n=read();m=read();
for(int i=1,r,c,l,s;i<=m;i++)
{
r=read();
c=read();
l=read();
s=read();
a[r][c]+=s;
a[r+l][c+l]-=s;
b[r+l][c]-=s;
b[r+l][l+c]+=s;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
b[i][j+1]+=b[i][j];
a[i][j]+=a[i-1][j-1];
}
}
for(int j=1;j<=n;j++)
{
for(int i=1;i<=n;i++)
{
a[i][j]+=a[i-1][j];
b[i][j]+=b[i-1][j];
}
}
for(int j=1;j<=n;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]+=a[i][j]+b[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ans^=f[i][j];
}
}
printf("%lld\n",ans);
return 0;
}

---

T2 状压DP+分段记忆化（数组+map）

//不是我代码，转自网络，侵删
#include
using namespace std;
map mp;
int n,k;
char s[100];
double f[1<<25];

double dfs(int node,int tot)
{
if(tot== n - k)
return 0;
if(tot > 24 && mp.find(node)!= mp.end())
return mp[node];
if(tot <= 24 && f[node]!= -1) return f[node]; double sum= 0; for(int i=1;i<= (tot >>1);i++)
{
int color1= (node >> (i-1)) &1;
int color2= (node >> (tot - i)) &1;
int node1= (node >>1) & (~ ((1 << (i-1)) -1)) | (node & ((1 << (i-1)) -1)); int node2= (node >>1) & (~ ((1 << (tot - i)) -1)) | (node & ((1 << (tot - i)) -1)); sum += 2 * max(dfs(node1,tot -1) + color1,dfs(node2,tot -1) + color2) / tot; } if(tot &1) { int i= (tot +1) >>1;
int color= (node >> (i-1)) &1;
int st= (node >>1) & (~ ((1 << (i-1)) -1)) | (node & ((1 << (i-1)) -1)); sum += (dfs(st,tot -1) + color) / tot; } return (tot > 24)?mp[node]= sum:f[node]= sum;
}

int main()
{
scanf("%d %d %s",&n,&k,s);
int node= 0;
for(int i= 0;i< (1 << 25);i++)
f[i]= -1;
for(int i=1;i<= n;i++)
node |= (s[i-1]== 'W') << (n - i);
node |= (1 << n);
printf("%.8f\n",dfs(node,n));
return 0;
}

---

T3 w

树形DP，f[u][0/1]（二元组）表示u点上面的边反转/不反转的最少路径和最短路。

#include
using namespace std;
const int inf=0x3f3f3f3f,N=300000;
struct bian
{
int nxt,to,w;
}
b[N];
int n,head[N],cnt;
pair f[2][N];
void add(int x,int y,int w)
{
b[++cnt].nxt=head[x];
b[cnt].to=y;
b[cnt].w=w;
head[x]=cnt;
}
pair pls(pair a,pair b)
{
return make_pair(a.first+b.first,a.second+b.second);
}
pair min(pair x,pair y)
{
if(x.firsty.first)
return y;
else if(x.second w1=make_pair(inf,inf);
pair w2=make_pair(0,0);
for(int i=head[x];i;i=b[i].nxt)
{
if(b[i].to!=fa)
{
dfs(b[i].to,x,b[i].w);
pair flag1=min(pls(w1,f[0][b[i].to]),pls(w2,f[1][b[i].to]));
pair flag2=min(pls(w1,f[1][b[i].to]),pls(w2,f[0][b[i].to]));
w1=flag1;
w2=flag2;
}
}
if(w==1)
f[0][x]=make_pair(inf,inf);
else
f[0][x]=min(make_pair(w1.first+1,w1.second),w2);
if(w==0)
f[1][x]=make_pair(inf,inf);
else
f[1][x]=min(make_pair(w1.first,w1.second+1),make_pair(w2.first+1,w2.second+1));
}
int main()
{
scanf("%d",&n);
for(int i=1,from,to,c,d;i>1,f[0][1].second);
return 0;
}