【NOIP模拟赛】密码锁

2014年6月1日2,1964

题目描述

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。

题解

此题非常蛋疼。。。

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分

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