South Pacific Divisionals Bake Off

文章转载自：xuanqis.com

Description

Davy decided to start a weekend market stall where he sells his famous cakes. For the first market stall, Davy decided to bake n cakes. Each cake is described by its deliciousness and the flavours it contains, which is a (possibly empty) subset of the flavours {caramel, cherry, chocolate, cinnamon, coconut, cookies}. Because of Davy’s skill in baking, he has a line of m customers when he opens his stall who wish to buy a cake. Davy will serve them in the order they are lined up. Each customer has a required subset of flavours they would like in their cake, but are happy to receive additional flavours in their cake. Davy will give each customer the most delicious cake left that contains at least the flavours that the customer has asked for. You should help Davy determine which cake to sell to each customer (or if there is no cake that satisfies that customer’s requirements, in which case, they buy nothing).

Input

The first line contains two integers n (1 ≤ n ≤ 300 000), which is the number of cakes, and m (1 ≤ m ≤ 100 000), which is the number of customers. The next 6 lines describe the flavours contained in the cakes. The first of these lines contains a string of length n, which describes if caramel is in each cake. This string will contain a 1 in the ith position if cake i contains caramel and 0 otherwise. The second through sixth of these lines will describe cherry, chocolate, cinnamon, coconut and cookies, respectively, in the same format. The cakes are numbered from left to right, starting with cake 1 on the left. No two cakes have the same deliciousness and are sorted by their deliciousness, with cake 1 being the least delicious and cake n being the most delicious. The next 6 lines describe the flavours requested by the customers. The first of these lines contains a string of length m, which describes if each customer has requested caramel in their cake. This string will contain a 1 in the ith position if customer i requested caramel and 0 otherwise. The second through sixth of these lines will describe cherry, chocolate, cinnamon, coconut and cookies, respectively, in the same format.

Output

Display the number of the cake purchased by each customer in the order that they are requested. If a customer does not purchase a cake, display -1 for them instead.

Sample Input

4 2
0001
1111
0001
1111
0001
1111
01
11
01
11
01
11

3 4
000
000
000
010
101
110
0000
0000
0000
0010
1000
0100

Sample Output

4 -1

3 2 -1 1

Hint

Source
South Pacific Divisionals

题意

有n个蛋糕，m个顾客，顾客排队购买蛋糕。每个蛋糕可以具有六种属性，顾客购买具有一定要求的蛋糕，可以卖给顾客属性多于他要求的蛋糕，但不能少。当多个蛋糕满足顾客要求时，从后面的蛋糕卖起。就是将蛋糕标号为1-n，第n个和n-1个都满足要求，卖第n个给顾客。

思路

首先将蛋糕转化为十进制的数字，六种口味，总共才64种，所以用一个优先队列数组（vector也行）来将该类型蛋糕的序号存入，然后对顾客的需要进行匹配，枚举看哪些类型的蛋糕满足顾客的要求，其中满足要求则按位与顾客需要的蛋糕的值得到的值仍然是顾客需要蛋糕的值。得出最大的序号，删除该序号所在队列的最大值。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>

using namespace std;

priority_queue<int> que[64];  
char str[6][310000];  
int num;
int main(){
    freopen("3.txt", "r", stdin);  
    int n,m;  
    while(~scanf("%d%d", &n, &m)){
        for(int i=0;i<64;i++){  //清空队列 
            while(!que[i].empty())que[i].pop();  
        }
        for(int i=0;i<6;i++){  //输入蛋糕的数据 
            scanf("%s",str[i]);  
        }
        for(int i=0;i<n;i++){  //计算蛋糕的类型并存入队列 
            num=0;  
            for(int j=0;j<6;j++){
                if(str[j][i]=='1'){
                    num += (1<<j); 
                }
            }
            que[num].push(i+1);  
        }
        for(int i=0;i<6;i++){  //输入顾客的需要 
            scanf("%s",str[i]);  
        }
        for(int i=0;i<m;i++){
            int numa=-1;//记录要删除值的队列 
            int numb=-1;//记录下标值 
            num=0;  
            for(int j=0;j<6;j++){  
                if(str[j][i]=='1'){  
                    num += (1<<j); 
                }  
            }  
            for(int j=0;j<64;j++){  
                if((j&num)==num){  //该类蛋糕满足了顾客的需要 
                    if(!que[j].empty() && que[j].top()>numb){  //还有蛋糕，并且序号大于当前值 
                        numb=que[j].top();  
                        numa=j;  
                    }  
                }  
            }  
            if(numa!=-1)que[numa].pop();  //能满足顾客需要的情况才删除 
            printf("%d",numb);  //输出，如果不能满足，是初值-1 
            if(i==m-1)printf("\n");    
            else printf(" ");    
        }  
    }  
}