背景
WZOI的小组成员今天集体食物中毒，什么事情也不能干了，这是一件十分可怕的事。幸亏WZOI的Bqc同志十分在行化学，他可以马上制作出解药来……
问题描述
Bqc经过一段时间的研究发现，要解这种毒需要一种特殊的药物。不幸的是，这种药物在市面上不存在，没有办法Bqc只好亲自制得这种药物。它含有M种化学物质A1,A2,…,AM。现在Bqc的手上有N种药材(每种药材只有一种)，每种药材含有若干种化学物质(Bqc他有一种机器，只要将药材放入机器，就能制得相应的药物)。 Bqc需要你的帮助，他希望你能帮他选取若干种药材，用这些选取的药材制作出Bqc需要的药物。由于这些化学物质是有毒的，因此你选出来的药物，必须含有这M种化学物质。有一点需要注意：根据中医以毒攻毒的理论，两个相同的化学物质在一起，它们的药性会同时消失变为一种无毒物质(大多情况下这种无毒物质会挥发掉，也就是说这种化学物质消失了)。比如说药材1有化学物质1、2，药材2有化学物质1、3，那么如果药材1和药材2混合，你得到的药物会含有化学物质2、3。 Bqc问你，需要选用那些药材可以制得他想要的药物？
输入格式
本题每个测试点存在多组数据，每组输入数据第1行包含两个整数N和M，表示Bqc拥有的药材数目和他所需药物所含的化学物质的种类数目； 第2行共有M个整数，分别表示M中化学物质的编号，用1~50之间的数字编号(输入数据保证同一种化学物质不会被描述多次)； 第3行到第N+2行，每行包含若干个数。第i+2行的第一个数为Mi，表示药材i包含Mi中化学物质，接下来Mi个数，描述药材i含有的化学物质的编号，用1~50之间的数字编号(同一种化学物质可能会被描述多次)。 每组输入数据用一个空行隔开。输出格式对于每组数据输出一行，如果用这些药材可以制得Bqc需要的药物，那么输出“Possible”；否则输出“Impossible”，不包含引号。
样例输入
输出
medicine.in
medicine.out
2 2 2 3 2 1 5 2 1 3 3 3 1 3 4 4 2 3 4 1 1 4
Impossible
Possible
Possible
3 样例解释对于样例的第三组数据，可行的方案有选取 1、3 和选取 2、4. 数据规模对于30%的数据，N≤10，M≤20；对于50%的数据，N≤20，M≤40；对于100%的数据，N≤20，M≤50；对于100%的数据，Mi≤50。保证测试数据的组数不超过100。时间限制 1s 提示同一种化学物质被描述偶数次，那么说明这种物质不存在；否则这种物质存在。
【题解】
①STD：暴搜，时间复杂度由于有T的存在是O(108)左右
②我：
由于只管治病的物质,因此将治病的物质编号压入线性基，
然后查询能否构造11111……1111就是了。时间复杂度O(5*106)
#include#include #include #define Xor go(j,1,m)x[j]^=A[i][j]#define go(i,a,b) for(int i=a;i<=b;i++)int n,m,a[103],M,t,index[103],x[55];bool Prior[103];struct Linear_Base{ int A[55][55],have[55]; void Clear(){go(i,1,m){have[i]=0;go(j,1,m)A[i][j]=0;}} void Insert() { go(i,1,m)if(x[i]){if(!have[i]){have[i]=1; go(j,1,m)A[i][j]=x[j];i=m;}else Xor;} } bool Capable() { go(i,1,m)if(x[i]&&A[i][i])Xor; int sum=0;go(i,1,m)sum+=x[i];return sum==0; }}Tool;int main(){ freopen("medicine.in","r",stdin); freopen("medicine.out","w",stdout); while(~scanf("%d%d",&n,&m)) { Tool.Clear(); memset(Prior,0,sizeof(Prior)); go(i,1,m)scanf("%d",a+i),Prior[a[i]]=1; std::sort(a+1,a+m+1);go(i,1,m)index[a[i]]=i; go(i,1,n){scanf("%d",&M);memset(x,0,sizeof(x)); go(i,1,M){scanf("%d",&t);if(Prior[t])x[index[t]]^=1;} Tool.Insert();}go(i,1,m)x[i]=1;puts(Tool.Capable()?"Possible":"Impossible"); } return 0;}//Paul_Guderian
.