自动搬运

查看原文

来自洛谷，原作者为

	lenlen 一如既往，萬事勝意.

搬运于2025-08-24 22:17:42，当前版本为作者最后更新于2022-10-31 21:07:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

本蒟蒻刚刚学完高斯消元，拿这个题试试水。

推荐一下个人博客：高斯消元学习笔记。

Problem

题目大意：每一只始祖鸟要么在上游，要么在下游，而每一只始祖鸟认识一些始祖鸟，要求他在的地方他所认识的始祖鸟的个数为偶数。

数据范围： $n \leq 2000$。

Solution

我们考虑要满足第 $i$ 只始祖鸟需要满足什么条件，我们可以把每一只始祖鸟分为奇数个朋友和偶数个朋友 2 类，并且定义 $x_i=1$ 表示第 $i$ 只始祖鸟去了上游， $x_i=0$ 表示第 $i$ 只始祖鸟去了下游，并定义 $i$ 的朋友分别为 $a_{i,1},a_{i,2},\cdots,a_{i,k}$。

• 当第 $i$ 只始祖鸟的朋友数为偶数时，显然我们必须保证 $x_{a_{i,1}} \oplus x_{a_{i,2}} \oplus \cdots \oplus x_{a_{i,k}}=1$，这样无论 $i$ 去哪里都能满足条件。

• 当第 $i$ 只始祖鸟的朋友数为偶数时，显然我们必须保证 $x_{a_{i,1}} \oplus x_{a_{i,2}} \oplus \cdots \oplus x_{a_{i,k}}=1$ 且 $x_i=0$ 或者 $x_{a_{i,1}} \oplus x_{a_{i,2}} \oplus \cdots \oplus x_{a_{i,k}}=0$ 且 $x_i=1$，显然可以综合一下即 $x_{a_{i,1}} \oplus x_{a_{i,2}} \oplus \cdots \oplus x_{a_{i,k}} \oplus x_i=1$。

然后就是异或高斯消元的模板题了。

当然本题还有一些注意事项（也可能是只有我掉坑里了）：

1. 存这 $n$ 个线性异或函数的时候最好用 bitset，我用结构体和数组处理异或的时候超时了（记录：优化前 优化后）。

2. 这个题的话因为若有不唯一解也是可以随便输出一个解的，所以当遇到一个主元系数都为 0 时是跳过而非退出，并且假设前面已经处理了 $cnt$ 个主元，而现在正在处理第 $i$ 个主元，那么要从 $cnt+1$ 开始寻找是否有第 $i$ 位为 1 的方程。

对于第二点，在这个题里面，好像不考虑也能过，我提供一组 hack 数据：

6
3 4 5 6
2 1 6
0
2 3 6
0
0

貌似题解区的几位公布了全部源码的几篇题解都被 hack 了，大家可以自己去推一下，看看自己输出的答案满不满足：

$$\begin{cases} & x_1 \oplus x_4 \oplus x_5 \oplus x_6=1\\ & x_1 \oplus x_6=0\\ & x_3 \oplus x_6=0 \end{cases}$$

Code

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2732;
int n,m,x,ans;
bitset<N>a[N];
void gauss()
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int maax=cnt+1;//就是我所说的第二个点，如果写法不同说不定这个问题就自动考虑进去了
        for(int j=i+1;j<=n;j++) 
        if(a[j][i]>a[maax][i]) maax=j;
        swap(a[cnt+1],a[maax]);
        if(!a[i][i]) continue;
        cnt++;
        for(int j=1;j<=n;j++)
        if(a[j][i]==1&&i!=j)a[j]=a[j]^a[i];
    }
    if(cnt<n)
    {
        for(int i=1;i<=n;i++) 
        if(!a[i][i]&&a[i][n+1]) 
        {
            printf("Impossible\n");
            exit(0);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&m);
        if(m&1) a[i][n+1]=1,a[i][i]=1;
        while(m--) scanf("%d",&x),a[i][x]=1;
    }
    gauss();
    for(int i=1;i<=n;i++) if(a[i][n+1]) ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++) if(a[i][n+1]) printf("%d ",i);
}