[AHOI 2001] 彩票摇奖

知识点

集合、标记数组、频次统计

解题思路

用布尔数组记录7个中奖号码。逐张彩票统计命中个数k，若k>0则累加cnt[k]。按k从7到1输出。

正确性说明

单张彩票号码各不相同，因此命中数就是该彩票与中奖号码集合的交集大小。交集大小唯一决定奖项，分别累加后逆序输出正好对应特等奖到六等奖。

易错点

号码的位置无关；0个命中不属于任何奖项；不能把号码值当作奖项编号。

复杂度

时间O(7n+33)=O(n)，额外空间O(33)=O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;bool win[34]={};int cnt[8]={};
    for(int i=0,x;i<7;++i){cin>>x;win[x]=true;}
    for(int i=0;i<n;++i){int k=0;for(int j=0,x;j<7;++j){cin>>x;k+=win[x];}if(k)++cnt[k];}
    for(int k=7;k>=1;--k)cout<<cnt[k]<<(k==1?'\n':' ');
}