P6126 [JSOI2012]始祖鸟 题解

· · 题解

前言

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

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

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}。

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

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

  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 了，大家可以自己去推一下，看看自己输出的答案满不满足：

& 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);
}