「NOIP模拟赛」密码锁

2014年6月1日5,2944

题目描述

hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,…xk为开，其他开关为关时，密码锁才会打开。

他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）

本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有的钱他哪里能逃过被chenzeyu97 NTR的命运？>_< 于是，他为了虐爆czy，也为了去泡更多的妹子，决定打开这把锁。但是他那么神的人根本不屑这种”水题”。于是，他找到了你。

你的任务很简单，求出最少需要多少步才能打开密码锁，或者如果无解的话，请输出-1。

输入

第1行，三个正整数N，K，M，如题目所述。

第2行，K个正整数，表示开关x1,x2,x3..xk必须为开，保证x两两不同。

第三行，M个正整数，表示size[i]，size[]可能有重复元素。

输出

输出答案，无解输出-1。

样例输入

10 8 2 1 2 3 5 6 7 8 9 3 5

样例输出

提示

「样例输入2」

3 2 1

1 2

「样例输出2」

-1

「数据规模」

对于50%的数据，1≤N≤20，1≤k≤5，1≤m≤3;

对于另外20%的数据，1≤N≤10000，1≤k≤5,1≤m≤30;

对于100%的数据，1≤N≤10000，1≤k≤10，1≤m≤100。

题解

此题非常蛋疼。。。

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分

#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;
}

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;

}

状压实际上似乎不难写。。。

#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;
}

#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;

}

« 「NOIP模拟赛」水灾「CF440C」One – Based Arithmetic »

orz状压

屌，现场怒A

屌

复制题解233333

hzwer.com _ Home | http://hzwer.com

「NOIP模拟赛」密码锁

题目描述

输入

输出

样例输入

样例输出

提示

题解

分类目录

热门文章

Myfriends

近期评论