3959

原题链接：P3959 乍一看，感觉像是一道图论的最短路这类的题，但是细想发现用图论似乎不可做。再看到这道题的数据范围 \(n<=12\)，立马就可以想到用状压 \(DP\)，因为数据范围很状压/。 思路 设计状态 首先来考虑状态的设计。如果按状压 \(DP\) 的套路来设的话，设 \(dp_{i,j ......

惊奇地发现我的赛时做法也可以通过转化一下计算式优化到 $O(n+m)$。或许也算是一种另解？ 首先，我们考虑把后手的决策视为图上的一个自环或一条边。对于每条边，你要对其选择其连接的一个点，且使得其满足两两不同。 对先手的决策，则意味着对这个点 / 边的额外代价，包括 * 无额外代价。（$|S\cap ......

有意思的题，做这题的时候也发现了不少有趣的东西~~虽然不会做~~。 考场上没有看出来建图。事实上本题复杂的性质基本决定它需要一步图论转化，而互不相同也是一个经典限制。可以得到如下建图转化：对于集合 $T_i$ 的两个数，在它们之间建立无向边，用定向表示选择，则我们需要给边定向使得每个点的入度不超过 ......