题解：P6873 [COCI2013-2014#6] FONT

题目传送门
首先，我们发现

1\le n \le 25

，可以爆搜每个字符串选与不选。但是如果我们在考虑“选”时遍历字符串的每个字符，复杂度最高为

\mathcal{O}(26^n)

，会 T 掉。
那么怎么办呢？
其实我们对于这

26

个字符并不需要记录字符的个数，只需要记录“这个字符有没有”即可。所以对于每个字符串，可以转化为一个

[0,2^{26}-1]

的值，这个值二进制的第

i

位表示“该字符串第

i

个字符有没有”。之后，在搜索时，如果我们考虑选这个字符串，只需要将状态按位或上这个字符串的值即可。复杂度为

\mathcal{O}(2^n)

。
code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=30,ed=67108863;//ed为2^26-1
int n,a[N],cnt;

void dfs(int x,int tot,int st)
{
	if(x==n+1)
	{
		if(st==ed) cnt++;
		return ;
	}
	dfs(x+1,tot,st);
	dfs(x+1,tot+1,st|a[x]);
	return ;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		string s="";
		char ch=0;
		while(!(ch>='a' and ch<='z')) ch=getchar();
		while(ch>='a' and ch<='z')
		{
			s+=ch;
			ch=getchar();
		}
		for(int j=0;j<26;j++)
		{
			bool flag=0;
			for(int k=0;k<s.size();k++)
				flag|=(s[k]-'a'==j);
			if(flag) a[i]+=(1<<j);
		}
	}
	dfs(1,0,0);
	cout<<cnt;
	return 0;
}

题解：P6873 [COCI2013-2014#6] FONT

文章操作

相关推荐

评论

题解：P6873 [COCI2013-2014#6] FONT