题目分析

题意简述

父母要为孩子准备圣诞礼物。先公布礼物候选清单，每个孩子提出礼物需求条件，条件由多个条件项“与”起来。条件项类型有：固定礼物子集、某兄弟姐妹礼物、两个条件项交集、某兄弟姐妹礼物排除特定子集。目标是给每个孩子分配最小礼物集满足所有孩子条件。

输入

• 第一行是测试用例数 $T$。
• 每个测试用例首行有两个整数，礼物候选数 $n$（$1\leq n\leq1000$）和孩子数 $m$（$1\leq m\leq100$）。
• 后续按孩子编号顺序描述条件，每个孩子条件：
  • 首行是孩子编号和条件项数。
  • 每行条件项以类型开头：
    • -1 后接固定礼物子集描述。
    • -2 后接兄弟姐妹编号。
    • -3 后接两个条件项描述。
    • -4 后接兄弟姐妹编号和要排除的礼物子集描述。

输出

每个测试用例按孩子编号升序输出礼物分配结果，每行是孩子编号及获赠礼物编号（升序），没礼物则只输出孩子编号。

解题思路

数据表示

用 bitset 表示孩子礼物集合，方便位运算。用结构体 cond 存涉及其他孩子礼物的条件项，vector 存每个孩子的条件项。

条件处理

• -1 类型条件项，直接把对应礼物加入孩子礼物集。
• -2、-3、-4 类型条件项先存 conds 数组，后续处理。

迭代更新

不断迭代更新孩子礼物集，直至不再变化。每次迭代依 conds 数组里的条件项更新每个孩子的礼物集，取并集满足所有条件。

代码实现

#include <iostream>
#include <stdio.h>
#include <bitset>
#include <vector>
using namespace std;

struct cond{
    int type;//只取2,3,4
    int subtype;//只对type=3有效
    int sibNo1, sibNo2;
    bitset<1001> constBit;
};

bitset<1001> bs[110];

vector<cond> conds[110];

int n,m;

void init(){
    for(int i = 1; i <= m; i++) bs[i].reset();
    for(int i = 1; i <= m; i++) conds[i].clear();
}

int main() {
    int t;
    scanf("%d", &t);
    for(int ii = 0; ii < t; ii++){
        scanf("%d%d", &n, &m);
        init();
        for(int chd = 1; chd <= m; chd++){
            int id, gs;
            scanf("%d%d", &id, &gs);
            for(int j = 0; j < gs; j++){
                int type;
                scanf("%d", &type);
                switch(type){
                    case -1:{
                        int ggs;
                        scanf("%d", &ggs);
                        bitset<1001> tempBs;
                        tempBs.reset();
                        for(int k = 0; k < ggs; k++){
                            int temp;
                            scanf("%d", &temp);
                            tempBs.set(temp);
                        }
                        bs[id] |= tempBs;
                        break;
                    }
                    case -2:{
                        cond tmpc;
                        tmpc.type = 2;
                        int sib;
                        scanf("%d", &sib);
                        tmpc.sibNo1 = sib;
                        conds[id].push_back(tmpc);
                        break;
                    }
                    case -3:{
                        bitset<1001> b[2];
                        b[0].reset(), b[1].reset();
                        int sibs[2];
                        int numB = 0, numS = 0;
                        int tag;
                        scanf("%d", &tag);
                        if(tag == -1){
                            numB++;
                            int gss;
                            scanf("%d", &gss);
                            for(int k = 0; k < gss; k++){
                                int tmmp;
                                scanf("%d", &tmmp);
                                b[0].set(tmmp);
                            }
                        }
                        else{
                            numS++;
                            scanf("%d", &sibs[0]);
                        }
                        scanf("%d", &tag);
                        if(tag == -1){
                            int gss;
                            scanf("%d", &gss);
                            for(int k = 0; k < gss; k++){
                                int tmmp;
                                scanf("%d", &tmmp);
                                b[numB].set(tmmp);
                            }
                            numB++;
                        }
                        else{
                            scanf("%d", &sibs[numS]);
                            numS++;
                        }
                        if(numB == 2){
                            bs[id] |= (b[0] & b[1]);
                        }
                        else{
                            cond tmpc;
                            tmpc.type = 3;
                            if(numB == 1){
                                tmpc.subtype = 0;
                                tmpc.sibNo1 = sibs[0];
                                tmpc.constBit = b[0];
                            }
                            else{
                                tmpc.subtype = 1;
                                tmpc.sibNo1 = sibs[0];
                                tmpc.sibNo2 = sibs[1];
                            }
                            conds[id].push_back(tmpc);
                        }
                        break;
                    }
                    case -4:{
                        int fei, sib;
                        scanf("%d%d", &fei, &sib);
                        cond tmpc;
                        tmpc.constBit.reset();
                        for(int jj = 1; jj <= n; jj++) tmpc.constBit.set(jj);
                        tmpc.type = 4;
                        tmpc.sibNo1 = sib;
                        scanf("%d%d", &fei, &sib);
                        for(int k = 0; k < sib; k++){
                            int tp;
                            scanf("%d", &tp);
                            tmpc.constBit.reset(tp);
                        }
                        conds[id].push_back(tmpc);
                        break;
                    }
                    default:
                        break;
                }
            }
        }
        while(1){
            bool gb = 0;
            for(int i = 1; i <= m; i++){
                bitset<1001> btemp = bs[i];
                int sz = conds[i].size();
                for(int j = 0; j < sz; j++){
                    cond &c = conds[i][j];
                    if(c.type == 2) btemp |= bs[c.sibNo1];
                    else if(c.type == 4) btemp |= (bs[c.sibNo1] & c.constBit);
                    else if(c.subtype == 0) btemp |= (bs[c.sibNo1] & c.constBit);
                    else btemp |= (bs[c.sibNo1] & bs[c.sibNo2]);
                }
                if(btemp.count() > bs[i].count()){
                    gb = 1;
                    bs[i] = btemp;
                }
            }
            if(!gb) break;
        }
        for(int i = 1; i <= m; i++){
            printf("%d", i);
            for(int j = 1; j <= n; j++){
                if(bs[i][j]) printf(" %d", j);
            }
            printf("\n");
        }
    }
    return 0;
}

代码说明

1. 数据结构

   • bitset<1001> bs[110]：存每个孩子礼物集合。
   • struct cond：存涉及其他孩子礼物的条件项。
   • vector<cond> conds[110]：存每个孩子的条件项。

2. 输入处理

   • init 函数：处理每个测试用例前，重置 bs 和 conds 数组。
   • 用 scanf 读数据，依条件项类型做不同处理。

3. 条件处理

   • -1 类型，把礼物加入 bs[id]。
   • -2、-3、-4 类型，存 conds[id] 中。

4. 迭代更新

   • 用 while 循环更新孩子礼物集，直至不变。
   • 每次迭代依 conds 数组更新 bs 数组。

5. 输出结果

   • 遍历 bs 数组，按孩子编号升序输出礼物分配结果。