一道感觉还不错的分讨题。模拟赛 \(t3\) 剩下 \(1\) 个小时的时候开始做。快结束的时候基本上会了，只写了 \(A\) 性质，不过挂到 \(36\)，好像不挂能直接有 \(96\)。
题意
直接看原题题意或者下面模拟赛版本的题意都可以。
要注意：每次战斗只有两回合，而且对手可以选择不防御。牌是不会消耗的，即之和拥有牌的种类有关。\(npc\) 的牌永远不变。
模拟赛题意：
\(n+1\) 个人， 编号为 \(0\) 的人是玩家， 其余 \(n\) 个人是 \(npc\)。 玩家的目标是战胜所有 \(npc\)。
此外还有 \(m\) 种攻击牌和 \(m\) 种防御牌，第 \(i\) 种防御牌可以防御第 \(i\) 种攻击牌。 每个人初始拥有一些攻击牌和防御牌（攻击牌和防御牌都至少有一种）。玩家的牌随着对局进行会增长。而敌人的牌的集合永远不变。
每一轮中，玩家可以任意挑选一个 \(npc\) 对战(可以对战一个 \(npc\) 任意轮)。
一轮对战分为两个回合，第一回合玩家行动，第二回合 \(npc\) 行动。在一回合内，行动方可以选择打出一张任意类型攻击牌（必须打出），另一方可以选择防御或者不防御。防御的前提是拥有对应的防御牌。注意：任意时刻，打出的牌不会被消耗掉。
玩家在这轮对战中胜利的条件是：成功攻击到对方（未被防御），且没有被对方攻击到（防御到了）。
如果战胜对方，则可以复制这位 \(npc\) 的所有手牌加入自己的手牌。对方手牌不会消失。
同时，玩家还可以复制本场战斗中所有敌人使用过的手牌加入到自己手牌。
玩家可以任意决策一个对战顺序，以及每轮对战中自己出的牌。（可以多次对战同一个角色，且对战顺序可以随着对战的进行而任意调整。）
问是否可以保证无论每轮战斗中对方如何出牌，最终玩家一定战胜过所有 \(npc\)。
多测，\(T\le 100\), \(n,m \le 1000\)，手牌数量总和不超过 \(50000\)。
做法
题意比较复杂，情况比较复杂的时候先尝试通过分讨做掉一些比较简单的情况从而尽量简化剩下的问题。
首先题意等价于当 \(npc\) 尽可能不让玩家获胜时，玩家能否获胜。
对于一次对战，我们定义一个二元组 \((x,y)\)。\(x\) 表示玩家的攻击集合是否是 \(npc\) 防御集合的严格超集，\(y\) 表示 \(npc\) 的攻击集合是否是玩家防御集合的严格超集。如果变量的值是 \(1\)，则攻击方一定可以在这轮进行有效攻击。
如果是 \((1,0)\)，那么玩家一定可以战胜对方，并获得所有手牌。
同时我们发现玩家的胜利条件就是要满足：和任何一个人的对战都是 \((1,0)\) 状态。
如果是 \((1,1)\) 的状态，玩家第一轮一定攻击成功，\(npc\) 一定会选择能造成有效攻击的牌使用。
玩家手牌变化：获得一张敌人指定的攻击牌（自己手牌中没有这张攻击牌对应的防御牌）。
如果是 \((0,0)\) 的状态，敌人一定可以防御成功。但如果敌人选择不防御，则一定会输掉对局。所以敌人将被迫防御。并在下一回合打出任意一张攻击牌。
玩家手牌变化：获得的一张自己指定的防御牌（自己手牌中要有对应的攻击牌），以及一张敌人指定的攻击牌。
如果是 \((0,1)\) 的状态。则敌人可以沿用 \((0,0)\) 的策略。也可以选择在第一轮不防御（减少玩家的防御牌集合），并必须在下一轮进行有效攻击。此时玩家手牌的变化和 \((1,1)\) 的一样。
但是我们无法很好地确定敌方会如何指定手牌。
下面是这题的关键步骤：
当遇到这种不知道下一步如何决策更优的时候，考虑延后决策，（很多 \(dp\) 延后计算的题也是这样的）。
不过赛时我是准备打暴力的时候考虑去编一个搜索顺序，看能不能减少搜索量才发现下面这个结论的：
由于我们发现进行一轮对战之后一定对后续局面不劣。我们可以以任意顺序对战，所以我们不妨先拿上我们确定能够获得的牌，看看会发生什么。
对于 \((1,0)\) 状态，我们肯定全部先操作。对于 \((0,0)\) 状态，我们一定可以收获到若干张防御牌。不妨考虑一直拿，直到不存在这样的状态供我们拿为止。
此时我们惊奇的发现，在剩下的状态（即 \((0,1),(1,1)\) 中，敌人存在一种方案让我们无法收获任何防御牌。也就是说，如果此时有一个敌人仍然能对玩家进行有效攻击（即二元组的第二维是 \(1\)），玩家一定无法获胜。直接做完了。
但其实还有点小问题：比如 \((0,0)\) 状态的对手有 \(1,2\) 的防御牌，玩家只有 \(1\) 的攻击牌，此时按道理玩家只能获得 \(1\) 类型的防御牌。但是如果还存在一个 \((1,0)\) 状态的对手的攻击牌只有 \(2\)，我们可以和他对战得到 \(2\) 的攻击牌，然后再获得 \(2\) 的防御牌。
但我们可以认为玩家可以获得所有 \((0,0)\) 状态的对手的防御牌。因为如果有对手打出了 \(2\) 的攻击牌，我们就可以获得这张防御牌。而如果没有人打出这张牌，那么这张 \(2\) 的防御牌也可有可无。
于是剩下的局面就是，不存在二元组的第二维是 \(1\)。同时也不会有 \((1,0)\) 的（因为都被取完了）。也就是只剩下了若干个 \((0,0)\) 状态。这个看着就能做了。注意我们此时还可以从每个 \((0,0)\) 的对手中获得一张敌人指定的任意攻击牌。
现在问题转化成了：敌人是否存在一种指定攻击牌的方式，使得玩家无法战胜所有敌人。
第一档部分分到这里就已经做完了，因为敌人可以全部选择给玩家第一类攻击牌，所以合法等价于剩下已经没有敌人。
这种选物品的，类似匹配，所以考虑建图。或者说这种指数级枚举，可以通过贪心/建图分析性质来减少枚举量。
如果敌人 \(i\) 存在一张攻击牌 \(c\) 可以有效攻击敌人 \(j\)，就连一条边 \((i,j)\)，颜色为 \(c\)。
由于我们如果战胜了一个敌人，就可以战胜所有他连接到的点，类似连通性关系，考虑缩强联通分量。之后我们只需要战胜所有 \(0\) 入度点的强联通分量即可。
一个强联通分量能被战胜，当且仅当内部存在一个点，其所有颜色的边都有至少一条在该强联通分量内。
实现的时候不用真的对每条颜色建边。查询的时候用 \(bitset\) 维护一下每条边对应的颜色集合即可。
中间的若干步骤都可以用 \(bitset\) 优化。
前半部分的化简，我写的是任意找一个 \((1,0)或(0,0)\) 点。直到找不到为止。
注意：这两个部分不要写成先 \((1,0)\) 后 \((0,0)\) 分开写，因为找到一个 \((0,0)\) 之后可能会产生新的 \((1,0)\) 点，赛时就是因为这个写挂了 \(/ll\)。这部分每个点只会访问 \(2\) 次。是 \(O(n^2/w)\) 的。
后半部分建图，边数是 \(O(n^2)\) 的。不过判断连边和颜色集合还需要一个 \(O(n/w)\) 的代价。总共是 \(O(n^3/w)\) 的。
最后总复杂度就是 \(O(Tn^3/w)\) 的。
常数很小，\(145ms\) 就可以通过，目前最优解。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define siz(s) ((int)s.size())
#define pb push_back
#define fi first
#define se second
#define a(x) array<int,x>
#define de(x) cerr<<#x<<"="<<x<<' '
template<class A> void cn(A&x,A y){if(y<x)x=y;
}
template<class A> void cm(A&x,A y){if(y>x)x=y;
}
const int N=2e3+10;
bitset<N> g[N],f[N];
vector<int> e[N];
int win(bitset<N> &g,bitset<N> &f){return (f&g)!=g;
}
int num,dfn[N],low[N],stk[N],top,bl[N],vis[N],tot;
int n,m;
void tar(int u){dfn[u]=low[u]=++tot;stk[++top]=u;vis[u]=1;for(auto v:e[u]){if(!dfn[v]){tar(v);low[u]=min(low[u],low[v]);}else if(vis[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){int x=0;++num;do{x=stk[top--];bl[x]=num;vis[x]=0;}while(x!=u);}
}
void init(){for(int i=0;i<=n+2;i++){f[i].reset();g[i].reset();e[i].clear();dfn[i]=low[i]=bl[i]=vis[i]=0;}tot=num=top=0;
}
int tst;
void solve(){cin>>n>>m;n--;cout<<"Case #"<<tst<<": ";init();for(int i=0;i<=n;i++){int k1,k2;cin>>k1>>k2;for(int j=1;j<=k1;j++){int x;cin>>x;g[i][x]=1;}for(int j=1;j<=k2;j++){int x;cin>>x;f[i][x]=1;}}vector<int> vis1(n+10,0),vis2(n+10,0);int fl=1;while(fl){fl=0;for(int i=1;i<=n;i++){if(vis1[i])continue;if(win(g[0],f[i])&&!win(g[i],f[0])){f[0]|=f[i];g[0]|=g[i];vis1[i]=1;fl=1;}if(vis1[i]||vis2[i])continue;if(!win(g[i],f[0])){f[0]|=f[i];vis2[i]=1;fl=1;}}}for(int i=1;i<=n;i++){if(win(g[i],f[0])){cout<<"NO\n";return;}}vector<int> p;for(int i=1;i<=n;i++){if(vis1[i])continue;p.pb(i);assert(!win(g[0],f[i])&&!win(g[i],f[0]));}for(auto i:p)for(auto j:p){if(win(g[i],f[j]))e[i].pb(j);}num=0;for(auto i:p){if(!dfn[i])tar(i);}vector<int> ck(num+10,0),in(num+10,0); for(auto u:p){for(auto v:e[u]){if(bl[u]!=bl[v])in[bl[v]]=1;}}for(auto u:p){if(in[bl[u]])continue;bitset<N> rs;for(auto v:e[u]){if(bl[u]==bl[v]){rs|=(g[u]&(~f[v]));} }assert((g[u]&rs)==rs);if(g[u]==rs)ck[bl[u]]=1; //ck=0 表示这个是不可被访问的//如果全部向内,就一定可以访问}for(int i=1;i<=num;i++){if(!in[i]&&!ck[i]){cout<<"NO\n";return;}}cout<<"YES\n";
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int stc=clock();int T;cin>>T;for(tst=1;tst<=T;tst++)solve();return 0;
}