[CQOI2018] 解锁屏幕

[CQOI2018] 解锁屏幕

BZOJ
luogu
mdzz毒瘤卡常题,记搜硬是不让过...
设(f[i][s])表示当前位于点i,已经划到的点的集合为s的方案数
考虑转移的一个限制,当前点i转移到j的这条线上的点必须全部划过
考虑预处理这个(c[i][j])表示要从i划到j必须选中的点集
具体就(O(n^3))枚举判断三点共线即可
所以每次转移判断是否已经包含c[i][j]这个集合,对于1的个数>=4的状态加进ans

#define ri register int
#include<bits/stdc++.h>
using namespace std;
const int N=25,_=1048580,p=1e8+7;
const double eps=1e-7;
inline int re(){
    ri x=0,w=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*w;
}
int n,ans;
int x[N],y[N],f[N][_],c[N][N];
double dis[N][N];
inline void add(int&x,int y){x+=y;if(x>=p)x-=p;}
inline double D(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
inline int count(int s){
	ri cnt=0;for(;s;s^=(s&-s))++cnt;return cnt;
}
int main(){
    n=re();
    for(ri i=0;i<n;i++)
        x[i]=re(),y[i]=re();
    for(ri i=0;i<n;i++)
        for(ri j=i+1;j<n;j++){
            dis[i][j]=D(i,j);
            dis[j][i]=dis[i][j];
        }
    for(ri i=0;i<n;i++)
        for(ri j=i+1;j<n;j++){
            for(ri k=0;k<n;k++){
                if(k==i||k==j)continue;
                if(dis[i][k]+dis[k][j]-dis[i][j]<eps)
                    c[i][j]|=(1<<k);
            }
            c[j][i]=c[i][j];
        }
	for(ri i=0;i<n;i++)f[i][1<<i]=1;
	for(ri s=0;s<(1<<n);s++)
		for(ri i=0;i<n;i++){
			if(!f[i][s])continue;
			for(ri j=0;j<n;j++){
				if(s>>j&1)continue;
				if(s==(s|c[i][j]))
					add(f[j][s|(1<<j)],f[i][s]);
			}
			if(count(s)>3)add(ans,f[i][s]);
		}
	printf("%d
",ans);
    return 0;
}