点灯游戏应该很多人都在小时候頽过吧

反正我直到现在也不会

很明显一个灯最多只需要点一次

然后高斯消元

解完肯定剩自由元(就是那些全是0的行)

然后这些都爆搜

由于剩下的自由元不会太多

所以时间复杂度$O(能过)$

以上

1 #include
      
        2 #include
       
         3 using std::swap; 4 const int N=40; 5 template
        
         void read(tp &kk){ 6     tp ret=0,f=1;char ch=getchar(); 7     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();} 8     while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();} 9     kk=ret*f;10 }11 int n,a[N][N];12 13 14 void gauss()15 {16     for(int l=1;l<=n;l++)17     {18         int g=l;19         while(g<=n&&(!a[g][l])) g++;20         if(g>n) continue;21         if(l!=g)22             for(int i=l;i<=n+1;i++) swap(a[l][i],a[g][i]);23         for(int i=1;i<=n;i++)24         {25             if(a[i][l]&&i!=l)26             {27                 for(int j=l;j<=n+1;j++) a[i][j]^=a[l][j];28             }29         }30     }31 }32 33 int ans;34 void wtf(int l,int x)35 {36     if(x>ans) return;37     if(!l){ans=x;return;}38     if(a[l][l]) wtf(l-1,x+a[l][n+1]);39     else40     {41         if(a[l][n+1]) return;42         wtf(l-1,x);43         for(int i=l-1;i;i--) a[i][n+1]^=a[i][l];44         wtf(l-1,x+1);45         for(int i=l-1;i;i--) a[i][n+1]^=a[i][l];46     }47 }48 int m,xi,yi;49 int main()50 {51     read(n),read(m);52     for(int i=1;i<=n;i++) a[i][i]=a[i][n+1]=1;53     for(int i=1;i<=m;i++)54     {55         read(xi),read(yi);56         a[xi][yi]^=1,a[yi][xi]^=1;57     }58     gauss();59     ans=n;60     wtf(n,0);61     printf("%d\n",ans);62     return 0;63 }