状态压缩

　　为什么这一篇访问量这么高啊QAQ

　　还是不懂鸭，明明没啥好题，写的也一般...不如顺便引个流，要不要康康蛤蛤日报？

　　状态压缩是个很神奇的东西，可以把复杂的状态压缩到一个简单的数来保存。类似于哈希？从某个课件上看到了这种总结感觉很不错：当状态维数很多，但总量很少时，可以将状态压缩为一个数来记录。以前以为状态压缩只能是dp，事实上配合别的算法也不错。

状压搜索：

　　关灯问题II https://www.luogu.org/problemnew/show/P2622

　　题意概述：n盏灯，m种操作，可以使每个灯的状态出现改变，问最少的操作数。

　　N<=10,所以可以用二进制保存目前有哪些灯是开的，然后就可以广搜啦。

# include <cstdio>
# include <iostream>

using namespace std;

int n,m,ans=0,l[101][11];
int no,ne,q[2000],h=1,t=2;
int vis[2000],f;

void bfs()
{
    while(h<t)
    {
        no=q[h++];
        for (int i=1;i<=m;i++)
        {
            ne=no;
            for (int j=0;j<n;j++)
            {
                if(l[i][j]==1)
                    if(ne&(1<<j)) ne-=(1<<j);
                if(l[i][j]==-1)
                    ne=ne|(1<<j);                    
            }
            if(vis[ne]==-1)
            {
                q[t++]=ne;
                vis[ne]=vis[no]+1;
            }
            if(ne==0)
            {
                f=true;
                ans=vis[ne];
                return ;
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<=1999;i++)
      vis[i]=-1;
    no=(1<<n)-1;
    for (int i=1;i<=m;i++)
        for (int j=0;j<n;j++)
            scanf("%d",&l[i][j]);
    q[h]=no;
    vis[no]=0;
    bfs();
    if(f) printf("%d",ans);
    else  printf("-1");
    return 0;
}

View Code

　　八数码难题：https://www.luogu.org/problemnew/show/P1379

　　题意概述：给定放好了八个棋子一个空格的棋盘，每次可以移动空格，求移动到目标棋盘的最少步数。

　　这真是个好题，在搜索-1，搜索-2中还会有进一步实现。

　　BFS！怎么保存棋盘,康拓展开。虽然不是一般的01状压，但是却符合维数很多总量较少的定义。不过对于这道题不用康拓展开，因为只有九个数字，所以暴力拽成一条链也是可以的。（也可以用set）。

# include <iostream>
# include <set>
# include <queue>
# include <cstdio>

using namespace std;

const int dx[]={-1,0,0,1};
const int dy[]={0,1,-1,0};

int x,dream=123804765;
int ans=-1;
int q[10000000]={0};
int ql[10000000]={0};
set<int> s;

int A()
{
    int head=0,tail=1;
    while (1)
    {
        int il=0,jl=0,n[3][3],now;
        now=q[++head];
        if(now==dream)
            return ql[head];
        for (register int i=2;i>=0;i--)
              for (register int j=2;j>=0;j--)
            {
                  if(now%10==0) il=i,jl=j;
                  n[i][j]=now%10;
                  now=now/10;
            }
        for (register int i=0;i<4;i++)
        {
            int xx=il+dx[i];
            int yy=jl+dy[i];
            if(xx>=0&&xx<=2&&yy>=0&&yy<=2)
            {
                int nn[3][3];
                for (register int ii=0;ii<3;ii++)
                  for (register int jj=0;jj<3;jj++) nn[ii][jj]=n[ii][jj];
                swap(nn[il][jl],nn[xx][yy]);
                now=nn[0][0]*100000000+nn[0][1]*10000000+nn[0][2]*1000000+nn[1][0]*100000+nn[1][1]*10000+nn[1][2]*1000+nn[2][0]*100+nn[2][1]*10+nn[2][2];
                if(s.find(now)!=s.end()) 
                { continue; }
                else
                {
                    s.insert(now);
                    q[++tail]=now;
                    ql[tail]=ql[head]+1;
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&x);
    q[1]=x;
    ql[1]=0;
    s.insert(x);
    ans=A();
    printf("%d",ans);
    return 0;
}

View Code

　　宝藏：https://www.luogu.org/problemnew/show/P3959

　　题意概述:NOIP 2017 D2T2。

　　看到$n<=12$感觉还是比较好的，应该就是搜索或者状压了，思索一下觉得状压搜索也是很可行的，而且非常可做，于是飞快的写了一个交上去：70；其实我觉得70很不错啦，下面是代码：

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # define R register int
 5 
 6 struct edge
 7 {
 8     int too,nex,co;
 9 }g[1000];
10 int h,n,m,x,y,v,firs[15],ans=0,k[15];
11 int G[15][15];
12 
13 int min(int a,int b)
14 {
15     if(a<b) return a;
16     return b;
17 }
18 
19 void add (int x,int y,int v)
20 {
21     g[++h].too=y;
22     g[h].co=v;
23     g[h].nex=firs[x];
24     firs[x]=h;
25 }
26 
27 void dfs(int co,int q)
28 {
29     if(co>=ans) return ;
30     if(q==(1<<n)-1)
31     {
32         ans=min(ans,co);
33         return ;
34     }
35     int a;
36     for (R i=1;i<=n;++i)
37     {
38         if(!(q&(1<<(i-1)))) continue;
39         for (R j=firs[i];j;j=g[j].nex)
40         {
41             a=g[j].too;
42             if(q&(1<<(a-1))) continue;
43             k[a]=k[i]+1;
44             dfs(co+k[i]*g[j].co,q|(1<<(a-1)));    
45         }
46     }
47 }
48 
49 int main()
50 {
51     memset(G,127,sizeof(G));
52     ans=G[1][1];
53     scanf("%d%d",&n,&m);
54     for (R i=1;i<=m;++i)
55     {
56         scanf("%d%d%d",&x,&y,&v);
57         G[x][y]=G[y][x]=min(G[x][y],v);
58     }
59     for (R i=1;i<=n;++i)
60         for (R j=1;j<=n;++j)
61             if(G[i][j]<=500000) add(i,j,G[i][j]);
62     for (R i=1;i<=n;++i)
63     {
64         memset(k,0,sizeof(k));
65         k[i]=1;
66         dfs(0,1<<(i-1));
67     }
68     printf("%d",ans);
69     return 0;
70 }

宝藏(70pts)

　　进行一番神奇的记忆化之后A掉了：dp[i]表示生成树中包含i这个集合的最小花费。但是这个不大对啊qwq 虽然并不能举出反例来，但是感性理解觉得不大对。

 1 // luogu-judger-enable-o2
 2 # include <cstdio>
 3 # include <iostream>
 4 # include <cstring>
 5 # define R register int
 6 
 7 struct edge
 8 {
 9     int too,nex,co;
10 }g[1000];
11 int h,n,m,x,y,v,firs[15],ans=0,k[15];
12 int G[15][15];
13 int vis[100000];
14 long long timee=0;
15 
16 int min(int a,int b)
17 {
18     if(a<b) return a;
19     return b;
20 }
21 
22 void add (int x,int y,int v)
23 {
24     g[++h].too=y;
25     g[h].co=v;
26     g[h].nex=firs[x];
27     firs[x]=h;
28 }
29 
30 void dfs(int co,int q)
31 {
32     if(co>=ans) return ;
33     if(q==(1<<n)-1)
34     {
35         ans=min(ans,co);
36         return ;
37     }
38     if(timee>=10000000) return ;
39     int a;
40     if(n>8)
41     {
42         if(vis[q]<=co) return ;
43         vis[q]=co;
44     }
45     for (R i=1;i<=n;++i)
46     {
47         if(!(q&(1<<(i-1)))) continue;
48         for (R j=firs[i];j;j=g[j].nex)
49         {
50             a=g[j].too;
51             
52             timee++;
53             if(timee>=10000000) return ;
54             
55             if(q&(1<<(a-1))) continue;
56             k[a]=k[i]+1;
57             dfs(co+k[i]*g[j].co,q|(1<<(a-1)));    
58         }
59     }
60 }
61 
62 int main()
63 {
64     memset(G,127,sizeof(G));
65     ans=G[1][1];
66     scanf("%d%d",&n,&m);
67     for (R i=1;i<=m;++i)
68     {
69         scanf("%d%d%d",&x,&y,&v);
70         G[x][y]=G[y][x]=min(G[x][y],v);
71     }
72     for (R i=1;i<=n;++i)
73         for (R j=1;j<=n;++j)
74             if(G[i][j]<=500000) add(i,j,G[i][j]);
75     memset(vis,127,sizeof(vis));
76     for (R i=1;i<=n;++i)
77     {
78         memset(k,0,sizeof(k));
79         k[i]=1;
80         dfs(0,1<<(i-1));
81     }
82     printf("%d",ans);
83     return 0;
84 }

宝藏 (100pts)

状压线段树：

　　色板问题 https://www.luogu.org/problemnew/show/P1558

　　题意概述：在序列上进行区间覆盖和查询，查询这段区间的元素种类。

　　看起来很像SDOI某一年的HH的项链，但是这道题支持修改就很不一样了。注意到元素种类非常少，最多才30种，所以可以进行状态压缩，update的时候可以或一下，pushdown的时候直接覆盖。

# include <cstdio>
# include <iostream>
# define R register int
# define nl n<<1
# define nr n<<1|1

using namespace std;

const int maxn=100009;
int xx,cc,n,t,o,l,r,co,s;
long long c[maxn<<2],delta[maxn<<2],ans;
char ch;

void build(int n,int l,int r)
{
    delta[n]=-1;
    if(l==r)
    {
        c[n]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(nl,l,mid);
    build(nr,mid+1,r);
    c[n]=c[nl]|c[nr];
}

void pushdown(int n,int l,int r)
{
    int x=delta[n];
    delta[n]=-1;
    delta[nl]=x;
    delta[nr]=x;
    c[nl]=(1<<(x-1));
    c[nr]=(1<<(x-1));
    c[n]=c[nl]|c[nr];
}

void chan (int n,int l,int r,int ll,int rr,int co)
{
    if(ll<=l&&r<=rr)
    {
        delta[n]=co;
        c[n]=(1<<(co-1));
        return ;
    }
    if(delta[n]!=-1) pushdown(n,l,r);
    int mid=(l+r)>>1;
    if(ll<=mid)chan(nl,l,mid,ll,rr,co);
    if(rr>mid)chan(nr,mid+1,r,ll,rr,co);
    c[n]=c[nl]|c[nr];
}

long long ask (int n,int l,int r,int ll,int rr)
{
    if(ll<=l&&r<=rr)
        return c[n];
    if(delta[n]!=-1) pushdown(n,l,r);
    int mid=(l+r)>>1;
    long long ans=0;
    if(ll<=mid) ans=ans|ask(nl,l,mid,ll,rr);
    if(rr>mid)  ans=ans|ask(nr,mid+1,r,ll,rr);
    return ans;
}

int read()
{
    xx=0;
    cc=getchar();
    while (!isdigit(cc)) cc=getchar();
    while (isdigit(cc))  xx=(xx<<3)+(xx<<1)+(cc^48),cc=getchar();
    return xx;
}

int main()
{
    n=read(),t=read(),o=read();
    build(1,1,n);
    for (R i=1;i<=o;i++)
    {
        ch=getchar();    
        while (ch!='P'&&ch!='C') ch=getchar();
        if(ch=='C')
        {
            l=read(),r=read(),co=read();
            if(l>r) swap(l,r);
            chan(1,1,n,l,r,co);    
        }
        else
        {
            l=read(),r=read();
            if(l>r) swap(l,r);
            ans=ask(1,1,n,l,r);
            s=0;
            for (int i=0;i<=t;i++)
                if (ans&(1<<i)) s++;
            printf("%d
",s);
        }
    }
    return 0;
}

View Code

状压DP：

　　玉米田：https://www.luogu.org/problemnew/show/P1879

　　题意概述：从给定的01网格中选出一些1点，且四不连通，求方案数。

　　突破点依旧在mn的范围很小，可以考虑按行转移（当然也可以按列），每一行的总状态数应从0循环到(1<<n)-1，按行转移时注意判断一下此状态是否合法，且与上一行的状态是否冲突。可以预处理每一行的所有合法状态，循环时外层循环本行状态，一旦不合法就剪掉，对于这道题可以优化到0ms。 O(2^(2*n)*n)去R2逛了一圈后深刻的认识到数据范围加0的恐怖，于是手动给这道题加0。然而加1个零我就不会做了，毕竟复杂度上界会爆炸。然而这道题的复杂度必然是非常不准的，因为每一层的状态不可能有2^n种那么多。

# include <cstdio>
# include <iostream>
# define R register int

using namespace std;

const int Mod=100000000;
int m,n;
int g[13][13];
long long dp[13][5000];
bool ca[13][5000];

inline bool check(int h,int x)
{
    for (R i=1;i<=n;i++)
        if((x&(1<<(i-1)))&&g[h][i]==0)
            return false;
    for (R i=1;i<n;i++)
        if((x&(1<<(i-1)))&&(x&(1<<i)))
            return false;
    return true;
}

int main()
{
    scanf("%d%d",&m,&n);
    for (R i=1;i<=m;i++)
        for (R j=n;j>=1;j--)
            scanf("%d",&g[i][j]);
    for (R i=1;i<=m;i++)
        for (R j=0;j<(1<<n);j++)
        {
            ca[i][j]=check(i,j);
            if(ca[i][j]&&i==1) dp[i][j]=1;
        }
    for (R i=2;i<=m;i++)
        for (R no=0;no<(1<<n);no++)
        {
            if(!ca[i][no]) continue;
            for (R j=0;j<(1<<n);j++)
            {
                if(no&j) continue;
                dp[i][no]=(dp[i][no]+dp[i-1][j])%Mod;
            }
        }
    long long ans=0;
    for (R i=0;i<(1<<n);i++)
        ans=(ans+dp[m][i])%Mod;
    printf("%lld",ans%Mod);
    return 0;
}

View Code

　　互不侵犯：https://www.luogu.org/problemnew/show/P1896

　　题意概述：在n*n的网格中选出k个点，使得任意两点间八不连通。

　　感觉和上一题很像，再加一维保存下目前有几个国王，判断时左移或一次，右移或一次，不动再或一次就可以了。

　　又到了愉快的加0时间，对于状压dp我已经放弃加0了，如果没有新的思路其实很难再优化，现在觉得能多+1几次已经很是进步了，而且题解也没有特别的思路，优化一下常数的话或许能快一点。其实这道题也可以跑很大的数据，因为它的输入量非常小，近乎于输入n输出答案的题目，于是自然可以想到。。。打表！慢慢跑出答案存个表的话差不多可以加2个零呢！

# include <cstdio>
# include <iostream>
# define R register int

using namespace std;

int s=0,n,k,mn,aa;
long long S=0;
long long dp[10][1000][100];
bool ca[1000];

inline int Hoone(int x)
{
    s=0;
    for (R i=1;i<=n;i++)
        if(x&(1<<(i-1))) s++;
    return s;
}

inline bool check(int x)
{
    for (R i=1;i<n;i++)
        if((x&(1<<(i-1)))&&(x&(1<<i)))    return false;
    return true;
}

int main()
{
    scanf("%d%d",&n,&k);
    mn=(1<<n)-1;
    for (R j=0;j<=mn;j++)
        {
            if(check(j)) ca[j]=true;
            if(ca[j]) dp[1][j][Hoone(j)]=1;                
        }
    for (R i=2;i<=n;i++)
        for (R no=0;no<=mn;no++)
        {
            if(ca[no]==false) continue;
            for (R j=0;j<=mn;j++)
                for (R h=0;h<=k;h++)
                {
                    if(dp[i-1][j][h]==0) continue;
                    if((no<<1)&j) continue;
                    if(no&j)      continue;
                    if(no&(j<<1)) continue;
                    aa=h+Hoone(no);
                    if(aa>k)       continue;
                    dp[i][no][aa]+=dp[i-1][j][h];
                }
        }
    for (R no=0;no<=mn;no++)
        S+=dp[n][no][k];
    printf("%lld",S);
    return 0;
}

View Code

　　选数游戏：https://www.luogu.org/problemnew/show/P1123

　　题意概述：在网格中选出一些数，使其八不连通且和最大。

　　这道题的数据范围很小，正解是搜索，写状压有炫技的嫌疑。。。主要还是想练一下状压。首先预处理出每一行的合法情况，再处理一下第一行的答案，按行转移即可。然而只有一行可情况不要忘了，ans要从预处理第一行时就开始统计答案。。。

# include <cstdio>
# include <iostream>
# include <cstring>

using namespace std;

int T;
int n,m,ans=0;
int a[7][7];
int vis[7][70];
int dp[7][70];

void check(int i,int j)
{
    if((j<<1)&j) 
    {
        vis[i][j]=-1;
        return ;
    }
    if((j>>1)&j)
    {
        vis[i][j]=-1;
        return ;
    }
    for (int x=1;x<=m;x++)
        if(j&(1<<(x-1))) vis[i][j]+=a[i][x];
}

int main()
{
    scanf("%d",&T);
    while (T)
    {
        ans=0;
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        for (int i=1;i<=n;i++)
            for (int j=0;j<(1<<m);j++)
                check(i,j);
        m=(1<<m)-1;
        for (int i=0;i<=m;i++)
        {
            dp[1][i]=vis[1][i];
            ans=max(ans,dp[1][i]);
        }
        for (int i=2;i<=n;i++)
            for (int j=0;j<=m;j++)
                for (int k=0;k<=m;k++)
                {
                    if(j&k) continue;
                    if((j<<1)&k) continue;
                    if((j>>1)&k) continue;
                    if(vis[i][j]==-1) continue;
                    if(vis[i-1][k]==-1) continue;
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+vis[i][j]);
                    ans=max(ans,dp[i][j]);
                }
        printf("%d
",ans);
        T--;
    }
    return 0;
}

选数游戏

2018.8.8：今天老师让提交一下近期做的dp题，结果发现最近做的全是dp题，咕咕咕。

　　愤怒的小鸟：https://www.luogu.org/problemnew/show/P2831

　　题意概述：从原点发射小鸟打n只猪，求最小的小鸟数量。(n<=18)

　　其实这题还是比较好想的，n<=18，几乎可以肯定是状压或者搜索，$18!$看起来有点大，但是$2^{18}$好像海星，所以就状压。

　　设$dp[x]$表示打掉x这个集合所需的最小小鸟数量，考虑转移。抛物线的数量是无限的，但是有的抛物线显然非常不优，只打一只猪一定可以用一只小鸟，而且两点无法确定一条抛物线，所以干脆预处理出来：$dp[1<<(i-1]=1$，剩下的抛物线就至少可以打两只猪了，枚举这两只猪求出抛物线解析式，再看看其他那些猪可以被这一条抛物线一起打到，就找出了所有有用的抛物线。感觉dp并不是非常好写，所以就写了一个记忆化搜索，顺便学了一个$n^3$枚举子集的方法，愉快的交上去，结果又WA又T，这真是非常伤心。后来发现是卡精度了，就改了一下。改到75之后发现不再是精度问题了。冷静分析，发现是预处理的问题。比如说有一条抛物线是111101,但是这次的转移只需要100101，这个状态反而被算成了2条抛物线，其实是不对的，于是又对每条抛物线进行了枚举子集，果然不再错了，(但是T了)。这时候我不得不承认这个做法虽然看起来精妙，时间复杂度却不对，使用递推可能还好一点。至此，$O(2^n*n^3)$的做法正式宣布破产。

　　看到讨论区有人说爆搜都比这个快，放弃梦想写了一个大爆搜，然而真的过了，而且非常非常快，原来要跑4.5s的数据现在...只要4ms？搜索的复杂度果然玄学。后来仔细想一想发现并不玄学，在最坏的情况下一共要搜索$2^n$种状态，而对于每种状态可以确定一个抛物线上的点，再枚举一个，所以总复杂度的上界就是$O(2^n*n)$，然后也再加上一点点玄学，自然就非常快了。

 1 // luogu-judger-enable-o2
 2 # include <cstdio>
 3 # include <iostream>
 4 # include <cstring>
 5 # include <cmath>
 6 # define R register int
 7 
 8 using namespace std;
 9 
10 double eps=0.000001;
11 int T,n,m,s;
12 int dp[302144];
13 bool vis[302144];
14 double x[20],a,b;
15 double y[20];
16 
17 void solve (int i,int j)
18 {
19     a=(y[i]*x[j]-y[j]*x[i])/(x[i]*x[i]*x[j]-x[j]*x[j]*x[i]);
20     b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[j]*x[i]*x[i]);}
21 
22 bool xd (double a,double b)
23 {
24     double c=a-b;
25     if(c<0) c=-c;
26     return c<(1e-6);
27 }
28 
29 int dfs (int x)
30 {
31     if(vis[x]) return dp[x];
32     int ans=dp[x];
33     vis[x]=true;
34     for(R t=x;t;t=(t-1)&x)
35     {
36         if(ans==1) break;
37         ans=min(ans,dfs(t)+dfs(x-t));
38     }
39     dp[x]=ans;
40     return ans;
41 }
42 
43 int main()
44 {
45     scanf("%d",&T);
46     while (T--)
47     {
48         scanf("%d%d",&n,&m);
49         memset(dp,127,sizeof(dp));
50         memset(vis,0,sizeof(vis));
51         dp[0]=0;
52         for (R i=1;i<=n;++i)
53             scanf("%lf%lf",&x[i],&y[i]);
54         for (R i=1;i<=n;++i)
55             dp[1<<(i-1)]=1,vis[1<<(i-1)]=1;
56         for (R i=1;i<=n;++i)
57             for (R j=1;j<=n;++j)
58             {
59                 if(i==j) continue;
60                 s=0;
61                 if(xd(x[i],x[j])) continue;
62                 solve(i,j);
63                 if(a>(-1e-6))
64                     continue;
65                 for (R k=1;k<=n;++k)
66                     if(xd(x[k]*x[k]*a+x[k]*b,y[k])) 
67                         s|=(1<<(k-1));
68                 for (int t=s;t;t=(t-1)&s)
69                     vis[t]=true,dp[t]=1;
70             }
71         printf("%d
",dfs((1<<n)-1));
72     }
73     return 0;
74 }

愤怒的小鸟_状压dp

 1 // luogu-judger-enable-o2
 2 # include <cstdio>
 3 # include <iostream>
 4 # include <cstring>
 5 # include <cmath>
 6 # define R register int
 7 # define eps 0.000001
 8 
 9 int T,n,m,s,fans;
10 int g[20][20];
11 int dp[262244];
12 double x[20],a,b;
13 double y[20];
14 
15 using namespace std;
16 
17 inline void solve (int i,int j)
18 {
19     a=(y[i]*x[j]-y[j]*x[i])/(x[i]*x[i]*x[j]-x[j]*x[j]*x[i]);
20     b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[j]*x[i]*x[i]);
21 }
22 
23 inline bool xd (double a,double b)
24 {
25     double c=a-b;
26     if(c<0) c=-c;
27     return c<eps;
28 }
29 
30 int logg (int x)
31 {
32     int a=1;
33     while (x!=(1<<(a-1)))
34         a++;
35     return a;
36 }
37  
38 inline void dfs (int x,int ans)
39 {
40     if(dp[x]<=ans) return ;
41     dp[x]=ans;
42     if(ans>=fans) return;
43     int q=(1<<n)-1,b=q-x;
44     if(!b)
45     {
46         fans=min(ans,fans);
47         dp[q]=fans;
48         return ;
49     }
50     int i=b&(-b);
51     i=logg(i);
52     for (int j=1;j<=n;++j)
53         dfs(x|g[i][j],ans+1);
54 }
55 
56 int main()
57 {
58     scanf("%d",&T);
59     while (T--)
60     {
61         scanf("%d%d",&n,&m);
62         memset(g,0,sizeof(g));
63         memset(dp,127,sizeof(dp));
64         for (R i=1;i<=n;++i)
65             scanf("%lf%lf",&x[i],&y[i]);
66         for (R i=1;i<=n;++i)
67             g[i][i]=1<<(i-1);
68         for (R i=1;i<=n;++i)
69             for (R j=i;j<=n;++j)
70             {
71                 if(i==j) continue;
72                 s=0;
73                 if(xd(x[i],x[j])) continue;
74                 solve(i,j);
75                 if(a>(-eps))
76                     continue;
77                 for (R k=1;k<=n;++k)
78                     if(xd(x[k]*x[k]*a+x[k]*b,y[k])) 
79                         s|=(1<<(k-1));
80                 g[i][j]=g[j][i]=s;
81             }
82         fans=1000;
83         dfs(0,0);
84         printf("%d
",fans);
85     }
86     
87     return 0;
88 }

愤怒的小鸟_搜索

1 for(R t=x;t;t=(t-1)&x) （枚举子集）

　　NOIP2018后补充：状态压缩太可怕了，我D2死磕T2的状压做法（显然根本不对），导致全面崩盘。

　　有的同学说我一直不更博，其实只是更到老文章的后面了。--2019.3.29

　　按位或：https://www.luogu.org/problemnew/show/P3175

　　题意概述：刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行或操作。选择数字i的概率是 $p_i$。保证 $0<=p_i<=1$，$sum p_i=1$问期望多少秒后，你手上的数字变成 $2^n-1$。(其实这就是抄了题面并加上了latex.)

　　今天看了看luogu智推：多项式，多项式，数据机构，多项式，“按位或”；那就看看这道没见过的题目吧。

　　哇luogu竟然推了一道看起来很不错的状压dp给我，好良心。好的，那我们按照套路，设 $dp_i$ 表示当前状态为 $i$ 时期望还要走几步才能结束，边界情况显然，转移的话列个方程就好了(有可能转移到自己) $dp_i=sum_{j}f(j)dp(i|j)+1$.嗯嗯，这样就做完了，看看数据范围吧...n<=20 ？可是这个做法是 $4^n$，好没有前途啊。得了30.点开题解想看看有什么神奇优化，结果：“min-max容斥+fwt”...原来luogu是觉得“fwt”和“fft”念起来很像才给我推这题的吗?

 1 # include <cstdio>
 2 # include <iostream>
 3 # define R register int
 4 
 5 using namespace std;
 6 
 7 const int maxn=(1<<20)+5;
 8 const double eps=1e-10;
 9 int n;
10 double f[maxn],dp[maxn],vis[40];
11 
12 int main()
13 {
14     scanf("%d",&n);
15     for (R i=0;i<(1<<n);++i)
16     {
17         scanf("%lf",&f[i]);
18         for (R j=0;j<n;++j)
19             if(i&(1<<j)) vis[j]+=f[i];
20     }
21     for (R i=0;i<n;++i)
22         if(vis[i]<eps) { puts("INF"); return 0; }
23     for (R i=(1<<n)-2;i>=0;--i)
24     {
25         double t1=0,t2=0;
26         for (R j=0;j<(1<<n);++j)
27         {
28             if((j|i)!=i) t1+=f[j]*dp[j|i];
29             else t2+=f[j];
30         }
31         dp[i]=(t1+1)/(1-t2);
32     }
33     printf("%.10lf",dp[0]);
34     return 0;
35 }

按位或 (30pts)

　　正解是min-max容斥，虽然我后来学会了，但是考虑到这篇文章的标题，就只粘一个代码吧。

 1 // luogu-judger-enable-o2
 2 # include <cstdio>
 3 # include <iostream>
 4 # define R register int
 5 
 6 using namespace std;
 7 
 8 const int maxn=(1<<20)+5;
 9 const double eps=1e-10;
10 int n,f[maxn]; //容斥系数 
11 double p[maxn],vis[40],g[maxn];
12 
13 int cal (int x)
14 {
15     int ans=0;
16     for (R i=0;i<n;++i) if(x&(1<<i)) ans++;
17     return ans;
18 }
19 
20 int main()
21 {
22     scanf("%d",&n);
23     for (R i=0;i<(1<<n);++i)
24     {
25         f[i]=cal(i);
26         if(f[i]%2) f[i]=1;
27         else f[i]=-1;
28     }
29     for (R i=0;i<(1<<n);++i)
30     {
31         scanf("%lf",&p[i]);
32         for (R j=0;j<n;++j)
33             if(i&(1<<j)) vis[j]+=p[i];
34     }
35     for (R i=0;i<n;++i)
36         for (R j=0;j<(1<<n);++j)
37             if(j&(1<<i)) p[j]+=p[j^(1<<i)];
38     for (R i=0;i<n;++i)
39         if(vis[i]<eps) { puts("INF"); return 0; }
40     for (R i=1;i<(1<<n);++i)
41         g[i]=1/(1-p[((1<<n)-1)^i]);
42     double ans=0;
43     for (R i=0;i<(1<<n);++i)
44         ans+=f[i]*g[i];
45     printf("%.10lf",ans);
46     return 0;
47 }

按位或

---shzr