集训队作业解题报告

1、题目来源Ural 1574 Mathematicians and bracketshttp:/acm.timus.ru/problem.aspx?space=1&num=1574问题描述定义：Turn(s,k)输入：s核心算法 为算法刻画和证明的方便，引入一下定义：对于任意长为n括号串S，定义：当=(时，=1；当=)时，=-1。（i=1,2n）并且规定=。 对于任意括号串s定义：F(s,l,r)= 。并且规定对于输入的串s，Ak=F(s,1,k)。 依次计算A1A2An，同时算出他们的最小值m。若An0，则输出0；若An=0，则寻找有多少个k使得Ak=m，这个统计的个数就是答案，直接输出即可。

2、算法证明 引理：一个长为n串S是合法的当且仅当，对所有的k=1,2,3n-1都有F(S,1,k) 0，且F(S,1,n)=0。 引理的证明： 先证必要性：若一个长为n串S是合法的，则对所有的k=1,2,3n-1都有F(S,1,k) 0，且F(S,1,n)=0。 对字符串的长度n归纳： 当n=2的时候，一定有s=()，命题成立。 若当字符串长为2,3,4n-1时，命题都成立，则当长为n时： 若s是(t)形式的（其中t是合法） 则F(s,1,1)=10，F(s,1,i+1)=1+F(t,1,i)10(i=1,2n-2)F(s,1,n)=1+F(t,1,n-2)+(-1)=0 命题成立。 若s是ab

3、形式的（其中a,b是合法的），a长为k，b长为n-k。 则F(s,1,i)0，（i=1,2k） F(s,1,i+k)=F(s,1,k)+F(s,k+1,i+k)=F(a,1,k)+F(b,1,i)0，(i=1,2n-k) F(s,1,n)=F(a,1,k)+F(b,1,n-k)=0 命题成立。 必要性证毕。 再证充分性：若对所有的k=1,2,3n-1都有F(S,1,k) 0，且F(S,1,n)=0，则一个长为n串S是合法的。 对字符串的长度n归纳： 当n=2的时候，由于F(s,1,1)= =1或-1，F(s,1,1)0，所以F(s,1,1)=1，所以=(，故命题成立。 若当字符串长为2,3,4

4、n-1时，命题都成立，则当长为n时： 若存在一个k=1,2n-1使得F(s,1,k)=0则F(s,k+1,k+i)=F(s,1,k+i)-F(s,1,k)=F(s,1,k+i)0所以s的子串，s1s2sk和sk+1sk+2sn都是合法的，所以s是合法的。 命题成立。 若不存在一个k=1,2n-1使得F(s,1,k)=0 则F(s,1,i)0，即F(s,1,i)1（i=1,2n-1） 所以F(s,1,1)=F(s,1,n-1)=1F(s,2,i)=F(s,1,i)-F(s,1,1)=F(s,1,i)-10 (i=2,3n-1)F(s,2,n-1)=F(s,1,n-1)-F(s,1,1)=0 所以

5、s的子串，s2s3sn-1是合法的，所以s是合法的。 命题成立。 充分性证毕。 引理证毕！ 回到原题： 由引理，“turn(s,k)是好的”等价于“对所有的j=1,2,3n都有F(s,k+1,k+j)0且An=0”而注意到：F(s,k+1,k+j)=F(s,1,k+j)-F(s,1,k)=Ak+j-Ak所以“F(s,k+1,k+j)0”等价于“Ak+jAk”另一方面，若An=0则对于任意的i=1,2n都有An+i=Ai。所以，当An=0时，“对所有的j=1,2,3n都有F(s,k+1,k+j)0”等价于“Ak是Ak+1 Ak+2 Ak+n的最小值”即“Ak是A1A2An的最小值”这就证明了算法

6、。算法实现 算法十分简单，没有实现上的问题。源代码var st:ansistring; i,n,s,min,ans:longint;begin readln(st); n:=length(st); s:=0; min:=0; ans:=0; for i:=1 to n do begin if sti=( then inc(s) else dec(s); if s=min then inc(ans); if smin then begin min:=s; ans:=1; end; end; if s=0 then writeln(ans) else writeln(0);end.原题描述1574

7、. Mathematicians and bracketsTime Limit: 1.0 secondMemory Limit: 64 MBOnce upon a time three mathematicians met The first of them wrote a sequence of brackets on a chalkboard. The second one wondered if there was a cyclic shift turning that sequence into a regular one. After thinking for a while, th

8、e third mathematician told the number of such shifts. You are given the sequence of brackets written by the first mathematician and you are to find the number told by the third mathematician. A regular sequence of brackets is defined as follows. An empty string is a regular sequence of brackets. If

9、a string a is a regular sequence of brackets, then the string (a) is also a regular sequence of brackets. If strings a and b are regular sequences of brackets, then the string ab is also a regular sequence of brackets. There are no other regular sequences of brackets. A string a is a cyclic shift of

10、 a string b if a and b have the same lengths and a consists of some (possibly empty) suffix from b followed by a prefix from b. InputThe only line of the input contains the sequence of brackets written by the first mathematician. The sequence is non-empty and its length doesnt exceed 105.OutputOutput the number of cyclic shift