首页 > ACM题库 > HDU-杭电 > hdu 2467 Déjà vu-回溯和剪枝-[解题报告]C++
2014
01-26

hdu 2467 Déjà vu-回溯和剪枝-[解题报告]C++

Déjà vu

问题描述 :

An antique machine with C(n , 3) switches capable of processing integers in the range 0…2N-1 has just been discovered. Each switch is associated to a distinct integer in 0…2N-1 with exactly three ones in its binary representation. By setting switches associated with number X0,X1…XM-1 to on, any integer Y passing through the machine will render a result of Y�X0�X1�…�XM-1(here “�” stands for bitwise-XOR).
Further inspections reveal that contrary to what we assumed in problem B, some of the switches on the machine are damaged due to their old age. We are interested in whether a configuration transforming integer S into T still exists, and if so, the minimum number of switches that have to be set to on to make it possible.
WARNING: a naive algorithm might not be sufficient to solve this problem.

输入:

There are multiple test cases in the input file.
Each test case starts with two integers, N and M ( 1 ≤ N ≤ 20), representing the number of bits and the number of functioning switches, respectively. Two integers, S and T ( 0 ≤ S,T < 2N), come in the next line, followed by another M lines, the ith one describing the value Vi associated to the ith switch ( 0 ≤ Vi < 2N).
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.

输出:

There are multiple test cases in the input file.
Each test case starts with two integers, N and M ( 1 ≤ N ≤ 20), representing the number of bits and the number of functioning switches, respectively. Two integers, S and T ( 0 ≤ S,T < 2N), come in the next line, followed by another M lines, the ith one describing the value Vi associated to the ith switch ( 0 ≤ Vi < 2N).
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.

样例输入:

6 7
55 21
11
22
25
56
41
49
28
5 2
0 21
22
28
0 0

样例输出:

Case #1: 2
Case #2: Impossible

算法:IDA*

这题不知为什么竟比第二名快了10倍,

先把启发函数预处理出来。

p[]为一个数字二进制表示中含1的个数,h[]就是启发函数。当p[i]=1时,因为只能某3个一起改变,随意改变次数至少为3才能到目标状态,所以

h[p[i]]=3,

同理推出1->20的h[]值,然后就基本是IDA*的标准写法了,见代码:

 

int h[]={0,3,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8};          //预处理启发函数值

int p[2000000];

int a[100];

int bound,i,j,n,m,s,t;

bool flag;

 

int count(int x){                                             //位运算计算x中1的个数

    x = (x & 0×55555555) + ((x >> 1) & 0×55555555);

    x = (x & 0×33333333) + ((x >> 2) & 0×33333333);

    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);

    x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);

    x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

    return x;

}

int f(int x){                                               //启发函数

    return h[p[x]];

}

void IDA(int d,int x,int tmp){                           //IDA*一般写法

    if(d==bound){

        if(tmp==t){

            flag=true;

        }

        return ;

    }

    if(f(tmp^t)+d>bound||(m-x)+d<bound) return ;         //后一半是一个较为有用的剪枝,判断无法到达bound就直接返回

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

        IDA(d+1,i,tmp^a[i]);

        if(flag) return ;

    }

}

int main(){

//    freopen("e:\\in.txt","r",stdin);

    for(i=0;i<=1100000;i++)

        p[i]=count(i);

    int cas=0;

    while(1){

        cas++;

        scanf("%d%d",&n,&m);

        scanf("%d%d",&s,&t);

        if(!n&&!m) break;

        for(i=1;i<=m;i++)

            scanf("%d",&a[i]);

        flag=false;

        for(bound=0;bound<=m;bound++){

            IDA(0,0,s);

            if(flag)

                break;

        }

        printf("Case #%d: ",cas);

        if(!flag) printf("Impossible\n");

        else printf("%d\n",bound);

    }

    return 0;

}

解题转自:http://hi.baidu.com/_lt_zyc/item/ede0fe349221c0242f20c4c4


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  4. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n