2008年浙江省賽ACM解題報(bào)告

2008年5月17日，在浙江大學(xué)成功舉行了浙江省第五屆大學(xué)生程序設(shè)計(jì)競(jìng)賽。本人的解題報(bào)告如下：

A簡(jiǎn)單題

因?yàn)閜的范圍很小才99所以從700-799就可以滿足全部要求了。可以打表出來，找出每個(gè)連續(xù)的一段滿足要求的數(shù)，保存起來（并且要求新存的段長(zhǎng)度比原先的要長(zhǎng)），打出一張表，對(duì)每個(gè)要求的數(shù)，2分答案。（把1-99的結(jié)果都保存好，直接輸出）。反正“轉(zhuǎn)折點(diǎn)”很少，怎么搞都可以。

B簡(jiǎn)單題

直接bfs無向圖mst。

C中等偏難。

給定直線，對(duì)每條直線，傳說解不等式組可以過，直接看是否存在一個(gè)點(diǎn)在直線之上。（左端點(diǎn)取max,右端點(diǎn)取min，如果左>=右，直接break掉）。有點(diǎn)ft...O(n^2)n=5000rp好的可以過....

我用的方法類似于凸包，先把所有直線按照斜率a由小到大排序，斜率相同取b較大的，扔掉b小的。于是所有直線斜率不同。準(zhǔn)備一個(gè)棧，棧里面存放上一次能看到的“最上面”的直線以及這條直線能看到的范圍x(x值右邊的部分可以被看到）。初始時(shí)，把斜率最小的直線入棧，并記錄x值為-inf。然后對(duì)第i條直線，所做的是用第i條直線和棧頂直線求交點(diǎn)x,如果這個(gè)x值不大于棧頂?shù)膞值，則把棧頂元素彈出，繼續(xù)求交，否則退出。這種判斷操作直到棧為空，或者當(dāng)前棧頂?shù)膞值大于棧頂?shù)膞值。然后把第i條直線入棧，繼續(xù)，看后面的直線。最后棧中的直線數(shù)就是能看到的。這種做法類似于凸包的方法，除去排序外，每條直線至多出入棧一次，復(fù)雜度O(n)。總復(fù)雜度是O(nlogn)。

D難題。

這題是比較有意思和有搞頭的題。應(yīng)該可以算壓軸題吧。題目意思不難，但是很難做。我想了好久，想出個(gè)方法，但是比vb的方法難一些。其實(shí)可以貪心。首先集合大小為1時(shí)，沒法搞，直接判斷掉。我們把A集合和B集合里的數(shù)都由小到大排序。要移動(dòng)元素并且保證代價(jià)，那么可以選擇的操作方法是A和B交換一些元素，然后A再給B(或者B再給A)若干個(gè)元素。我們只討論最后A再給B若干個(gè)數(shù)的情形，B給A的可以類似討論。那么設(shè)A和B交換的個(gè)數(shù)為x,（注意交換完后，A和B仍然還各有n個(gè)元素），最后A再給B的元素個(gè)數(shù)為i,因?yàn)椴荒芮蹇誂,所以0<=i<n。如果枚舉i，再枚舉x，則復(fù)雜度要到O(n^2)，n=20000,不可忍受?？紤]整個(gè)過程：A先把最小的x個(gè)和B中最大的x個(gè)交換，然后A再繼續(xù)把原來其中的最小的i個(gè)給B。（移動(dòng)進(jìn)來的元素不準(zhǔn)再移動(dòng)出去，因?yàn)闀?huì)浪費(fèi)代價(jià)）。那么從效果上考慮，A把最小的（x+i）個(gè)元素給了B,B把最大的x個(gè)元素給了A。那么我們完全可以把這個(gè)過程變?yōu)锳先給Bi個(gè)元素，然后再和B交換x個(gè)元素，這樣可以達(dá)到相同的效果。但是這樣的好處是，A和B開始交換時(shí)是從A的第i個(gè)元素和B的第(n-1)個(gè)元素開始的。（下標(biāo)都是從0開始）。那么這樣交換多少個(gè)才“劃算”呢？即如何確定x呢？顯然，交換的次數(shù)并非越多越好。我們只要交換到A中最小元素比B中最大元素大就可以停止交換了。于是可以預(yù)先搞一個(gè)數(shù)組ca[j]表示從A的第j個(gè)元素開始和B的第(n-1)個(gè)元素開始交換，最多交換多少次是“劃算”的。即找到第一個(gè)滿足a[j+ca[j]]>b[n-1-ca[j]]的位置（如果不存在這樣的位置顯然ca[j]=n-j）因?yàn)閍b都是排序好的，所以ca[j]這個(gè)值可以2分出來，（同理可以算出cb[j],表示a[cb[j]]>b[j-cb[j]]的第一個(gè)位置)。前面排序再預(yù)處理求cacb的時(shí)間復(fù)雜度為O(nlogn)。然后，我枚舉i后，至少需要的代價(jià)是i*(i-1)，由給定的cost可以確定至多交換的次數(shù)是(cost-i*(i-1))/2,然后由“劃算”的程度，決定交換的次數(shù)至多是ca[i]，于是這兩個(gè)值取min,就是交換的次數(shù)。這樣交換的次數(shù)可以由i求出來，并且此時(shí)A中最小值應(yīng)該是min(換進(jìn)來的最小值,第一個(gè)沒被換出去的值），B中的最大值應(yīng)該是max(換進(jìn)來的最大值,尾端第一個(gè)沒被換出的值)，這些都很容易求，于是可以求出題目中的N和M,枚舉i值，取N-M最大的即可。（再類似考慮B給Ai個(gè)，再循環(huán)一次，取最大值就好了）。后面枚舉的復(fù)雜度是O(n)。（預(yù)處理ca,cb后，循環(huán)里所有操作是O(1)的）因此，總時(shí)間復(fù)雜度O(nlogn)。

E我出的題，簡(jiǎn)單題。

沒有太多好說的，直接硬搞就行。原題的輸出要求比這個(gè)麻煩得多，是要輸出(f(x))'=g(x)的，這就有對(duì)系數(shù)為1和0的輸出處理，以及指數(shù)為0和1的處理。題目簡(jiǎn)化了，沒什么注意的地方了。

F簡(jiǎn)單題

找最大最小值，沒什么好說的。

G我出的題，可以認(rèn)為是簡(jiǎn)單模擬。

直接打表10^9是顯然不可行的。其實(shí)我認(rèn)為最簡(jiǎn)單的做法，是預(yù)map所有不超過1000的數(shù)的讀法和阿拉伯?dāng)?shù)，這樣讀數(shù)可以分3節(jié)處理。注意一下and,zero等就好了。輸出直接輸出數(shù)字沒有逗號(hào)。-.-

H簡(jiǎn)單dp。

背包....注意體力可以為0，滿了不能再超。

I比較復(fù)雜的模擬

稍微有點(diǎn)復(fù)雜，但不是難到做不了，我寫的代碼210+行。大部分在解析xml。當(dāng)然采取了偷懶的方法，如tag只看“<”里第一個(gè)非空白的字母（或前2個(gè)字母），頻繁使用isdigit,isspace等庫函數(shù)。然后當(dāng)解析到rule或者default時(shí)，用strstr看里面是否有interval=和wait=的字樣，如果有再用*10法處理數(shù)字。我并沒假設(shè)“=”后面一定有引號(hào)，所以處理數(shù)字前是從“=”后面第一個(gè)是數(shù)字的處理到連續(xù)數(shù)字后面第一個(gè)非數(shù)字的。還有不管什么東西，我把XML里的所有字母都tolower了一次。（轉(zhuǎn)換成小寫字母了）。還有一點(diǎn)注意的是tag間的空白不能隨便忽視。比如之間的字符全都有用（包括空格），也就是說從一個(gè)tag的“>”開始讀到下一個(gè)tag的“<”結(jié)束。這樣就處理好了XML。

然后對(duì)處理看到的帖子，對(duì)每個(gè)時(shí)間，（不是第一個(gè)帖子的話）分析看到這個(gè)帖子的時(shí)間加上wait值和上次發(fā)貼時(shí)間加上上次保存的interval值是否不小于當(dāng)前的時(shí)間。如果是，則可以發(fā)貼，保存發(fā)帖時(shí)間，更新interval?？雌饋砭瓦@么簡(jiǎn)單。但是我認(rèn)為還是有2點(diǎn)要注意的：（1）關(guān)于時(shí)間，題目上說看到的帖子是按時(shí)間先后排序的，2個(gè)帖子時(shí)間間隔小于24小時(shí)，也就是說，單看hh:mm:ss，可能后面的時(shí)間小于前面的時(shí)間時(shí)，這就是下一天的時(shí)間了。（按題目描述應(yīng)該沒有恰好24小時(shí)的情況，不過如果有的話，我簡(jiǎn)單地把第個(gè)時(shí)間忽略掉），我采取處理時(shí)間的方法是絕對(duì)時(shí)間，就是把時(shí)間通過hh*3600+mm*60+ss，轉(zhuǎn)換成秒，然后看這個(gè)值%(一天的秒數(shù)）是增大還是減小了，然后決定加上多少來保證時(shí)間的單調(diào)遞增，輸出時(shí)還要轉(zhuǎn)換成hh:mm:ss的形式(2)輸入關(guān)于格式，題目后半部分的輸入格式，hh:mm:ss后面一定有一個(gè)空格不算做發(fā)帖內(nèi)容,這在匹配發(fā)帖內(nèi)容時(shí)至關(guān)重要。（也許要匹配規(guī)則中可能包含首空格）在效率上，我使用的是getchar()，估計(jì)被gets要高一些吧。:)

J中等題

比較顯然的矩陣乘方。用O(nlogn)的求冪方法即可。有一點(diǎn)注意題目中的K=0時(shí)（沒有從該容器倒水的規(guī)則），并不是把其中的水都到出去，而是它其中的水始終保持不變。（若第p個(gè)容器K=0，則與輸入的是1,下一行是p，等價(jià)）

K中等題

O(n^3)的dp。枚舉兩行i,j再枚舉一列k。起初，用一個(gè)ans=0表示結(jié)果，設(shè)a[c]表示設(shè)定i,j后截止到當(dāng)前列，i,j行的位置都是第c種福娃的列數(shù)。(c=0,1,2,3,4)。每當(dāng)循環(huán)k前，先把a(bǔ)數(shù)組都清0。mat為輸入矩陣，然后循環(huán)k,如果mat[i][k]==mat[j][k]，設(shè)mat[i][k]為第c種福娃，則總數(shù)ans顯然應(yīng)該加上a[c]（前面那些列都可以和當(dāng)前列構(gòu)成滿足要求的矩陣的），并且a[c]數(shù)加1。最后ans為所求。

L簡(jiǎn)單題

可能圖看不大清楚。其實(shí)點(diǎn)光源到（x,y,z)到它在z=0平面的投影點(diǎn)的光強(qiáng)度最強(qiáng)，然后隨著它在z=0平面投影點(diǎn)為圓心的同心圓由里到外強(qiáng)度逐漸減弱，點(diǎn)光源(x,y,z)