u,v,w。
这场考过。
T1 u
差分裸题
#include<bits/stdc++.h> 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<b?a:b; } int read() { int s=0,w=1;char ch=getchar(); while(ch<'0'||ch>'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 <bits/stdc++.h> using namespace std; map <int,double > 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<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f,N=300000; struct bian { int nxt,to,w; } b[N]; int n,head[N],cnt; pair<int,int> 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<int,int> pls(pair<int,int> a,pair<int,int> b) { return make_pair(a.first+b.first,a.second+b.second); } pair<int,int> min(pair<int,int> x,pair<int,int> y) { if(x.first<y.first) return x; else if(x.first>y.first) return y; else if(x.second<y.second) return x; else return y; } void dfs(int x,int fa,int w) { pair<int,int> w1=make_pair(inf,inf); pair<int,int> 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<int,int> flag1=min(pls(w1,f[0][b[i].to]),pls(w2,f[1][b[i].to])); pair<int,int> 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<n;i++) { scanf("%d%d%d%d",&from,&to,&c,&d); if(d==2) { add(from,to,2); add(to,from,2); } else { add(from,to,c!=d); add(to,from,c!=d); } } dfs(1,0,2); printf("%d %d\n",f[0][1].first>>1,f[0][1].second); return 0; }