首页 > ACM题库 > HDU-杭电 > hdu 2286 God and Devil-状态压缩[解题报告]C++
2014
01-05

hdu 2286 God and Devil-状态压缩[解题报告]C++

God and Devil

问题描述 :

There are many gods and devils living on HDU Island, and echo is one of them. Gods always tell the truth whereas devils sometimes tell the truth but sometimes not. What’s more, every god and devil knows all the others are a god or a devil.
One day, an accident unfortunately happened which made echo lose her memory. She was so despairing and determined to turn to others for help. She asked all the residents a question, but all of the answers were merely "Be careful! X is a devil!". As a result she failed to arouse her memory. However, she has to find out a method to calculate the minimum number of devils on the island. Could you help echo to manage it well?

输入:

There are multi-cases (The total number of cases won’t exceed 20). First line is an integer N(1<=N<=15000), the total number of gods and devils. Then N lines follow, each line includes a name, and the length of each name won’t exceed 30. The first name is "echo". The next N-1 lines will be as the formation "A says: Be careful! B is a devil!"(A is different from B), and you can assume that at least one of them will consider echo is a devil and says "Be careful! echo is a devil!".

输出:

There are multi-cases (The total number of cases won’t exceed 20). First line is an integer N(1<=N<=15000), the total number of gods and devils. Then N lines follow, each line includes a name, and the length of each name won’t exceed 30. The first name is "echo". The next N-1 lines will be as the formation "A says: Be careful! B is a devil!"(A is different from B), and you can assume that at least one of them will consider echo is a devil and says "Be careful! echo is a devil!".

样例输入:

3
echo
bigdog
smalldog
smalldog says: Be careful! bigdog is a devil!
bigdog says: Be careful! echo is a devil!
4
echo
Lethe
bigdog
smalldog
Lethe says: Be careful! bigdog is a devil!
smalldog says: Be careful! echo is a devil!
bigdog says: Be careful! smalldog is a devil!

样例输出:

1
2


船过河问题
题意:有n样东西,有m种情况不可以合并过河,一次船可以载t样东西
求最少多少次可以把所有的东西载到河对面 ,不可能的话输出 -1
思路:三层DP i,j是最终岸的状态 L是起始岸的状态
对于每一个i,遍历所有可能转换到i的状态j,对于每一个j遍历 起始岸L ,
表示东西在转移的途中,起始岸的状态是L,终岸的状态是j
转移到终岸之后,再从终岸向起始岸转移,此时终岸的状态是i

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
#define Maxn 1<<12
int Ddc[110];
int n, m, t;
int M, N;
int dp[Maxn];
int pp[Maxn];
bool hash[Maxn];
int co;
int num[Maxn];
//制作Ddc数组,将所有的不可以共存状态存成一个数字
void getmap() {
    char str[1000];
    char st[1000];
    map<string,int>to;
    for (int i = 0 ; i < n; i ++) {
        scanf("%s", st);
        if(to.count(st)) continue;
        to[st] = i;
    }
    getchar();
    memset(Ddc, 0, sizeof(Ddc));
    for (int k = 0; k < m; k ++) {
        gets(st);
        int tm = -1;
        int len = strlen(st);
        for (int i = 0; i <= len; i ++) {
            if(st[i] == ' ' || st[i] == '\0') {
                if(tm != -1) {
                    str[++tm] = '\0';
                    if(to.count(str)) {
                        int a = to[str];
                        Ddc[k] += (1<<a);
                    }
                }
                tm = -1;
            }else {
                str[++tm] = st[i];
            }
        }
    }
}
//获取n里面有多少个1
int getnum(int n)
{
     n = (0x55555555UL&n)+((n>>1)&0x55555555UL);
     n = (0x33333333UL&n)+((n>>2)&0x33333333UL);
     n = (0x0f0f0f0fUL&n)+((n>>4)&0x0f0f0f0fUL);
     n = (0x00ff00ffUL&n)+((n>>8)&0x00ff00ffUL);
     n = (0x0000ffffUL&n)+((n>>16)&0x0000ffffUL);
    return n;
}
//y内是否有x,有返回true
bool Judge(int y, int x) {
    if ((x&y) == x) return true;
    return false;
}

void pri() {
    memset(dp, -1, sizeof(dp));
    memset(hash, 0, sizeof(hash));
    M = 1<<n;
    N = M - 1;
    co = -1;
    pp[++co] = 0;
    for (int i = 1; i < M; i ++) {
        bool mark = true;
        for (int j = 0; j < m; j ++) {
            if(Judge(i,Ddc[j])) {
                mark = false;
                break;
            }
        }
        if(mark) {
            pp[++co] = i;
            hash[i] = true;
        }
    }
    hash[0] = true;
    pp[++co] = N;
}
int Min(int x, int y) {
    return x > y ? y : x;
}
int getans() {
    dp[0] = 0;
    for (int i = 1; i <= co; i ++) {
        for (int j = 0; j < co; j++) {
            if(i == j) continue;
            if(!(dp[j]+1)) continue;
            for (int L = 0; L < co; L ++) {
                if(pp[j]&pp[L]) continue; //i和L中存在相同的东西
                if(pp[i]&pp[L]) continue; //j和L中存在相同的东西
                if((n- num[pp[j]] - num[pp[L]])>t) continue; //从起始岸到终岸的船上的东西超过了t件
                if((n- num[pp[i]] - num[pp[L]])>t) continue; //从终岸到的起始岸船上的东西超过了t件
                if(dp[i]+1) {
                    dp[i] = Min(dp[i], dp[j]+1);
                }else {
                    dp[i] = dp[j]+1;
                }
            }
        }
    }
    return dp[co];
}
void init() {
    memset(num, 0, sizeof(num));
    M = 1<<12;
    for (int i = 0; i < M; i ++) {
        num[i] = getnum(i);
    }
}
//注意要先处理掉没有限制条件的,不然L的范围不只到co-1
int main()
{
    init();
    while(scanf("%d%d%d", &n, &m, &t) != EOF) {
        getmap();
        if(!m) {
            int tmp = n/t;
            if(t*tmp < n) tmp ++;
            printf("%d\n", tmp*2-1);
            continue;
        }
        pri();
        int ans = getans();
        if(ans+1) {
            ans = ans*2 - 1;
            printf("%d\n", ans);
        }else {
            printf("-1\n");
        }
    }
    return 0;
}

  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?