注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

2528: [Poi2011]Periodicity  

2013-03-09 15:51:21|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目大意】
给定一个字符串s,其长度为n,如果对于任意的i(1<=i<=n-t)有s[i]=s[i+t](1<=t<n-1),那么称其t是s的一个周期。
定义Per(s)为所有s的周期组成的集合。
例如:Per(ABIABUABIAB)={6,9}, Per(01001010010)={5,8,10}, Per(0000)={1,2,3}。
你的任务是构造一个长度恰好为n的01串r,使得:
1.Per(s) = Per(r)
2.在所有满足条件1的01串中,该串的字典序最小。


神构造题……
我来转述下波兰人的捉法。

首先波兰人认为题目中那样定义Per不科学,在Per里人为地加上周期n。

定义:(Name and Conquer)
s是字符串,则|s|表示s的长度。
A是集合,则|A|表示集合A的大小。
s[i]表示字符串的第i个字符,从1开始标号。
s[l, r]表示区间[l, r]以内的那个子串。
s1 . s2:串联s1、s2两个字符串,如"娃" . "哈哈" = "哇哈哈"
s * a表示把字符串重复a次形成的字符串。如"娃哈哈" * 3 = "娃哈哈娃哈哈娃哈哈" (*的优先级大于.)

gcd(a, b):a、b的最大公约数
a \ b:a能整除b,即a是b的约数。使用斜杠而不是竖线是具体数学推崇的,因为竖线在数学里被过度使用了。
本原串:一个字符串s除|s|以外的周期,都不是|s|的约数,则称s是本原串。
前后缀:如果一个字符串t,它既是s的前缀,也是s的后缀,那么t就是s的前后缀。
(求神犇告诉我prefix-suffix怎么翻译……我只会这么翻译)


【Lemat 1 (o okresowosci)】(定理一 (周期定理))
若p, q ∈ Per(s)且 p + q <= |s|,则gcd(p, q) ∈ Per(s)
【周期定理的证明】
波兰人没有给出……波兰人说他们出过类似题……这东西的证明在那道类似题的题解里面……
于是自己YY了下,发现是可证的。
不妨设p > q
则对于任意的i (1 <= i <= n - p),必有s[i] = s[i + p]
而另一方面,设p = aq + r (0 <= r < q)
若r = 0,则gcd(p, q) = q,而q ∈ Per(s)。
若r ≠ 0,则又因为
s[i + r] = s[i + r + q] = s[i + r + 2q] = ... = s[i + r + aq] = s[i + p]
得到个神奇的结论:
对于任意的i (1 <= i <= n - p),必有s[i] = s[i + r]

现在一定有0 < r < q
再设q = br + t (0 <= t < r)
若t = 0,则gcd(p, q) = gcd(q, r) = r,由于:
s[i] = s[i + r] (1 <= i <= n - p)
s[i] = s[i + q] = s[i + br] (1 <= i <= n - q)
n - p >= q
所以有:
s[1, r] = s[r + 1, 2r] = ... = s[(b - 1)r + 1, br]
得:
s[1, br] = s[1, r] * b
这就一目了然了吧……q ∈ Per(s)所以 r ∈ Per(s)
若t ≠ 0,则又因为
s[i + t] = s[i + t + r] = s[i + t + 2r] = ... = s[i + t + br] = s[i + q]
且要满足1 <= i <= n - p - q + r
又可以得到个神奇的结论:
对于任意的i (1 <= i <= n - p - q + r),必有s[i] = s[i + t]

第一轮是:p, 1 <= i <= n - p; q, 1 <= i <= n - q; 得到r, 1 <= i <= n - p
第二轮是:q, 1 <= i <= n - q; r, 1 <= i <= n - p; 得到t, 1 <= t <= n - p - q + r
第三轮是: r, 1 <= r <= n - p; t, 1 <= t <= n - p - q + r; 得到u, 1 <= u <= n - p - q + t

发现是个辗转相除法的过程。
如此重复进行证明就行了。严谨的应该用数学归纳法……

【Lemat 2 (o slowach pierwotnych)】(定理二 (本原串定理))
如果一个串不是本原串,修改其中任意一个字符,它就会变成本原串。
【本原串定理的证明】
波兰人没有给出……不过这个很好理解也很好证了吧囧……

考虑一个长度t,那么t是周期等价于s[1, |s| - t] = s[t, |s|],这个显然吧。
也就是说s[1, |s| - t]是s的前后缀。
反过来,如果s[1, a]是s的前后缀,那么|s| - a一定是周期,这个也显然吧。
与其研究周期,还不如研究前后缀。
定义PS(s)为s的所有前后缀的长度组成的集合。即PS(s) = {x | s[1, x]是s的前后缀}
规定0 不属于 PS(s), 而|s| ∈ PS(s)

对于题目中给的s,将PS(s)里的元素从小到大排序,得到p[1], p[2], p[3], ..., p[|PS(s)|]。
再设 strP[i] 为 PS(r) = {p[1], p[2], ... p[i]}的字典序最小的01串。当然了……|strP[i]| = p[i]

注意对于给定的s,PS(s)是非常好求的,就是KMP一下,那么PS(s) = {next[|s|], next[next[|s|]], next[next[next[|s|]]], ...}

【Opis algorytmu】(算法描述)
我们想求strP[|PS(s)|],于是我们顺次考虑strP[1]、strP[2]、...、strP[|PS(s)|]

如果说现在已知strP[i]了,我们要求strP[i + 1]
考虑一个简单的情况,p[i + 1] <= 2 * p[i]
现在我们断言:
【结论一】
strP[i]一定是strP[i + 1]的前后缀。
那么就是如图:
2528: [Poi2011]Periodicity - vfleaking - vfleaking的博客
由于p[i + 1]太小,导致两个字符串会叠在一起。
设中间重合部位的长度为 j, 则j = 2 * p[i] - p[i + 1]
于是只要在strP[i]后面添上strP[i][j + 1, p[i]]就能得到strP[i + 1]

【结论一的证明】
这样为什么是正确的呢?
字典序显然会是最小的了。
而前后缀的前后缀一定是前后缀,所以p[1], p[2], ... p[i - 1] ∈ PS(strP[i + 1])(没看懂的同学可以去复习KMP……)
那么就是要证明两个东西:
1.p[i] ∈ PS(strP[i + 1])
2.不存在q, p[i] < q < p[i + 1], 使得q ∈ PS(strP[i + 1])

先来看1。
即证strP[i + 1][1, p[i]] = strP[i + 1][p[i + 1] - p[i], p[i + 1]]
即证上图中的两个串重合部分相等
即证j ∈ PS(strP[i])
即证p[i] - j ∈ Per(strP[i])
即证p[i + 1] - p[i] ∈ Per(strP[i])
对于题目中给的串s,设strW[i]和strW[i + 1]分别为s[1, p[i]], s[1, p[i + 1]]
那么就肯定有:
2528: [Poi2011]Periodicity - vfleaking - vfleaking的博客
笑话!难道strW[i]没有p[i + 1] - p[i]这个周期?
所以p[i + 1] - p[i] ∈ Per(strW[i]) = Per(strP[i])
得证。

再来看2。
反证法,假设存在这样一个q,那么strP[i + 1]就必存在两个周期:p[i + 1] - p[i], p[i + 1] - q
因为p[i + 1] - p[i] + p[i + 1] - q < p[i + 1] - p[i] + p[i + 1] - p[i] = p[i + 1] + (p[i + 1] - 2 * p[i]) <= p[i + 1]
所以p[i + 1] - p[i] + p[i + 1] - q <= p[i + 1]
那么就可以使用周期定理,于是strP[i + 1]必有周期d = gcd(p[i + 1] - p[i], p[i + 1] - q)
则d \ (p[i + 1] - p[i])。
仿照1中设strW,我们可以发现:
笑话!strW[i + 1]怎么可能会有d这个周期?如果有的话,则长度在p[i]与p[i + 1]之间必然还存在一个前后缀p[i + 1] - d。



再来考虑复杂一点的情况,p[i + 1] > 2 * p[i]
设j = p[i + 1] - 2 * p[i]
此时我们断言:
2528: [Poi2011]Periodicity - vfleaking - vfleaking的博客
且Δ不是"0" * j就是 "0" * (j - 1) . "1"
我们先来证明一个看似无关紧要的结论:
【结论二】
若有一个字符串P,设U = P . "0" * j . P,则不存在q,|P| < q < |U|,使得q ∈ PS(U)的充要条件是P . "0" * j是本原串。
【结论二的证明】
设H = P . "0" * j

当P全是0的时候显然成立。因为一定存在q,且H不可能是本原串哇哈哈……

所以只考虑P不全是0的情况。

先来证明存在一个这样的q时,H一定不是本原串。
如果说情形是这样子的:
2528: [Poi2011]Periodicity - vfleaking - vfleaking的博客
那么设Q = strP[i + 1][1, q]
然而我们发现了一个很囧的事情:
Q = P . "0" * t = "0" * t . P (t = q - |P|
可以手动反复递归一下……P只可能全是0。矛盾了……

那么其实实际情况是这样的:
2528: [Poi2011]Periodicity - vfleaking - vfleaking的博客
即q >= |H|
感到振奋人心的事情了煤油?
|U| - |P|是周期吧~
|U| - q也是周期吧~
|H| + |P| = |U|吧……
|U| - |P| + |U| - q <= |U| - |P| + |U| - |H| <= |U|吧……
所以gcd(|U| - |P|, |U| - q)也是U的周期吧……
设它为d吧……
那么d \ (|U| - |P|)吧……
|U| - |P|好像是|H|诶!!!
所以d也是H的周期吧……而且d还是|H|的约数吧……
这一部分证完了……

下面反过来,证明H不是本原串时,一定存在这样的q。
不是本原串就一定有个周期d且d \ |H|
发现d也一定是U的周期啊囧……
所以取q = |U| - d就行了啊……
这一部分也证完了……

【结论三】
Δ不是"0" * j就是 "0" * (j - 1) . "1"
【结论三的证明
如果Δ = "0" * j时不行,说明此时strP[i] . "0" * j不是本原串。
由于本原串定理,所以取Δ = "0" * (j - 1) . "1"时一定行。
而字典序难道不是最小的?
所以得证。

两种情况都讨论完了。
所以……所以直接上代码吧:

function MinLex(p[1], p[2], ..., p[k]) // p数组,长度为k。意义如前所述
begin
if p[1] = 1 then

strP[1] = "0"

else

strP[1] = ("0" * (p[1] - 1)) . "1";
for i = 1 to k - 1 do begin
j = p[i + 1] - 2 * p[i];
if j <= 0 then

strP[i + 1] = strP[i] . strP[i][(-j) + 1, p[i]]
else if strP[i] . "0" * j 是本原串 then

strP[i + 1] = strP[i] . "0" * j . strP[i]
else

strP[i + 1] = strP[i] . "0" * (j - 1) . "1" . strP[i];
end
return strP[k];
end


接下来大家都应该会实现了……网上有些题解是O(nlogn)的,不要误导小朋友啊T_T 虽然也可以A……

回忆KMP,这个算法要求每次在后面添加一个字符,在后面删除一个字符,我们可以轻易维护next数组,而且还是均摊O(1)的。
就有一个地方有点不好办,判断strP[i] . ("0" * j)是不是本原串。
当然在程序里肯定是把当期维护的答案r加了j个"0"后再来判断。不是的话就删一个字符,加一个"1"。
那么现在有一个字符串,也有它的next数组,怎么判断是不是本原串。
结论是字符串s是本原串当且仅当它的最小周期不为|s|且最小周期是|s|的约数。
这个还是很好证的。
假设最小周期为|s|……不再赘述
假设最小周期不为|s|且最小周期不是|s|的约数,但s是本原串
那么假设|s|最小周期为a,有一个周期d是|s|的约数且d ≠ |s|
则必有 d <= |s| / 2
而a < d
所以 a < |s| / 2
所以a + d <= |s|
所以gcd(a, d)也是周期
而a不是d的约数,所以必有 gcd(a, d) < a,矛盾。
于是就爽了,总时间复杂度O(n)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MaxN = 200000;

class KMPString
{
private:
inline void calc(const int &pos)
{
if (pos == 0)
next[pos] = -1;
else
{
int i = next[pos - 1];
while (i != -1 && s[i + 1] != s[pos])
i = next[i];
if (s[i + 1] == s[pos])
i++;
next[pos] = i;
}
}
public:
int n;
char s[MaxN + 1];
int next[MaxN];

inline void init()
{
n = 0;
s[n] = '\0';
}
inline void input()
{
scanf("%s", s);
n = strlen(s);

for (int i = 0; i < n; i++)
calc(i);
}
inline void output()
{
printf("%s\n", s);
}

inline void push_back(char c)
{
s[n++] = c;
calc(n - 1);
s[n] = '\0';
}
inline void pop_back()
{
n--;
s[n] = '\0';
}
};

int main()
{
int nCases;
cin >> nCases;

while (nCases--)
{
static KMPString str;
str.input();

int per_n = 0; // period
static int per[MaxN];

for (int i = str.n - 1; i >= 0; i = str.next[i])
per[per_n++] = i + 1;
reverse(per, per + per_n);

static KMPString res;
res.init();
if (per[0] == 1)
res.push_back('0');
else
{
for (int j = 0; j < per[0] - 1; j++)
res.push_back('0');
res.push_back('1');
}

for (int i = 1; i < per_n; i++)
{
if (per[i] <= per[i - 1] * 2)
{
for (int j = 2 * per[i - 1] - per[i]; j < per[i - 1]; j++)
res.push_back(res.s[j]);
}
else
{
int t = per[i] - per[i - 1] * 2;
for (int j = 0; j < t; j++)
res.push_back('0');
if (res.next[res.n - 1] != -1 && res.n % (res.n - (res.next[res.n - 1] + 1)) == 0)
{
res.pop_back();
res.push_back('1');
}
for (int j = 0; j < per[i - 1]; j++)
res.push_back(res.s[j]);
}
}

res.output();
}

return 0;
}


  评论这张
 
阅读(1270)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017