洛谷 GDOI 发现d≤8d \le 8d≤8，这仿佛在提示我们要暴力枚举xxx代表的是什么，注意到b,cb,cb,c和a,ca,ca,c就可以覆盖到xxx的所有情况，所以我们只要枚举xxx是AAA或BBB即可，时间复杂度2d2^d2d，我们把枚举出来的地图序列叫做MapMapMap 考虑这样编号，AAA对应[1,n][1,n][1,n]，BBB对应[n+1,2×n][n+1,2 \time...

洛谷 GDOI 首先，按照2−SAT2-SAT2−SAT问题的套路，我们要把这个转化成依赖性问题 又发现一只奶牛刚好投两次票，所以只要不满足奶牛的其中一次投票，就要满足另一次，这样就转化成了依赖性问题。 但是，这道题还要输出"?""?""?"，怎么搞 再看一眼数据范围1≤N≤10001 \le N \le 10001≤N≤1000，...

传送门 GDOI 根据2−SAT2-SAT2−SAT套路，我们要把这个问题转换成依赖性问题，即选择uuu，就必须选vvv。 这个也是非常好转化的，假设iii，jjj互相憎恶，因为每个党派都必须有一个代表，所以选择了iii就必须选择jjj所在的党派的另一人，同理，选择了jjj就必须选择iii所在党派的另一人。 123456789101112131415161718192021222324252...

对于x1...xnx_1 ... x_nx1​...xn​，考虑如下的mmm条限制： xix_ixi​为true/false或者xjx_jxj​为true/false 我们举个例子，如果要求的是xix_ixi​为true或者xjx_jxj​为false 那么如果xix_ixi​为false，xjx_jxj​就必须为true 反之，如果xjx_jxj​为true，xix_ixi​就必须为tru...