首页 > 代码库 > BZOJ3806: Neerc2011 Dictionary Size
BZOJ3806: Neerc2011 Dictionary Size
题解：
这题搞得我真是酸（dan）爽（teng）
原来一直不会，一定会用到什么神奇的东西。因为重复的不知道如何计算。
今天中午睡起来忽然想到好像可以在正trie上故意走无出边，因为这样就保证了这次统计的所有字符串在它的孩子都不会再次被统计到。
然后感觉这题就解了。
然后和别人的程序对拍发现居然一直少计算了什么！去多了？
然后发现没有算上trie上的节点，前面只考虑了在trie后面加字符串。。。
然后发现好像正反都得特判，然后发现又有重复的！！！这怎么搞！！！
感觉AC无望便去颓了两集火影。。。
看完了乱搞了一下居然就A了。。。我真的是乱搞的T_T现在还不知道为什么能A。。。
int n,m,tot,a[maxn][26],s[2][26];char st[10001][45];bool b[26];int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read(); for1(k,n) { scanf("%s",st[k]);m=strlen(st[k]); int now=0; for0(i,m-1) { int j=st[k][i]-‘a‘; if(!a[now][j])a[now][j]=++tot,s[0][j]--; now=a[now][j]; } b[(int)(st[k][m-1]-‘a‘)]=1; } for0(i,25)s[0][i]+=tot; ll ans=0; for0(i,tot)for0(j,25)if(a[i][j]&&b[j])ans++; memset(b,0,sizeof(b)); memset(a,0,sizeof(a));tot=0; for1(k,n) { int now=0;m=strlen(st[k]); for3(i,m-1,0) { int j=st[k][i]-‘a‘; if(!a[now][j])a[now][j]=++tot,s[1][j]++; now=a[now][j]; } b[(int)(st[k][0]-‘a‘)]=1; } for1(i,tot)for0(j,25)if(a[i][j]&&b[j])ans++; memset(b,0,sizeof(b)); for1(i,n)if(strlen(st[i])==1)b[(int)(st[i][0]-‘a‘)]=1; for0(i,25)ans+=b[i]; for0(i,25)ans+=(ll)s[0][i]*s[1][i]; cout<<ans<<endl; return 0;}
BZOJ3806: Neerc2011 Dictionary Size
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。