A.
复杂度2^(sqrt(n))*n。
若(n-m)>=n/2，那么直接求答案。
若m>sqrt(n)，那么就可以枚举每一块翻转不翻转，然后统计答案。
若m<=sqrt(n)，那么枚举这个长度为m的模板串长什么样，然后dp。具体比较好想，就是细节有点多吧。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 350 #define inf 1000000007 using namespace std; char s[maxn]; int bit[maxn],n=0,m,f[maxn][3][3],g[maxn][2],sum[maxn][2],c[maxn],cnt[maxn][2]; int ans=inf; bool vis[maxn]; void get_bit() { n=strlen(s); for (int i=1;i<=n;i++) bit[i]=s[i-1]-'0'; } int check1() { memset(g,0,sizeof(g)); int ret=0,low=(n/m)*m; for (int i=low+1;i<=n;i++) ret+=(c[i%m+1]^bit[i]); for (int i=1;i<=(n/m);i++) for (int j=(i-1)*m+1;j<=i*m;j++) g[i][0]+=(c[j%m+1]^bit[j]),g[i][1]+=(c[j%m+1]^bit[j]^1); for (int i=1;i<=(n/m);i++) sum[i][0]=sum[i-1][0]+g[i][0],sum[i][1]=sum[i-1][1]+g[i][1]; int r1,r2,r3,r4; for (int i=1;i<=(n/m);i++) { f[i][0][0]=min(f[i-1][0][0],f[i-1][1][2])+g[i][0]; f[i][1][0]=f[i-1][0][0]+g[i][1]+(i!=1);f[i][1][1]=f[i][1][0]; for (int j=1;j<=i-1;j++) f[i][1][1]=min(f[j-1][0][0]+(sum[i][1]-sum[j-1][1])+(j!=1),f[i][1][1]); f[i][1][2]=min(f[i][1][0],f[i][1][1])+1; } return min(f[n/m][0][0],f[n/m][1][2])+ret; } int check2() { memset(cnt,0,sizeof(cnt)); int low=(n/m)*m,ret=0; for (int i=1;i<=(n/m);i++) for (int j=(i-1)*m+1;j<=i*m;j++) c[j]=bit[j]^vis[i]; for (int i=low+1;i<=n;i++) c[i]=bit[i]; for (int i=1;i<=n;i++) cnt[i%m+1][c[i]]++; for (int i=1;i<=m;i++) ret+=min(cnt[i][0],cnt[i][1]); return ret; } int calc() { int pre=0,ans=0; for (int i=1;i<=(n/m);i++) { if ((!pre) && (vis[i])) ans++; pre=vis[i]; } return (ans<<1)-(vis[1]); } void dfs1(int x) { if (x==m+1) { ans=min(ans,check1()); return; } dfs1(x+1); c[x]=1;dfs1(x+1);c[x]=0; } void dfs2(int x) { if (x==(n/m)+1) { ans=min(ans,check2()+calc()); return; } dfs2(x+1); vis[x]=1;dfs2(x+1);vis[x]=0; } void work1() { int t1=0,t2=0,p=m+1; for (int i=1;i<=n-m;i++) { if (bit[i]==bit[p]) t1++; else t2++; p++; } printf("%d ",min(t1+1,t2)); } void work2() { dfs1(1); printf("%d ",ans); } void work3() { dfs2(1); printf("%d ",ans); } int main() { scanf("%s",s);scanf("%d",&m); get_bit(); if ((n-m)<=(n/2)) work1(); else if (m<=(int)sqrt(n)) work2(); else work3(); return 0; }
B.
首先可以知道一个n^5的dp：dp[i][x][y][0/1]，表示i点子树，有x个连通块，y个孤立点 ，i是不是孤立点的答案。
然后ans=ΣΣ(2x-y-4)*dp[1][x][y][0/1]。
我们展开这个式子，发现ans=2*x*dp[1][x]Σy... - y*dp[1][y]Σx... - 4*2^(n-1)。
第一个代表这个树期望连通块的情况，第二个是期望孤立点的情况。
然后。。。就发现第一块，第二块可以直接O(N)统计。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 50 using namespace std; long long n,x,y,table[maxv],d[maxv]; long long ans=0; int main() { scanf("%lld",&n); for (long long i=1;i<=n-1;i++) { scanf("%lld%lld",&x,&y); d[x]++;d[y]++; } table[0]=1;for (long long i=1;i<=n;i++) table[i]=table[i-1]<<1; ans=2*((n-1)*table[n-2]+table[n-1]); for (long long i=1;i<=n;i++) ans-=table[n-1-d[i]]; ans-=4*table[n-1];ans+=n+2; printf("%.9Lf ",(long double)ans/table[n-1]); return 0; }
C.
简单最小割。。不说了。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxv 50050 #define maxe 500050 #define inf 0x7f7f7f7f7f7f7f7fLL using namespace std; long long n,m,vala[maxv],valb[maxv],sum=0,max_flow=0,x,y,a,b,c,s=1,t,nume=1,g[maxv]; long long dis[maxv]; struct edge { long long v,f,nxt; }e[maxe]; queue <long long> q; void addedge(long long u,long long v,long long f) { e[++nume].v=v;e[nume].f=f; e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0; e[nume].nxt=g[v];g[v]=nume; } bool bfs() { for (long long i=s;i<=t;i++) dis[i]=inf; dis[s]=0;q.push(s); while (!q.empty()) { long long head=q.front();q.pop(); for (long long i=g[head];i;i=e[i].nxt) { long long v=e[i].v; if ((e[i].f>0) && (dis[v]>dis[head]+1)) { dis[v]=dis[head]+1; q.push(v); } } } return dis[t]!=inf; } long long dinic(long long x,long long low) { if (x==t) return low; long long ret=0; for (long long i=g[x];low && i;i=e[i].nxt) { long long v=e[i].v; if ((e[i].f>0) && (dis[v]==dis[x]+1)) { long long dd=dinic(v,min(low,e[i].f)); ret+=dd;low-=dd; e[i].f-=dd;e[i^1].f+=dd; } } if (!ret) dis[x]=inf; return ret; } int main() { scanf("%lld%lld",&n,&m);t=n; for (long long i=2;i<=n-1;i++) {scanf("%lld",&vala[i]);sum+=vala[i];vala[i]<<=1;} for (long long i=2;i<=n-1;i++) {scanf("%lld",&valb[i]);sum+=valb[i];valb[i]<<=1;} for (long long i=1;i<=m;i++) { scanf("%lld%lld%lld%lld%lld",&x,&y,&a,&b,&c);sum+=a+b; if (x>y) swap(x,y); if ((x==1) && (y==n)) { sum-=a+b+c; continue; } if (x==1) vala[y]+=2*a+2*c,sum-=b; else if (y==n) valb[x]+=2*b+2*c,sum-=a; else vala[x]+=a,valb[x]+=b,vala[y]+=a,valb[y]+=b; if ((x!=1) && (y!=n)) addedge(x,y,a+b+2*c),addedge(y,x,a+b+2*c); } for (long long i=2;i<=n-1;i++) addedge(s,i,vala[i]),addedge(i,t,valb[i]); while (bfs()) max_flow+=dinic(s,inf); printf("%lld ",sum-max_flow/2); return 0; }