前缀单词
前缀进行排序处理如何就可以保证答案的正确性呢?比如前面有一个子集,既然有那个子集,那么就一定子集中不存在前缀,如此我来了一个新的变量,我如何证明那个子集中不含有我的前缀呢?一个很显然的结论,假如存在我的前缀,那么这个集合中的任何一个都不包含这个前缀,假如这个前缀不是最后面的那个集合.那么就会出现一个什么问题呢?很显然顺序是已经确定了的,我最后一个元素一定比出现前缀的那个集合要大,而且我肯定不能包含那个集合,也就是说,我一定在它结尾的时候就比它大,而它后面的那个包含这个前缀的就一定比最后一个元素小,如此就矛盾了...
可能文字有些看不明白举个栗子就好了,这个集合假设说包含的前缀是1234 而我最后一个元素一定是>1234且不是在第4位以后大于,而我现在的元素一定是在第4位以后大于..(排序的正确性证明)
有了排序的正确性证明,那么我们令f[0]=1(空集),f[i]表示到了第i个以i结尾的子集数量,然后答案就是对它们求和...
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=55;
string s[N];
long long f[N],ans;
int main()
{
int n;
cin>>n;
for(int i=0;i<=n;i++) f[i]=1;
for(int i=1;i<=n;i++) cin>>s[i];
sort(s+1,s+1+n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(s[i].find(s[j])) f[i]+=f[j];
}
}
for(int i=0;i<=n;i++) ans+=f[i];
cout<<ans<<endl;
return 0;
}lpt的小屋 文章被收录于专栏
我想要一份甜甜的爱情
投递三一重工等公司10个岗位