程式碼備份區

題意：

有很多種披薩的餡料，然後有一群人想要一起訂披薩

他們各自有自己的需求，如果是 +A表示她想要A這種料，如果-A表示她不想要A這個料

請你找出一種組合，讓每個人至少滿足其中一個條件(有某種料或是不出現某種料)

解法：

因為料只有16種，所以最可以做暴搜(2^16)

有一些cut

1.只做有出現過的披薩料：在跑暴搜時如果選到某個料，但是這個料沒有人有條件是他，那就可以不理這組

2.如果有某個組合前面已經確定有人不行了，就直接跳掉

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

unsigned int peoY[20];
unsigned int peoN[20];
int maxApp;
int bb;
void input(int n,char ch){
    char temp = getchar()-'A';
    peoY[n] = 0;
    peoN[n] = 0;
    bb |= 1<<(temp);
    if(temp>maxApp)maxApp = temp;
    if(ch=='+') peoY[n] |= 1<<((temp));
    else  peoN[n] |= 1<<((temp));
    while((ch = getchar())!=';'){
        temp = getchar()-'A';
        bb |= 1<<(temp);
        if(temp>maxApp)maxApp = temp;
        if(ch=='+') peoY[n] |= 1<<((temp));
        else  peoN[n] |= 1<<((temp));
    }
    getchar();
}
int main(){
    int i,j;
    int n;
    char ch;
    int max;
    while((ch = getchar())!=EOF){
        n = bb = maxApp = 0;
        input(n++,ch);
        while((ch = getchar())!='.'){
            input(n++,ch);
        }
        getchar();
        maxApp+=1;
        bb = ~bb;
        for(i=0,max=(1<<maxApp);i<max;++i){
            if( (i&bb)) continue;
            for(j=0;j<n && (((peoY[j]&i)|(peoN[j]&(~i)))>0);++j);
            if(j>=n)break;
        }
        if(i==max){
            puts("No pizza can satisfy these requests.");
        }else {
            printf("Toppings: ");
            for(j=0;j<maxApp;++j){
                if(i&(1<<j))putchar('A'+j);
            }
            putchar('\n');
        }
    }
    return 0;
}