题目大意：有n个初始字符串，由这n个初始字符串延伸出实际字符串。
每个实际字符串为初始字符串循环后得到。字符集为 {0,1}。如初始字符串
01，循环后得到实际字符串
01010101…。求n个实际字符串中任意两个串的最长公共前缀。第i个初始字符串的长度小于500。保证每个初始字符串都不存在周期。其中n属于20000.
一个很显然的思路：既然只有01，那么我们分治来做，对于每一位，是0的分一堆儿，是1的分一堆儿
然后分到最后，l=r的时候，分到了哪一位就是最长的公共前缀，然后每个都取max
注意：一定要提前处理好字符串的长度，不可边算边处理
hack数据：
10与101
如果先排序后处理的话，会得到：10，101
如果先处理后排序的话，会得到101，10(10)
这就是tm20pts与100pts的区别
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 66, inf = 214748364;
int n, res; string s[N];
inline void solve(int x, int l, int r)
{
if (l == r) return (void)(res = max(res, x - 1));
int i, mid = -inf;
for (i = l + 1; i <= r; ++ i)
{
if (s[i][x] != s[i - 1][x])
{
mid = i - 1;
break;
}
}
if (mid != -inf) solve(x + 1, l, mid), solve(x + 1, mid + 1, r);
else solve(x + 1, l, r);
return;
}
signed main()
{
int i; n = read();
for (i = 1; i <= n; ++ i)
{
getline(cin, s[i]);
string a = s[i];
while ((s[i].length() + a.length()) <= 1000) s[i] += a;
}
sort(s + 1, s + n + 1), solve(0, 1, n);
put(res);
fclose(stdin), fclose(stdout);
return 0;
}
|
总结：细节决定成败，我今天的经历仿佛一场梦，从第一到倒数，无法预料
还是要以积极的态度面对生活，放下分数，拿起知识，尽人事，听天命，面临CSP-S最后一个月，冲冲冲！