UVA11362 Phone List 题解

题目链接：UVA11362 Phone List

题意：给定\(n\)个长度不超过\(10\)的数字串，判断是否有两个字符串\(A\)和\(B\),满足\(A\)是\(B\)的前缀，若有，输出NO，若没有，输出YES。

其实可以去建个 \(\tt{trie}\) 树然后dfs的

但是方便起见，直接sort就能过

时间复杂度 \(O(Qn^2)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+15)

int Q,n;
string s[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> Q;
    while(Q--)
    {
        cin >> n;
        for(int i=1; i<=n; i++)
            cin >> s[i];
        sort(s+1,s+1+n);
        int ok=0;
        for(int i=2; i<=n&&!ok; i++)
            if(s[i].find(s[i-1])==0)ok=1;
        cout << (ok?"NO\n":"YES\n");
    }
    return 0;
}