國家集訓(xùn)隊(duì)作業(yè)treblecross解題報告

1、Treblecross 解題江蘇省常州高級中學(xué)問題描述Treblecross 是一個在一維棋盤上進(jìn)行的雙人流在棋盤上的任何一個空位置放上 X。如果某個。開始時，棋盤是空的。兩名者輪者的某步操作之后，出現(xiàn)了三個相鄰的X，該者獲勝。判斷任意一個局面（可能不是初始局面）是必勝局面還是必敗局面。數(shù)據(jù)限制棋盤長度不超過 200。題目來源UVA Problemset Achieve Problem 10561 Treblecross算法分析由于棋盤的長度比較長，直接用博弈樹是行不通的，必須分析這個問題的特殊性。的目標(biāo)是得到三個相鄰的X，來看看哪些情況下可以立即得到三個相鄰的X，不難發(fā)現(xiàn)只有兩種情況：如果已

2、經(jīng)有兩個相鄰的 X 了，只要在它們旁邊放上一個 X，就可以了；如果有兩個X 之間只有一個空位，只要在它們中間放上X，就可以了。兩種最簡單的必勝局面上述兩種情況是最簡單的必勝局面，但是如果當(dāng)前局面不包含這兩種情況呢？那么任意兩個 X 之間至少有兩個空位（沒有空位和只有一個空位就是上述的必勝局面）。由剛才的分析得到，如果一個位置上放了X，這個位置的周圍兩格都不能再放上 X 了，否則就必敗了。所以在一個位置放上 X 后，可以想象它周圍兩格都被刪掉了，因?yàn)槌遣坏靡?，這些格子是不會被占的。對初始局面，進(jìn)行一次刪格子的操作，可以把棋盤斷成若干個互不影響的空位段。以后的每一步操作都可以看作是刪掉一段空位，

3、得到一組新的空位段。這樣，原問題被轉(zhuǎn)化成了經(jīng)典的取石子類的博弈問題1。這類博弈問題的一般特點(diǎn)是：1.2.雙人；每一步只能對某一堆石子進(jìn)行操作；1參見 2002 年中國國家集訓(xùn)隊(duì)同學(xué)由感性認(rèn)識到理性認(rèn)識透析一類搏弈的解答過程XXXX3.4.5.每一步操作的限制，只與這堆石子的數(shù)目或一些常數(shù)有關(guān)；操作在有限終止，并不會出現(xiàn)循環(huán)；誰無法繼續(xù)操作，誰就是輸家。此類問題的一般解法：1.2.3.4.5.6.7.8.用一個 n 元組(a1, a2, , an)，來描述過程中的一個局面。用符號#S，表示局面 S 所對應(yīng)的二進(jìn)制數(shù)。用符號$(x)，表示局面(x)的下一步所有可能出現(xiàn)的局面的集合。定義集合 g(x

4、)：設(shè)$(x)=S1, S2, , Sk，則 g(x)=#S1, #S2, , #Sk。負(fù)整數(shù)集為全集，集合 G(x)表示集合 g(x)的補(bǔ)集。定義函數(shù)f(n)：f(n)=minG(n)，即f(n)等于集合 G(n)中的最小數(shù)。設(shè)局面S=(a1, a2, , an)，#S=f(a1)+f(a2)+f(an)，采用二進(jìn)制數(shù)的加法。若#S0，則先行者有必勝策略；若#S=0，則后行者有必勝策略。根據(jù)這個一般定律，可以設(shè)計出一個高效的遞推算法，它的時間復(fù)雜度為 O(n2)，空間復(fù)雜度為O(n)。對于此題的數(shù)據(jù)范圍已經(jīng)綽綽有余了。源程序Program Treblecross;ConstMaxn=200;

5、Varf:Array 0.Maxn of Long;used,backupused:Array 1.Maxn ofNumOfTestcases,Testcase:Long;n:Long;a:String;Function Max(a,b:LongBegin):Long;If ab Then Max:=a Else Max:=b;End;Function Min(a,b:LongBegin):Long;If ab Then Min:=a Else Min:=b;End;Procedure Init;Varvisit:Array 0.Maxn of;i,j,left,right:Long Begi

6、nf0:=0;For i:=1 to Maxn Do BeginFillchar(visit,Sizeof(visit),0); For j:=1 to i DoBeginleft:=Max(j-2,1); right:=Min(j+2,i);visitfleft-1 xor End;j:=0; While visitj fi:=j;End;End;fi-right:=True;nc(j);Procedure Input_Data; BeginReadln(a);n:=LengEnd;);Function Win:Vari,ans,tot:Long Beginans:=0; i:=1;Whil

7、e i=n Do BeginWhile (i=n) tot:=0; While (i0);End;and usedinc(i);and not usediDoftot;Procedure Solve;Vari,j:Long:Begin;:=True;For i:=1 to n DoIf (ai=.) and (i1) and (i2) and (ai-2=X) and (ai-1=X) and (ai+2=X) ThenBegin IfThen BeginWrin(WINNING);:=False;EndElse Write( ); Write(i);End;or(in-1)and(ai+1=

8、X)If not BeginWrin; Exit;End;ThenFillchar(used,Sizeof(used),0); For i:=1 to n DoIf ai=X ThenFor j:=Max(i-2,1) to Min(i+2,n) If WinThen BeginWrin(WINNING);For i:=1 to n DoIf not usedi Then Beginbackupused:=used;Do usedj:=True;For j:=Max(i-2,1) to Min(i+2,n) Do usedj:=True;If not W BeginIfhenThen:=False Else Write( );Write(i); End;used:=backupused;end;EndElse Wrin(LOSING);WriEnd;n;BeginAssign(Input,10561.in); Assign(Output,10561.out); Reset(Input);Rewrite