STR[#6]

photo

首先，只用枚举能看到船沿的观察者（收缩法）

然后，处理出所有观察者的位置。看左右两个观察者能否合并在一起即可。

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=2e5+5;

int n, cl, cr; //m[0/1]：向左/右的差分标记 p：观察者位置

struct mark{

	int pos, v;

	mark(int x=0, int y=0){ pos=x; v=y; }

}m[2][maxn];

bool cmp(const mark &a, const mark &b){ return a.pos<b.pos; }

int p[maxn], cntp, l[maxn], r[maxn], a[maxn]; //l/r:这个观察者能看到多少个往左/往右的

int main(){

	scanf("%d", &n); int x, y, z, d;

	for (int i=1; i<=n; ++i){

		scanf("%d%d%d%d", &x, &y, &z, &d);

		if (y-x>2*z) continue;  //直接忽略不可能看见的船

		p[cntp++]=x+z; p[cntp++]=y-z;  //观察者的可能位置

		//在此区域内的观察者能看到向0/1行驶的这艘船

		if (d==-1){ m[0][cl++]=mark(y-z, 1), m[0][cl++]=mark(x+z+1, -1); }

		else{ m[1][cr++]=mark(y-z, 1), m[1][cr++]=mark(x+z+1, -1); }

	}

	sort(p, p+cntp); sort(m[0], m[0]+cl, cmp); sort(m[1], m[1]+cr, cmp);

	int t=0, now=0;

	for (int i=0; i<cntp; ++i){  //当前观察者能看到几艘向左的船

		while (m[0][t].pos<=p[i]&&t<cl) now+=m[0][t++].v;

		l[i]=now; }

	t=0; now=0;

	for (int i=0; i<cntp; ++i){  //当前观察者能看到几艘向右的船

		while (m[1][t].pos<=p[i]&&t<cr) now+=m[1][t++].v;

		r[i]=now; }

	a[0]=r[0]; int ans=0;  //a表示前缀最大值

	for (int i=1; i<cntp; ++i) a[i]=max(a[i-1], r[i]);

	//for (int i=0; i<cntp; ++i) printf("%d\n", a[i]);

	for (int i=1; i<cntp; ++i) ans=max(ans, l[i]+a[i-1]);  //左右合成

	printf("%d\n", ans);

	return 0;

}

graph

用\(f[S][j]\)，表示S集合分成j个连通块有多少种边集。为了去重，锁定一个点p，设\(S_p\subset S,p \in S_p\)，那么\(f[S][j]+=f[S-S_p][j-1]*f[S_p][1]\)。

#include <cstdio>

using namespace std;

#define popc __builtin_popcount

#define lowbit __builtin_ctz

typedef long long LL;

const int maxn=15, mod=1e9+9;

int n, m, k, pw2[maxn*maxn], G[maxn][maxn], in[1<<maxn];

LL f[1<<maxn][maxn];

int main(){

	pw2[0]=1;

	for (int i=1; i<maxn*maxn; ++i) pw2[i]=pw2[i-1]*2%mod;

	scanf("%d%d%d", &n, &m, &k); int x, y, v;

	for (int i=1; i<=m; ++i){

		scanf("%d%d", &x, &y); --x; --y; G[x][y]=G[y][x]=1; }

	for (int i=1; i<1<<n; ++i) if (popc(i)>1){

		v=lowbit(i);

		in[i]=in[i^(1<<v)];

		for (int j=0; j<n; ++j)

			if (G[v][j]&&(i&(1<<j))) ++in[i];

		//printf("%d %d %d %d\n", i, v, in[i^(1<<v)], in[i]);

	}

	for (int i=1; i<1<<n; ++i) if (popc(i)>1){

		f[i][1]=pw2[in[i]];

		for (int j=popc(i); j>1; --j){  //切成几个连通块

			int v=lowbit(i), k=i^(1<<v), r=i^(1<<v);

			do{  //枚举子连通块

				f[i][j]=(f[i][j]+f[1<<v|k][1]*f[r^k][j-1])%mod;

				k=k-1&r;

			}while(k!=r);

			f[i][1]-=f[i][j];

		}

		f[i][1]=f[i][1]%mod+(f[i][1]>>63&mod);

	} else f[i][1]=1;

	printf("%lld\n", f[(1<<n)-1][k]);

	return 0;

}