信息學(xué)試題cqoi2013簡單解析

1、CQOI2013 簡單解析Leqsott新Nim游戲顯然沒有輸出-1的情況，A必勝。（最壞情況下第一輪只剩一堆）直接暴力枚舉每種第一輪A拿了過后的狀態(tài)，再暴力枚舉第一輪B拿了過后的狀態(tài)，然后對剩下的進行普通的Nim游戲。此算法可通過50%的測試點。若把每堆火柴看作集合S中的元素，每種A拿后必勝的狀態(tài)看作集合L中的元素（即L為集合的集合），據(jù)分析及證明，M=S，L為擬陣。（詳見Topcoder）因M為擬陣，根據(jù)擬陣的性質(zhì)，我們可以把S中的元素從大到小按順序貪心考慮加入一個初始為空的集合T中，若不違背必勝的狀態(tài)就加入。答案即為沒有加入集合T中的元素和。此算法可通過100%的測試點。棋盤游戲這題在考

2、場上不容易想到正確思路。但是同上題一樣，此題也沒有輸出DRAW的情況（若A不能在第一回合干掉B，則B必勝，原理同象棋中的卒與馬，B只須把A往角落中趕即可）。模擬驅(qū)趕的過程？怎么模擬？考場中有人寫模擬得了此題的最高分，通過了44%的測試點。此題為博弈論，找N/P態(tài)即可。定義tijxy5維狀態(tài)，表示A在（i，j），B在（x，y），當(dāng)t=0時表示為A先手，否則為B先手。根據(jù)狀態(tài)的轉(zhuǎn)移建圖，當(dāng)i=x且j=y時為最初的P態(tài)，將所有一步操作能進入P態(tài)的標(biāo)記為N態(tài)，如果從某個狀態(tài)開始的所有一步操作都只能進入N態(tài)，則標(biāo)記為P態(tài)。用F表示此狀態(tài)為N/P，G表示達到此狀態(tài)所需的步數(shù)（倒推的）。當(dāng)為時，當(dāng)前狀態(tài)的G

3、取能到達的狀態(tài)中G的最小值+1。（盡快獲勝）當(dāng)為時，當(dāng)前狀態(tài)的G取能到達的狀態(tài)中G的最大值+1。（拖延時間）最后看初始狀態(tài)的F判斷輸贏，G判斷步數(shù)。此算法可通過100%的測試點。二進制A+B統(tǒng)計A中有多少1，B中有多少1，C中有多少1，暴力枚舉A中1放的位置，B中1放的位置，相加計算C是否1剛好有那么多。若剛好有那么多1且位數(shù)不超過最大位數(shù)，比較出最小的C，即為答案。此算法可通過44%的測試點。數(shù)位DP。定義 tijkp5維狀態(tài)，F(xiàn)為此狀態(tài)下的最小C值，從低位枚舉，表示枚舉到第t位，A已放i個1，B已放j個1，C已放k個1，若p=0，表示該狀態(tài)無進位；否則表示有進位。同時枚舉第t位時A和B放0

4、還是1，結(jié)合上一位的進位，算出該位是否有進位與C該位上為0還是1。設(shè)該位上A、B與上次進位之和為res，則有fti+xj+yk+(res&1)res1 = Min(ft-1ijkp+(res&1)(t-1)，x，y為0或1。此算法可通過100%的測試點。圖的逆變換此題為本次省選中最簡單的一題，但是AC率卻很低，可能是大家把模型想復(fù)雜了。原圖中的一條邊為新圖中的一個點，原圖中兩條相接的邊為新圖中的一條邊，即ab為點ab，abc為abbc。題目要求根據(jù)新圖判斷是否存在一個原圖。設(shè)新圖中ab出發(fā)可達bc(1)、bc(2)、bc(i)、bc(n)。則對于bc(i)和bc(j)，若其它任意一個點對于這兩個點都是可達或不可達，則存在原圖；若存在一個點對于這兩個點一個可達一個不可達，則不存在原圖。此算法可通過100%的測試點。新數(shù)獨搜索題。仔細處理輸入?？上葘?*3的小