2008年浙江省賽ACM解題報告

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

A簡單題

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

B簡單題

直接bfs無向圖mst。

C中等偏難。

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

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

D難題。

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

E我出的題，簡單題。

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

F簡單題

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

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

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

H簡單dp。

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

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

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

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

J中等題

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

K中等題

O(n^3)的dp。枚舉兩行i,j再枚舉一列k。起初，用一個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簡單題

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