前言

2017.12.10,浙江中醫(yī)藥大學(xué)主辦了一場acm賽制的比賽（浙江中醫(yī)藥大學(xué)第十一屆程序設(shè)計競賽），而我和我們學(xué)校（杭州二中白馬湖學(xué)校）的另外兩名同學(xué)組成一隊也去參加了，這是我打的第一場acm比賽，和傳統(tǒng)的oi比賽不同，acm賽制的形式不一樣，題目類型也不一樣。

規(guī)則介紹

這場比賽的規(guī)則和傳統(tǒng)acm大致相同，只是在時間的方面不一樣。這場比賽一共四個小時（傳統(tǒng)五個小時），有11題編號分別為a~k。比賽以隊伍的形式參加，人數(shù)為1~3人，每隊只能使用一臺電腦。每a掉1題就可以獲得1個氣球，不同的題目有不同顏色的氣球，另外的，每一題的一血隊伍能獲得一個金色帶著題號的氣球。

比賽進行時

一開始，我們商定好了每個人開哪幾個編號的題目，我要開的是C題，一看到題目，我就有了思路，于是先開始打了起來

C題（尋找zcmu）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=2
題意簡介：多組數(shù)據(jù)，每組數(shù)據(jù)一個長度不超過100000的字符串，讓你在其中找到一種方案，刪去最少的字符時得串中出現(xiàn)一段連續(xù)的字符“zcmu”。
解決方法：顯然這是一道dp題，dp[i][j]表示終點為i，包含目標(biāo)串的前j個字母的最靠后的起點位置，滾動一維數(shù)組，就很好寫啦

當(dāng)然，最后我A掉了C題
在我打C題的過程中，另外兩名隊員先大致看了一遍其它的題，找到了2道水題，一道是E題，一道是G題

E題（Pizza）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=4
題意簡介：很玄乎的題目，但是只要分析以后就可以發(fā)現(xiàn)答案其實就是輸出輸入的k，多組數(shù)據(jù)
解決方法：對于每組數(shù)據(jù)輸入一個整數(shù)，輸出這個數(shù)

G題也很水

G題（特產(chǎn)）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=6
題意簡介：一個人出游時空箱子重量為a,回來時重量為b，問他在旅游過程中買了多重的東西，輸入2個實數(shù)，輸出一個整數(shù)
解決方法：用double讀入，輸出時用.0lf就好了，這是b-a problem

隨后我們由一位同學(xué)來打樹鏈剖分的一道模板題A題

A題（不存在的樹）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=0
題意簡介：樹上的路徑上求max、求和并支持單點修改
解決方法：樹鏈剖分

那位同學(xué)很給力，這一題也A了
在那位同學(xué)打A題代碼的時候，我和另外一個同學(xué)推出了B題

n(n<=1?1019)，求一個最小的大于n的b滿足2?a?(a+1)2=b2(a,b∈Z)
解決方法：即要滿足2?a?(a+1)2是完全平方數(shù)，那么顯然a一定滿足a=2?x2(x∈Z)可以發(fā)現(xiàn)x和a的單調(diào)性相同，所以說只要二分這個x就好了，另外要注意的是要用unsigned long long，否則會爆，還有要特判0的情況，否則二分容易陷入死循環(huán)

接下來呢，我們又有一個同學(xué)一眼秒了J題

J題（序列）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=9
題意簡介：給定兩個長度為n(n<=100000)的序列a,b，讓你求有序數(shù)對<i,j><script type="math/tex" id="MathJax-Element-6"></script>的數(shù)量滿足ai=bj且gcd(i,j)=1
解決方法：經(jīng)典做法，用容斥，顯然只滿足第一個條件的很好統(tǒng)計，然后再減去gcd(i,j)大于1的滿足條件有序數(shù)對數(shù)量就好了

在后面，我們又切了F題

F題（開心的cc）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=5
題意簡介：多組數(shù)據(jù)，給定一個長度為n（n<=100000）的1、-1的串，串可以復(fù)制以后加到后面，求1~n中能作為起點滿足從起點開始的長度為n的串的前綴和為正
解決方法：考慮用一個單調(diào)隊列來維護前綴和的從小到大的值，若單調(diào)隊列的最小值大于0則計入答案即可

比賽過去三個小時了，有很多隊伍A掉了D題，然而我們隊卻還沒有，怎么辦呢，我們想了很久，一直沒有想出來，最后換了一個思路，最終做了出來

D題（cc的神奇背包）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=3
題意簡介：多組數(shù)據(jù)，你有一個背包，初始容量為v，你有n個物品（n<=1000），第i個物品需要占用ai的空間，并且如果成功放入，背包會多出bi的空間，問能否放入所有的的物品
解決方法：首先，如果某個物品的ai<=bi并且放的進去，那么就貪心的放進去，讓背包擴容，然后呢剩下的物品用倒推的方法，先計算出如果所有物品都成功放入最后背包還剩的體積vlas，那么倒推最后一個放的物品x，vlas一定大于等于bx，那么可以倒推vlas1位vlas-bx+ax，若發(fā)現(xiàn)不能倒推了且還有物品沒被用掉，那么就說明不行，否則就可以

最后我們隊還剩三題沒有A，分別是H、I、K，我H題可能會做了，我有一個同學(xué)會做K題，I題是一道字符串的比較繁的題
我就在說一下H題吧，至少我大致是會的

H題（剪紙）

題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=7
題意簡介：輸入n（4<=n<10），代表一個n*n的正方形，你要用一條折線把這個正方形分成面積相同的兩半，問方案數(shù)（旋轉(zhuǎn)相同算同一種方案）
解決方法：如果n是奇數(shù)，那么面積也是奇數(shù)，方案數(shù)為0，那么根據(jù)數(shù)據(jù)范圍也就是只要分別知道n=4、6、8時的方案數(shù)就好了，那么怎么算呢，可以爆搜，可是n=8時怎么辦呢，264顯然受不了啊，那么可以縮小問題規(guī)模
先說我的復(fù)雜度，是O（2(n?2)?n/2?(n?2)?n/2）的,當(dāng)n=8時復(fù)雜度為402653184，大概只要跑4s
首先呢先假設(shè)兩半的顏色一半黑一半白，那么靠兩邊各的一列分別都是一種顏色的，顯然不證。那么考慮只要搜中間的一大塊的一半就好了，另一半是中心對稱的，那么就指數(shù)枚舉，在加判斷，只要是所有黑色都和左邊聯(lián)通，所有白色都和右邊聯(lián)通，這個很好判斷，還有要注意的是盡管只枚舉了一半，但是還是要考慮上下的情況，這個也很好處理，連著前面的用并查集就好

剩下的題：
I題（Memory leak）題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=8
K題（追求者）題目網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1214&pid=8
有興趣的讀者可以去做一做哦

總結(jié)

感覺這一次三個人配合的很好，然后呢D題出的很慢，導(dǎo)致最后題目來不及碼代碼很可惜
這套題目給我的感覺是，如果能把題意轉(zhuǎn)化一下很多題目就不是那么難了
然后呢，打acm比賽團結(jié)協(xié)作很重要分配好時間和人力，這樣才能多拿分
總榜網(wǎng)址：http://acm.zcmu.edu.cn/JudgeOnline/contestrank.php?cid=1214
我們隊拿了rank6，可能罰時偏多了

總結(jié)

以上是生活随笔為你收集整理的参加浙江中医药大学第十一届程序设计竞赛（ACM赛制）的总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。