【Codeforces Round #434 (Div. 1) B】Polycarp's phone book
Codeforces div round Phone Book
2023-09-14 09:03:49 时间
【链接】h在这里写链接
【题意】
给你n个电话号码。
让你给每一个电话号码选定一个字符串s;
使得这个串s是这个电话号码的子串。
且不是任何一个其他电话号码的子串。
s要求最短。
【题解】
字典树。
每个电话号码,1,2,..length(s)开始的长度为length(s)...3,2,1的子串。
依次从根节点加入到字典树当中去。
然后考虑,一个子串s在另外一个字符串中出现过。
则另外一个字符串,在某个起点开始的子串加入到字典树的过程中,肯定会覆盖到s的路径。
(因为s肯定也是从根节点开始加入到字典树里面的)
则只要s没有完全被另外一个子串覆盖就好了。
->转换到字典树上,就是一条从根节点开始的路径(代表这个子串)没有被另外从根节点开始的一条路径完全覆盖就行。
那么这个子串就是只出现在i电话号码中的。
(在建字典树的时候,记录当前路径是哪个电话号码的子串就好.如果出现了重叠,就标记那个节点被覆盖了。)
【错的次数】
0
【反思】
抓住问题的本质。
思考问题中出现的矛盾点。
想想要怎么解决这个问题。
【代码】
#include <bits/stdc++.h> using namespace std; const int N = 7e4; int n,cnt = 1;//cnt 代表总节点个数 根节点在1位置,所以开始得赋值为1 string s[N+10]; int ch[(int)400e4][10];//最多有400万个节点。实际上没那么多。 int tc[(int)400e4]; int main(){ //freopen("F:\\rush.txt","r",stdin); ios::sync_with_stdio(0),cin.tie(0); cin >> n; for (int i = 1;i <= n;i++){//输入n个字符串,并且加入到AC自动机里去 //每个子串都要加进去 cin >> s[i]; int len = s[i].size(); for (int j = 0;j <= len-1;j++){//枚举起点 int now = 1; for (int k = j;k <= len-1;k++){ int &temp = ch[now][s[i][k]-'0']; if (temp==0) temp = ++cnt; now = temp;//一层一层地往下走。 if (tc[now]==0)//如果这个节点之前没有出现过 tc[now] = i;//赋值这个点第一次被i走过。 else//如果之前有走过。 if (tc[now]!=i)//如果之前有被其他人走过。 //就说明这条路被多个字符串走过。 //路径有覆盖的地方 //这个now位置显然有被覆盖 tc[now] = -1;//则直接赋值为-1 //下次有个字符串到了这个位置的话。 //就不能用这个字符串。还得往下走。 //走道没有被覆盖的地方为止。 //else } } } for (int i = 1;i <= n;i++){ //每个答案都对应输出一下。 //枚举每个子串的开头。然后在字典树里走路径。 //找到第一个没有被多个字符串的子串覆盖的路径 int ans = 100;//存最后的最小长度 int id;//最后答案的起始位置 int len = s[i].size(); for (int j = 0;j <= len-1;j++){ int now = 1; for (int k = j;k <= len-1;k++){ now = ch[now][s[i][k]-'0'];//往下走 if (tc[now]==i)//如果只有它一个人走过。则可以保证只有 //它一个字符串有这个子串 if (ans > k-j+1){ //如果答案更优 ans = k-j+1; id = j;//记录起始位置 break;//再往后找没有意义了。break就好 } } } for (int j = id;j <= id+ans-1;j++) cout << s[i][j]; cout << endl; } return 0; }
相关文章
- 【Codeforces Round #693 (Div. 3) E】Correct Placement
- 【Codeforces Round #635 (Div. 2) E】Kaavi and Magic Spell
- 【Codeforces Round #589 (Div. 2) D】Complete Tripartite
- 【Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) A】 Doggo Recoloring
- 【Codeforces Round #499 (Div. 2) E】Border
- 【Codeforces Round #482 (Div. 2) B】Treasure Hunt
- 【Educational Codeforces Round 41 (Rated for Div. 2) D】Pair Of Lines
- 【ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) C】 Permutation Cycle
- 【ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) B】Recursive Queries
- 【Codeforces Round #460 (Div. 2) D】Substring
- 【Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) A】 Perfect Squares
- 【Codeforces Round #301 (Div. 2) C】 Ice Cave
- 【codeforces 434 div 1 A】Did you mean...
- 【Codeforces Round #433 (Div. 2) C】Planning
- 【 Codeforces Round #425 (Div. 2) D】Misha, Grisha and Underground
- 【Codeforces Round #425 (Div. 2) B】Petya and Exam
- 【Codeforces Round #420 (Div. 2) C】Okabe and Boxes
- Codeforces Round #FF (Div. 2) D. DZY Loves Modification 贪心+优先队列
- Codeforces Round #254 (Div. 2)D(预计)
- Codeforces Round #FF (Div. 2)
- Codeforces Round #264 (Div. 2) C
- Codeforces Round #216 (Div. 2) E. Valera and Queries (BIT)
- Codeforces Round #107 (Div. 2)---A. Soft Drinking
- Codeforces Round #469 (Div. 2)
- Codeforces Round #451 (Div. 2)
- 赛后补题:Codeforces Round #843 (Div. 2) 1775C. Interesting Sequence
- 赛后题解:Codeforces Round #841(Div. 2) CF1731D. Valiant‘s New Map