集訓(xùn)隊作業(yè)解題報告

1、題目來源Ural 1574 Mathematicians and bracketshttp:/acm.timus.ru/problem.aspx?space=1&num=1574問題描述定義：Turn(s,k)輸入：s核心算法 為算法刻畫和證明的方便，引入一下定義：對于任意長為n括號串S，定義：當(dāng)=(時，=1；當(dāng)=)時，=-1。（i=1,2n）并且規(guī)定=。 對于任意括號串s定義：F(s,l,r)= 。并且規(guī)定對于輸入的串s，Ak=F(s,1,k)。 依次計算A1A2An，同時算出他們的最小值m。若An0，則輸出0；若An=0，則尋找有多少個k使得Ak=m，這個統(tǒng)計的個數(shù)就是答案，直接輸出即可。

2、算法證明 引理：一個長為n串S是合法的當(dāng)且僅當(dāng)，對所有的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歸納： 當(dāng)n=2的時候，一定有s=()，命題成立。 若當(dāng)字符串長為2,3,4n-1時，命題都成立，則當(dāng)長為n時： 若s是(t)形式的（其中t是合法） 則F(s,1,1)=10，F(xiàn)(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歸納： 當(dāng)n=2的時候，由于F(s,1,1)= =1或-1，F(xiàn)(s,1,1)0，所以F(s,1,1)=1，所以=(，故命題成立。 若當(dāng)字符串長為2,3,4

4、n-1時，命題都成立，則當(dāng)長為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。所以，當(dāng)An=0時，“對所有的j=1,2,3n都有F(s,k+1,k+j)0”等價于“Ak是Ak+1 Ak+2 Ak+n的最小值”即“Ak是A1A2An的最小值”這就證明了算法

6、。算法實現(xiàn) 算法十分簡單，沒有實現(xiàn)上的問題。源代碼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