「NOIP模拟赛」密码锁
题目描述
输入
输出
样例输入
样例输出
提示
题解
此题非常蛋疼。。。
50分n很小,才20,对位置进行状压,复杂度是O(nm*2^n)。
注意到题目中的是区间修改,把沿途的位置取反,这个可以看做是在模2意义下,给区间的加一操作。在我们通常的思路中,对于区间的操作,原本是要修改区间长度个的位置的情况,我们都可以通过考虑它的差分序列,使得要修改的位置个数变成2个,我们要求最少的修改,使得原序列变成全0。
所以对原序列进行差分,那么每次修改就是要你对i号位置和i+size[]模2意义下的加1。
差分后的序列中,数值为1的个数是不会超过2k个,即不会超过20个。
考虑每次对i和i+x改动的过程,如果原序列中,i号位置和i+x号位置都是0的话,我们这么改,没有任何必要。所以任意时刻,数值为1的位置个数是不会增加的,那么我们可以把每一个的1看成一个的石子,那么每次我们可以把石子往某个方向移动size[]步,如果移动之后的位置存在石子的话,就对对碰,消掉了。
因为是对对碰,石子之间的关系肯定是一个匹配的关系,我们不妨求出Dist[i][j]表示,石子i要走到石子j的位置,至少需要移动多少步,那么我们可以枚举每一个石子,然后进行一遍的bfs即可,这一部分的复杂度是O(2kmn)。
现在问题转化为有一个大小不超过20的完全图,我们想要求它的最小权最大匹配。
对于70%的数据,直接暴力搜即可。
——————————-以下为错误算法————————————–
然后可以将每个点拆成俩个点x,x’,能匹配的点xy从x向y’连边权值为1费用Dist[i][j],源点向x连边,x’向汇连边,都是权值1费用0,然后一遍最小费用最大流就可以出解,但是发现这样是不能排除掉无解的情况的
比如6个点,每3个点互相都可以匹配,这样费用流是可以得到解的,但是显然无法两两配对,所幸数据中无解的情况只有一组。。。90分。。。
其实费用流的方法本身就是有问题的。。。一般图的带权匹配要用带花树解决,流算法不知道到底有多少可取之处,算是一种骗分吧
——————————-以上为错误算法————————————–
100%的做法因为完全图的个数非常小,直接状压DP即可。对于一个状态,我们考虑其下标最小的那个位置和谁匹配了,就能递归成子问题了,复杂度是O(2kmn+2k*2^(2k))。
90分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #define inf 1000000000 #define T 45 #define N 10005 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} return x*f; } int n,K,m,cnt,sz=1,ans; int x[N],size[N],a[N],num[N]; bool vis[N]; int dis[N],d[25][25]; int q[N]; int head[N],from[N]; bool inq[N]; struct data{int from,to,next,v,c;}e[100005]; void ins(int u,int v,int w,int c) { e[++sz].from=u;e[sz].to=v; e[sz].next=head[u];head[u]=sz; e[sz].v=w;e[sz].c=c; } void insert(int u,int v,int w,int c) {ins(u,v,w,c);ins(v,u,0,-c);} //=============================================== bool spfa() { int t=0,w=1; for(int i=0;i<=T;i++)dis[i]=inf; dis[0]=0;q[t]=0;inq[0]=1; while(t!=w) { int now=q[t];t++;if(t==1001)t=0; for(int i=head[now];i;i=e[i].next) if(e[i].v&&dis[now]+e[i].c<dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].c; from[e[i].to]=i; if(!inq[e[i].to]) { inq[e[i].to]=1; q[w++]=e[i].to; if(w==1001)w=0; } } inq[now]=0; } if(dis[T]==inf)return 0; return 1; } void mcf() { int x=inf; for(int i=from[T];i;i=from[e[i].from]) x=min(x,e[i].v); for(int i=from[T];i;i=from[e[i].from]) {e[i].v-=x;e[i^1].v+=x;ans+=e[i].c*x;} } //===============================================费用流 void bfs(int x) { memset(vis,0,sizeof(vis)); int t=0,w=1; dis[x]=0;q[t]=x;vis[x]=1; while(t!=w) { int now=q[t];t++; for(int i=1;i<=m;i++) { if(now+size[i]<=n&&(!vis[now+size[i]])) { vis[now+size[i]]=1; dis[now+size[i]]=dis[now]+1; q[w++]=now+size[i]; } if(now-size[i]>0&&(!vis[now-size[i]])) { vis[now-size[i]]=1; dis[now-size[i]]=dis[now]+1; q[w++]=now-size[i]; } } } for(int i=1;i<=n;i++) if(num[i]) { if(!vis[i])d[num[x]][num[i]]=inf; else d[num[x]][num[i]]=dis[i]; } } int main() { n=read();K=read();m=read(); for(int i=1;i<=K;i++) { x[i]=read(); a[x[i]]=1; } for(int i=1;i<=m;i++)size[i]=read(); for(int i=n+1;i;i--)a[i]^=a[i-1]; n++; for(int i=1;i<=n;i++) if(a[i]) num[i]=++cnt; for(int i=1;i<=n;i++) if(a[i])bfs(i); for(int i=1;i<=cnt;i++) {insert(0,i,1,0);insert(i+cnt,T,1,0);} for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) if(i!=j&&d[i][j]!=inf)insert(i,j+cnt,1,d[i][j]); while(spfa())mcf(); printf("%d",ans/2); return 0; } |
状压实际上似乎不难写。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #define inf 1000000000 #define N 10005 #define M 2000005 #define T 45 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} return x*f; } int n,K,m,cnt; int x[N],size[N],a[N],num[N]; bool vis[N],mark[M]; int dis[N],d[25][25]; int q[N]; int f[M]; void bfs(int x) { memset(vis,0,sizeof(vis)); int t=0,w=1; dis[x]=0;q[t]=x;vis[x]=1; while(t!=w) { int now=q[t];t++; for(int i=1;i<=m;i++) { if(now+size[i]<=n&&(!vis[now+size[i]])) { vis[now+size[i]]=1; dis[now+size[i]]=dis[now]+1; q[w++]=now+size[i]; } if(now-size[i]>0&&(!vis[now-size[i]])) { vis[now-size[i]]=1; dis[now-size[i]]=dis[now]+1; q[w++]=now-size[i]; } } } for(int i=1;i<=n;i++) if(num[i]) { if(!vis[i])d[num[x]][num[i]]=inf; else d[num[x]][num[i]]=dis[i]; } } int dp(int x) { if(!x)return 0; if(mark[x])return f[x]; mark[x]=1; f[x]=inf; int st=0; for(int i=1;i<=cnt;i++) { if(x&(1<<(i-1))) { if(!st)st=i; else { if(d[st][i]!=inf) f[x]=min(f[x],dp(x^(1<<(st-1))^(1<<(i-1)))+d[st][i]); } } } return f[x]; } int main() { n=read();K=read();m=read(); for(int i=1;i<=K;i++) { x[i]=read(); a[x[i]]=1; } for(int i=1;i<=m;i++)size[i]=read(); for(int i=n+1;i;i--)a[i]^=a[i-1]; n++; for(int i=1;i<=n;i++) if(a[i]) num[i]=++cnt; for(int i=1;i<=n;i++) if(a[i])bfs(i); dp((1<<cnt)-1); if(f[(1<<cnt)-1]==inf)printf("-1"); else printf("%d",f[(1<<cnt)-1]); return 0; } |
orz状压
屌,现场怒A
屌
复制题解233333