hdu 1305 Immediate Decodability

深碍√TFBOYSˉ_ 2021-12-13 21:47 141阅读 0赞

[http://acm.hdu.edu.cn/showproblem.php?pid=1305][http_acm.hdu.edu.cn_showproblem.php_pid_1305]

题意：给你几个串，如果这些串中不存在一个串是另一个串的前缀，就说明这一组串是immediately decodable，反之则不是。

思路：先把所有串全部插入，然后来一个循环判断每个单词结尾处的cnt与1的大小关系，大于1的话说明这个串是某一个或者某几个串的前缀，那么就是not immediately decodable。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <algorithm>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    #include <cmath>
    #include <stack>
    
    using namespace std;
    
    const int maxn=2;
    
    struct node
    {
        int cnt;
        node *next[maxn];
        node()
        {
            cnt=0;
            for(int i=0;i<maxn;i++)
                next[i]=NULL;
        }
        ~node()
        {
            for(int i=0;i<maxn;i++)
            {
                if(next[i]!=NULL)
                    next[i]=NULL;
            }
        }
    };
    
    class Trie
    {
        public:
        node *root;
        Trie()
        {
            root=NULL;
        }
        void insert(char *s)
        {
            if(!root)
                root=new node();
            node *loca=root;
            for(int i=0;s[i];i++)
            {
                int id=s[i]-'0';
                if(loca->next[id]==NULL)
                    loca->next[id]=new node();
                loca->next[id]->cnt++;
                loca=loca->next[id];
            }
        }
        int search(char *s)
        {
            node *loca=root;
            for(int i=0;s[i];i++)
            {
                int id=s[i]-'0';
                if(loca->next[id]==NULL)
                    return 0;
                loca=loca->next[id];
            }
            return loca->cnt;
        }
    };
    
    int main()
    {
        char str[15][15];
        int line=0,cnt=1;
        while(~scanf("%s",str[line]))
        {
            Trie t;
            t.insert(str[line++]);
            while(scanf("%s",str[line]))
            {
                if(str[line][0]=='9') break;
                t.insert(str[line++]);
            }
            bool flg=false;
            for(int i=0;i<line;i++)
            {
                if(t.search(str[i])>1)
                {
                    flg=true;
                    break;
                }
            }
            printf("Set %d is ",cnt++);
            if(flg)
                printf("not ");
            printf("immediately decodable\n");
            line=0;
        }
        return 0;
    }

善待每一天，努力做好自己。

欢迎转载，注明出处。

转载于:https://www.cnblogs.com/RainingDays/archive/2013/05/09/3068758.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1305]: http://acm.hdu.edu.cn/showproblem.php?pid=1305
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211213/5cbb8c502d404bbab836720be35086be.png