前缀单词

前缀进行排序处理如何就可以保证答案的正确性呢?比如前面有一个子集,既然有那个子集,那么就一定子集中不存在前缀,如此我来了一个新的变量,我如何证明那个子集中不含有我的前缀呢?一个很显然的结论,假如存在我的前缀,那么这个集合中的任何一个都不包含这个前缀,假如这个前缀不是最后面的那个集合.那么就会出现一个什么问题呢?很显然顺序是已经确定了的,我最后一个元素一定比出现前缀的那个集合要大,而且我肯定不能包含那个集合,也就是说,我一定在它结尾的时候就比它大,而它后面的那个包含这个前缀的就一定比最后一个元素小,如此就矛盾了...
可能文字有些看不明白举个栗子就好了,这个集合假设说包含的前缀是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的小屋 文章被收录于专栏

我想要一份甜甜的爱情

全部评论

相关推荐

07-24 19:01
门头沟学院 Java
后天笔试,又要开始做题了
Sairus:明天10:00笔试
投递京东等公司10个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
07-10 14:08
已编辑
江西农业大学 Java
拒绝无效加班的小学生...:期望3k吗?java这辈子有了
点赞 评论 收藏
分享
07-23 14:04
东北大学 C++
既然这样,为什么不点击就送呢
牛马88号:因为你合适。但有很多笔试就挂了、通过了再排序的
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务