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

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

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

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

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