https://atcoder.jp/contests/abc312/tasks/abc312_h
Ex - snukesnuke
N个字符串s[i]
1
2
3
4
5
6
7
8
| t = set<string>
for i := 1..n
k_i = 1
while s[i] * k_i in t:
k_i++
t.insert(s[i] * k_i)
求 所有 k_1..n
|
$\sum |S_i| \le 2\cdot 10^5$, 小写英文字母
2s
1024mb
我的思路
如果不同字符串之间互不影响，那么相同si的ki对应的值就是1,2,4,5,6,7…
那么问题就是如果不同的字符串之间有影响
$k_i\cdot s_i = k_j\cdot s_j, s_i \neq s_j$
若$k_i = 1$,也就是 $s_i$会是$s_j$的重复序列， 首先重复序列的长度一定是 $s_i$长度的因数，这样可以 额外$O(|s_i| log|s_i|)$ 的把所有处理成
$(s_i,repeat)$ 的形式
根据字符串的循环结的理论，显然 一个字符串有一个最小循环单位，且其它循环都是它的倍数
1
2
3
4
5
6
7
8
9
| 引理 简单证明
最小循环节 l0 [.....][.....]
非倍数循环结 l1 [.........]
可以得到 (长度l1中，起始长度l0循环平移相等) -> F(l1,l0)
而 F(a,b) 当 a%b!=0时 可以得到 -> F(b,a%b)
这就是 gcd的过程，是有限的，所以总可以得到更小的循环节，矛盾
|
若 $k_i,k_j$均不为1,且$gcd(k_i,k_j) = 1$,那么用到上面引理类似的
不失一般性，设 $|s_i| > |s_j|$
1
2
3
4
5
| [s_i......][s_i......][s_i......][s_i......][s_i.....]
[s_j....][s_j....][s_j....][s_j....][s_j....][s_j....]
得到 $F(len(s_i), len(s_j))$
所以它们一定有更小的循环节
|
综上，首先把所有的字符串拆成最小循环节和repeat, 然后对所有 最小循环结做hash
似乎就没了
题解
我的代码直接过了
代码
https://atcoder.jp/contests/abc312/submissions/49407753
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N = 200000;
char t[N+10];
struct State{
string s;
int idx;
int repeat;
};
vector<State> sidxr;
vector<int> y[N+10];
bool check(const string&s,int r){
rep(i,0,r) rep(j,0,s.length()/r) if(s[i+j*r] != s[i]) return false;
return true;
}
int main(){
rep(i,1,N+10) rep(j,2,N+10){
if(i*j > N) break;
y[i*j].push_back(i);
}
int n=read();
rep(i,0,n) {
scanf("%s",t);
sidxr.push_back(State{string(t),(int)i,1});
}
rep(i,0,n) {
int sz = sidxr[i].s.length();
for(auto j:y[sz]) if(check(sidxr[i].s,j)) {
sidxr[i].repeat= sz / j;
sidxr[i].s = sidxr[i].s.substr(0,j);
break;
}
}
vector<int>ans(n);
map<string,map<int,int> > last;
map<string,set<int> > used;
sort(begin(sidxr),end(sidxr),[&](const auto&a,const auto&b){return a.s == b.s? a.idx<b.idx:a.s<b.s;});
for(const auto&o:sidxr) {
auto &u=used[o.s];
auto &l=last[o.s];
for(ll c = l[o.repeat] + 1;;c++) if(!u.count(c*o.repeat)) {
ans[o.idx] = c;
l[o.repeat] = c;
u.insert(c*o.repeat);
break;
}
}
for(auto o:ans)printf("%d ",o);
return 0;
}
|
总结
Ex，题目评分倒是不高2477
嗯，自己过了，这个应该就是是否熟练的 字符串的算法了，这字符串自己循环好像就这个东西，用了好多次，熟练的话都可以省去上面的证明引理的细节