首页 > 代码库 > 【NOIP模拟赛】密码锁

【NOIP模拟赛】密码锁

题目描述

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

提示

【样例输入2】
3 2 1
1 2
3
【样例输出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。

首先最终状态是1 1 1 0 1 1 1 1 1 0 0

差分后为     1 0 0 1 1 0 0 0 0 1 0

这个差分结果可以换成括号序列的思想来理解

四个1分别出现在1 4 5 10四个位置,这是一个半闭半开区间,也就是说[1,4) [5,10)这两个区间内的数都必须是1

怎么办。

我们先处理出每一段区间全部变成1所需要的最少操作数

初始时所有的位置都是0,所以我们的任务是让[1,4) [5,10)这两个区间内的数变成1,而且操作数最少

所以考虑所有让这两个内的数变成1的情况,算出每种情况的操作数,然后取最小

把[1,4) [5,10)这两个区间内的数变成1就是把这两个区间内的元素取反

我们发现,取反这两个区间和取反[1,6) [4,10)这两个区间是等价的,所以这些数可以随机两两组合来进行变换,每次变换的加起来就是这种方案的操作数

k辣么小很明显用到状态压缩

#include<iostream>#include<cstdio>#include<queue>#include<cstring>using namespace std;#define inf 1000000000#define N 10005#define M 2000005#define T 45queue<int>q;int n,k,m,num[N],x[N],sz[N],a[N],cnt,dis[N],d[30][30],f[M];bool vis[N],mark[M];void bfs(int x){    while(!q.empty())q.pop();    memset(vis,0,sizeof(vis));    q.push(x);    vis[x]=1;dis[x]=0;    while(!q.empty()){        int now=q.front();q.pop();        for(int i=1;i<=m;i++){            if(now+sz[i]<=n&&(!vis[now+sz[i]])){                vis[now+sz[i]]=1;                dis[now+sz[i]]=dis[now]+1;                q.push(now+sz[i]);            }            if(now-sz[i]>0&&(!vis[now-sz[i]])){                vis[now-sz[i]]=1;                dis[now-sz[i]]=dis[now]+1;                q.push(now-sz[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(){    freopen("password.in","r",stdin);    freopen("password.out","w",stdout);    //freopen("Cola.txt","r",stdin);    scanf("%d%d%d",&n,&k,&m);    for(int i=1;i<=k;i++){scanf("%d",&x[i]);a[x[i]]=1;}    for(int i=1;i<=m;i++)scanf("%d",&sz[i]);    for(int i=n+1;i;i--)a[i]^=a[i-1];    n++;    for(int i=1;i<=n;i++){if(a[i])cnt++,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模拟赛】密码锁