題意

　　給你一個由r w b組成的字符串，這個串首位相接連成一個環

　　給出一個計算方法:選取這個環任意兩個相鄰元素的之間，由這個位置順時針取連續相同元素，逆時針取連續相同元素，兩個方向的元素可不同

　　求問能取到最大的數目

　　注：w可以被看作r，也可以被看作b

分析

　　方法1：模擬

　　關于環的處理：將這個環任意一個位置斷開成一條鏈，然后復制出一條一模一樣的接在這條鏈的后面，即構造了一個2*n長度的鏈

? ? ? 模擬時注意w的問題，w元素的前后元素一致時，w元素后的元素才可計入（WA一次）

? ? ? 第二個問題，當一條鏈元素一樣時，正反兩次掃描會計算兩次，注意掃過的元素不能再利用（WA第二次）

? ? ? 比如test2就是 ：rrr 答案應該是3 而不是6

　　后來各種SB錯誤比如文件名寫錯啦沒關文件啦忘記屏蔽亂七八糟的輸出啦之類的..總共交了6次才過T.T

? ? ? 方法2：模擬..【比較帥一點的模擬..其實算遞推啦、

? ? ? 在把環處理成鏈后，只需正反各掃一次即可

　　例如從左向右掃，開兩個數組r b，每次掃描到i 時遇到r就r[i]=r[i-1]++,b[i]=0 ，遇到b時b[i]=b[i-1]++,r[i]=0，遇到w時b[i]=b[i-1]++,r[i]=r[i-1]++

　　簡單明了，每次遇到一個元素時，另一個元素就不連續了，需要清零，而這個元素就是上一個元素位置時本元素數組+1

? ? ? 所以對于每一個位置i，可以取的總和是max(bl[i],rl[i])+max(br[i+1],rr[i+1])

　　然后在所有i里挑一個最大的，記為ans，輸出即可

? ? ?這個也要注意正反兩次掃完可能會計算兩邊的情況（對應test2），如果ans>n，輸出n

Accepted Code

? ? ?方法1：

1 { 2 ID: jessiel2 3 PROG: beads 4 LANG: PASCAL 5 } 6 Program beads; 7 Const 8 Infile = 'beads.in'; 9 Outfile = 'beads.out'; 10 Var 11 t,s,t2:Array[0..1000]Of Char; 12 i,ans,n,j,ii,sum1,sum2:Longint; 13 last:Char; 14 Function pd1(x:Longint):Boolean; 15 Begin 16 If (t[x]<>'w') And (t[x+1]<>'w') Then Begin 17 If t[x]=t[x+1] Then Exit(true) Else Exit(false); 18 End; 19 If (t[x]='w') And (t[x+1]<>'w') Then Begin 20 If (t[x+1]=last) Or (last='0') Then Exit(true) Else Exit(false); 21 End; 22 If (t[x]<>'w') And (t[x+1]='w') Then Begin 23 last:=t[x]; 24 Exit(true); 25 End; 26 If (t[x]='w') And (t[x+1]='w') Then Begin 27 Exit(true); 28 End; 29 Exit(false); 30 End; 31 Begin 32 Assign(input,infile);Reset(input); 33 Assign(output,outfile);Rewrite(output); 34 ReadLn(n); 35 ans:=1; 36 For i:=1 To n Do Read(s[i]); 37 FOr i:=n+1 To 2*n Do s[i]:=s[i-n]; 38 For i:=1 To n Do Begin 39 For j:=1 To n Do t[j]:=s[j+i-1]; 40 j:=1; 41 sum1:=1; 42 If t[1]<>'w' Then last:=t[1] Else last:='0'; 43 While pd1(j) And (j<n) Do Begin 44 t[j]:=chr(j); 45 Inc(j); 46 Inc(sum1); 47 End; 48 t[j]:=chr(j); 49 If (t[n]<>'r') And (t[n]<>'b') And (t[n]<>'w') Then sum2:=0 Else 50 sum2:=1; 51 j:=1; 52 t2:=t; 53 For ii:=1 To n Do t[ii]:=t2[n-ii+1]; 54 If t[1]<>'w' Then last:=t[1] Else last:='0'; 55 While pd1(j) And (j<n) Do Begin 56 t[j]:=chr(j+n); 57 Inc(j); 58 Inc(sum2); 59 End; 60 If sum1+sum2>ans Then ans:=sum1+sum2; 61 End; 62 WriteLn(ans); 63 Close(input);Close(output); 64 End.

方法2

1 { 2 ID: jessiel2 3 PROG: beads 4 LANG: PASCAL 5 } 6 Program beads; 7 Const 8 infile = 'beads.in'; 9 outfile = 'beads.out'; 10 Var 11 bead:Array[0..701]Of Char; 12 rl,bl,rr,br:Array[0..701]Of Integer; 13 i,n,ans:Integer; 14 15 Function max(a,b:Integer):Integer; 16 Begin 17 If a>b Then exit(a) Else exit(b); 18 ENd; 19 20 Begin 21 Assign(input,infile);Reset(input); 22 Assign(output,outfile);Rewrite(output); 23 ReadLn(n); 24 For i:=1 TO n Do Read(bead[i]); 25 For i:=n+1 To 2*n Do bead[i]:=bead[i-n]; 26 rl[0]:=0;bl[0]:=0; 27 For i:=1 To 2*n Do 28 Case bead[i] Of 29 'r': 30 Begin 31 rl[i]:=rl[i-1]+1; 32 bl[i]:=0; 33 End; 34 'b': 35 Begin 36 rl[i]:=0; 37 bl[i]:=bl[i-1]+1; 38 ENd; 39 'w': 40 Begin 41 rl[i]:=rl[i-1]+1; 42 bl[i]:=bl[i-1]+1; 43 End; 44 End; 45 rr[2*n+1]:=0; 46 br[2*n+1]:=0; 47 For i:=2*n Downto 1 Do 48 Case bead[i] Of 49 'r': 50 Begin 51 rr[i]:=rr[i+1]+1; 52 br[i]:=0; 53 End; 54 'b': 55 Begin 56 rr[i]:=0; 57 br[i]:=br[i+1]+1; 58 End; 59 'w': 60 Begin 61 rr[i]:=rr[i+1]+1; 62 br[i]:=br[i+1]+1; 63 ENd; 64 End; 65 ans:=0; 66 For i:=1 TO 2*n-1 Do 67 ans:=max(max(bl[i],rl[i])+max(br[i+1],rr[i+1]),ans); 68 If ans>n Then ans:=n; 69 WriteLn(ans); 70 Close(input);Close(output); 71 End.

?

?

?

轉載于:https://www.cnblogs.com/Rinyo/archive/2013/05/05/3060894.html

總結

以上是生活随笔為你收集整理的模拟/usaco 1.1.4 Broken Necklace的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。