NC202155. Prefix Code
描述
输入描述
The first line of the input gives the numbers of test cases, (). test cases follow.Each test case consists of one line with one integer (), the number of code words.
Then follows lines with one code word on each line. A code word is asequence of at most ten digits.
输出描述
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is "Yes" if the code is a prefix code, or "No" if not.
示例1
输入:
3 2 9 55 4 9 5 59 55 4 01 01 123 321
输出:
Case #1: Yes Case #2: No Case #3: No
C++(g++ 7.5.0) 解法, 执行用时: 343ms, 内存消耗: 740K, 提交时间: 2022-10-04 19:08:20
#include<iostream> #include<algorithm> using namespace std; int t,n,cnt; string s[10040]; bool check(int i,int j){ for(int x=0;x<s[i].length();x++) if(s[i][x]!=s[j][x]) return false; return true; } bool solve(){ cin>>n; for(int i=0,cur;i<n;i++) cin>>s[i]; sort(s,s+n); for(int i=1;i<n;i++) if(check(i-1,i)) return false; return true; } int main() { ios::sync_with_stdio(false); cin>>t; for(int i=1;i<=t;i++){ cout<<"Case #"<<i<<": "; if(solve()) cout<<"Yes"<<'\n'; else cout<<"No"<<'\n'; } return 0; }
C++ 解法, 执行用时: 4821ms, 内存消耗: 5968K, 提交时间: 2022-04-24 20:15:47
#include<bits/stdc++.h> #define maxn 10005 using namespace std; int n; string s[maxn]; void work(int t){ map<string,int> mp; int pd=0; int n;scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>s[i]; if(mp[s[i]]) pd=1; mp[s[i]]=1; } for(int i=1;i<=n;i++){ string now; for(int j=0;j<s[i].length()-1;j++){ now+=s[i][j]; if(mp[now]) pd=1; } } if(pd==1) printf("Case #%d: No\n",t); else printf("Case #%d: Yes\n",t); } int main() { int t; cin>>t; for(int i=1;i<=t;i++) work(i); }
Python3(3.5.2) 解法, 执行用时: 2102ms, 内存消耗: 5216K, 提交时间: 2020-02-16 14:34:50
def OK(words): words.sort() for i in range(len(words)-1): if words[i+1].startswith(words[i]): return False return True T = int(input()) for t in range(1, T+1): N = int(input()) words = [input() for n in range(N)] print("Case #%d: %s"%(t, "Yes" if OK(words) else "No"))