BZOJ 1130 [POI2008]POD Subdivision of Kingdom 状压

题意:链接方法:状压解析:N这么小的范围，看到就忍不住想要压一压- -！先想想对半分的方案数。大概500W吧挺小的。现在看我们的转移辣。如果O(n)的话是作死！所以如何降到O(1)呢？我们把每一个点的连向的点压成一个二进制数。然后转移我们就可以做到删去原来的加上新的。这个复杂度是O(1的个数)但是如果我们预处理出二进制数中1的个数，，那么转移就O(1)辣，这题就可以水过去啦注意:预处理的话我们只能处理1<<13范围内的，再往上半劈就好了。代码:;int n,m;int edge[N];int cnt[(1<<13)+10];int s1,s2;int ans,print;void init(){for(int i=0;i<=(1<<13);i++){for(int j=13;j>=0;j–){if(i&(1<<j))cnt[i]++;}}}int get_num(int x){return cnt[x>>13]+cnt[(x-((x>>13)<<13))];}void dfs(int pos,int all,int sum){if(all==n/2){if(sum<ans){ans=sum;print=s1;}return;}for(int i=pos+1;i<=n;i++){int tmp=get_num(edge[i]|s1);int tmp2=get_num(edge[i]|s2);s1|=(1<<(i-1));s2^=(1<<(i-1));dfs(i,all+1,sum-tmp2+tmp);s1^=(1<<(i-1));s2|=(1<<(i-1));}}int main(){scanf(“%d%d”,&n,&m);s1=0,ans=0x3f3f3f3f,s2=(1<<n)-1;for(int i=1;i<=m;i++){int x,y;scanf(“%d%d”,&x,&y);edge[x]|=(1<<(y-1));edge[y]|=(1<<(x-1));}init();dfs(0,0,0);for(int i=1;i<=n;i++){if(print&(1<<(i-1))){printf(“%d “,i);}}puts(“”);}

生气是拿别人做错的事来惩罚自己