【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】

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。

首先最终状态是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 45

queue<int>q;

int n,k,m,num[N],x[N],sz[N],a[N],cnt,dis[N],d[][],f[M];

bool vis[N],mark[M];

void bfs(int x){

    while(!q.empty())q.pop();

    memset(vis,,sizeof(vis));

    q.push(x);

    vis[x]=;dis[x]=;

    while(!q.empty()){

        int now=q.front();q.pop();

        for(int i=;i<=m;i++){

            if(now+sz[i]<=n&&(!vis[now+sz[i]])){

                vis[now+sz[i]]=;

                dis[now+sz[i]]=dis[now]+;

                q.push(now+sz[i]);

            }

            if(now-sz[i]>&&(!vis[now-sz[i]])){

                vis[now-sz[i]]=;

                dis[now-sz[i]]=dis[now]+;

                q.push(now-sz[i]);

            }

        }

    }

    for(int i=;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 ;

    if(mark[x])return f[x];

    mark[x]=;f[x]=inf;

    int st=;

    for(int i=;i<=cnt;i++){

        if(x&(<<(i-))){

            if(!st)st=i;

            else{

                if(d[st][i]!=inf)

                f[x]=min(f[x],dp(x^(<<(st-))^(<<(i-)))+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=;i<=k;i++){scanf("%d",&x[i]);a[x[i]]=;}

    for(int i=;i<=m;i++)scanf("%d",&sz[i]);

    for(int i=n+;i;i--)a[i]^=a[i-];

    n++;

    for(int i=;i<=n;i++){if(a[i])cnt++,num[i]=cnt;}

    for(int i=;i<=n;i++)if(a[i])bfs(i);

    dp((<<cnt)-);

    if(f[(<<cnt)-]==inf)printf("-1");

    else printf("%d",f[(<<cnt)-]);

    return ;

}

巴特西

【NOIP模拟赛】密码锁

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章