HDU 6208 The Dominator of Strings（stl）

超、凢脫俗 2022-06-08 07:57 103阅读 0赞

# The Dominator of Strings #

**Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)  
Total Submission(s): 2439 Accepted Submission(s): 879**

Problem Description

Here you have a set of strings. A dominator is a string of the set dominating all strings else. The string  S is dominated by  T if  S is a substring of  T.

Input

The input contains several test cases and the first line provides the total number of cases.  
For each test case, the first line contains an integer  N indicating the size of the set.  
Each of the following  N lines describes a string of the set in lowercase.  
The total length of strings in each case has the limit of  100000.  
The limit is 30MB for the input file.

Output

For each test case, output a dominator if exist, or No if not.

Sample Input

3
    10
    you
    better
    worse
    richer
    poorer
    sickness
    health
    death
    faithfulness
    youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
    5
    abc
    cde
    abcde
    abcde
    bcde
    3
    aaaaa
    aaaab
    aaaac

Sample Output

youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
    abcde
    No

Source

[2017 ACM/ICPC Asia Regional Qingdao Online][2017 ACM_ICPC Asia Regional Qingdao Online]

Recommend

liuyiding | We have carefully selected several similar problems for you: [6216][] [6215][] [6214][] [6213][] [6212][]

题解：

很水的一题，暴力就可以解决，直接取最长的作为模板串，如果和他等长的串和他不相同就不可以，然后其他的串要在那个串里面找得到。。。

比赛的时候我tm也是醉了，莫名其妙wa了好几遍，最后也没发现错，后来比完赛才知道错在了取消了cin和cout的同步以后用printf就会出错了。。。我把printf改成cout就ac了，我%@\#￥@\#￥@\#￥@，以后不能随便用取消同步了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    #define ll long long
    #define INF 100861111
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    struct node
    {
        string s;
    };
    node p[100005];
    string t;
    int main()
    {
        std::ios::sync_with_stdio(false);
        int test,i,j,n,num,maxx,tag;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d",&n);
            maxx=0;
            for(i=0;i<n;i++)
            {
                cin>>p[i].s;
                if(p[i].s.size()>maxx)
                {
                    maxx=p[i].s.size();
                    t=p[i].s;
                }
            }
            tag=1;
            for(i=0;i<n;i++)
            {
                if(p[i].s.size()==maxx)
                {
                    if(p[i].s!=t)
                    {
                        tag=0;
                        break;
                    }
                }
                else
                {
                    if(t.find(p[i].s)==string::npos)
                    {
                        tag=0;
                        break;
                    }
                }
            }
            if(tag)
                cout<<t<<endl;
            else
                cout<<"No"<<endl;
        }
        return 0;
    }

[2017 ACM_ICPC Asia Regional Qingdao Online]: http://acm.hdu.edu.cn/search.php?field=problem&key=2017+ACM%2FICPC+Asia+Regional+Qingdao+Online&source=1&searchmode=source
[6216]: http://acm.hdu.edu.cn/showproblem.php?pid=6216
[6215]: http://acm.hdu.edu.cn/showproblem.php?pid=6215
[6214]: http://acm.hdu.edu.cn/showproblem.php?pid=6214
[6213]: http://acm.hdu.edu.cn/showproblem.php?pid=6213
[6212]: http://acm.hdu.edu.cn/showproblem.php?pid=6212