noip模拟題題解集

最近做模拟題看到一些好的題及題解。

升格思想：

核電站問題

一個核電站有N個放核物質的坑，坑排列在一條直線上。如果連續M個坑中放入核物質，則會發生爆炸，于是，在某些坑中可能不放核物質。

任務：對于給定的N和M，求不發生爆炸的放置核物質的方案總數

輸入：輸入檔案隻一行，兩個正整數N，M( 1<N<50，2≤M≤5)

輸出：輸出檔案隻有一個正整數S，表示方案總數。

運用升格思想。設N個坑不會發生爆炸的方案數是f[N]，那麼我們假設N以前的坑的方案

都已知了，那麼我們隻需要考慮第N個坑如何放即可（順序是從左到右）。我們考慮兩種情況：

1、當N這個坑放入物質，那麼有兩種可能，一種是因為之前放了連續的m-1個，現在放了就會爆炸，那麼這種情況有f[N-1-m]種情況，這是要剪掉的。一種是不會發生爆炸，那麼方案數就是f[N-1]。是以這個坑放入物質的方案有f[N-1]-f[N-1-m]。

2、當N這個坑不放入物質，那麼方案直接就是f[N-1]。

是以f[N]=f[N-1]+f[N-1]-f[N-1-m]

其中f[0]=f[-1]=1

動态規劃：最優化問題第一應該要想到動歸

鷹蛋實驗

在ural大學的一個教授的别墅上有一鷹巢。教授對這個鷹巢很感興趣。經過仔細觀察，他發現鷹巢中有若幹枚蛋。于是他想利用這些蛋做一個試驗。測試一下蛋的堅固程度。

這些蛋應該是具有相同的堅硬度。存在一個非負整數E，如果從樓的第E層往下扔蛋，但不會破，但如果從第E＋1層（包括高于E＋1層）扔，蛋就會破。你要做一組試驗，來找出E。最簡單的方法是一層層試。但是你有多個蛋試，不必用笨方法，可以用更少的次數找出E。注意這裡的次數都是指對你的方法的最壞情況且蛋破了就不能再用，還有E可以取0。

如果實驗到了最高層蛋還不破，則認為E取最高層的層數。

輸入：一行，蛋的個數n和樓的層數n，k<=1000。（中間一個空格）

輸出：最少實驗次數。

第一次試驗有10種選擇——1到10層

如果選第3層，最壞情況下當然E!=3，如果E<3，蛋就碎了（關鍵！），那麼還需要a[2][1]次

如果E>3，那麼還需要a[7][2]次，由于考慮最壞情況，取兩個的最大值，再加1

如果n層樓，m個蛋，其實就是

for(i=1;i<=n;i++) a[n][m]=min{1+max{a[i-1][m-1],a[n-i][m]}}

當然還要注意剪枝。

1000層樓，最多需要10個蛋

木棒分組

【題目描述】

有 n 根木棒,你需要将它們分成盡量多的組,滿足每組木棒長度和相等。你不能将木棒砍斷。輸出最優方案下一組中木棒長度之和。

【輸入格式】

第一行一個整數 n。接下來 n 個整數,表示 n 根木棒的長度

【輸出格式】

一行一個整數,表示木棒長度之和

【樣例輸入】

4

2 5 3 4

【樣例輸出】

7

【資料範圍】

70%的資料保證 n<=8

100%的資料保證 n<=50

這題資料很小我們可以考慮枚舉組數（顯然<=50，且能整除sigma(a[i])），然後因為對于組量，我們不需要考慮順序，隻需要考慮是否能夠有足夠的元素分成一組即可（但是要用最少的元素），是以我們用01背包來dfs，每一次就判斷是否能在剩餘的元素中找盡量少的元素比對到sum/組數這個值。一定要注意初始化，因為這個問題我調試了老半天。。

拓展歐幾裡得是y-=a/b*x啊啊啊啊。不是y-=x*a/b啊啊啊，是取下界！！！！！

寂寞的程式員

【題目描述】

有兩個寂寞的程式員 J 和 Y,J 說他可以兩分鐘敲 8000 字,Y 說不信,于是 J 與 Y的 4kb/min 機器人進行了一場打字比賽。機器人以勻高速敲着亂碼,而 J 找到了幫他超越手速的鍵:CTRL。J 可以花不同的時間進行以下操作:

1. 敲一個字元

2. 按 CTRL-A

3. 按 CTRL-C

4. 按 CTRL-V

(具體效果請在記事本内實驗)

你需要制定一個操作順序,使得 J 在 n 毫秒内輸入的字元數最多。

【輸入檔案】

第一行五個整數 n cost input cost CtrlA cost CtrlC cost CtrlV ,四個cost分别對應進行四個操作需要耗費的毫秒數

【輸出檔案】

一行一個整數,表示能夠輸入的最多字元數

【樣例輸入】

14 10 1 1 1

【樣例輸出】

2

【資料範圍】

30%的資料保證 n ≤ 10

100%的資料保證 1 ≤ n ≤ 1,000; 1 ≤ cost ≤ n

這題的dp我一開始就想錯了QAQsad。。我們隻需要設狀态d[i]表示i時刻最多能打的字，然後d[i]=max(d[i-ctrla-ctrlc-ctrlv-j*ctrlv]*(j+1))即可。。這個自己多想想吧，很容易的。是以以後我們看到諸種類型的題，即一個操作對其它的操作有依賴，那麼直接将這些操作看做整體來做（但是要從頭到尾掃一遍更新）

帶*号的公共字串比對

有串A和B，其中A中帶*号的字元表示這個地方可指派任意串（包括空串），問是否可以比對A和B

設狀态d[i,j]表示A中前i和B中前j是否能被比對，則

d[1,0]=true 當 A[1]=’*’

d[0,0]=true

d[i,j]=d[i-1,j-1], A[i]==B[j]

d[i,j]=d[i-1,j-1] || d[i-1,j] || d[i,j-1], A[i]!=B[j]

狀态壓縮：

驢友

有一批驢友在深山中探險,他們來到了一個山洞的洞口。所有驢友都必須穿過這個山洞。可是山洞太窄,他們無法同時穿過山洞。是以,他們隻能分成小組分别穿越山洞。然而,他們隻有一個手電筒。是以一組人穿越山洞後,必須有人帶着手電筒回來,直到最後一個人穿越山洞。

山洞中有座橋,每次穿越山洞的人必須同時過橋。然而,橋的承重量有限,不能承受超過m的品質,否則橋會垮掉。每個人的體重事先已經知道了。可以有單獨一個驢友穿越山洞。當然,如果同時穿越山洞的小組人數多于一人,則每個人都必須至少要有另外一個他信任的人也在這個小組中。給定一個鄰接矩陣T,T[i,j]等于”Y”則表示i信任j,否則i不信任j。每個人行走的速度不盡相同,是以一組人走的時候,按照其中走的最慢的人的速度行進。你已經知道了每個人分别穿越山洞所需的時間。請你求出,所有人都通過山洞所需的最小時間。如果不可能穿越山洞,輸出-1。

【輸入檔案】

第一行兩個整數n,m,表示總人數和橋的承重量。

接下來一行有n個整數,表示每個人的品質。接下來一行有n個整數,表示每個人通過山洞所需時間。

接下來是一個n×n的字元矩陣,隻有‘Y’和‘N’兩種字元,表示信任矩陣。

【輸出檔案】

一個整數,表示最小時間,戒者-1 表示無解。

【資料範圍】

1 ≤ n ≤ 13 , 1 ≤ m ≤ 5000

看到n<=13就應該要想到狀壓。我們考慮兩種狀态，狀态一和狀态二。都表示目前人的情況。隻不過狀态一是表示還沒進洞，狀态二表示已經進洞。那麼狀态一轉移到狀态二顯然就是兩個狀态的交這些人進了洞（反過來也行）。是以我們預處理所有的兩邊的可能情況，然後算出每種情況的最小費用，那麼就在這些狀态上連邊。最後從沒進洞的狀态（所有人）跑一遍最短路，答案就是進洞的狀态（所有人）。

以後看到資料範圍<=15，可以優先想狀壓。

最短路：

逃生

小 J 在一次旅行中感染了一隻可以分裂細菌,這種細菌在出現一分鐘後會分裂成兩隻相同重量的細菌,其中一隻不再分裂,另一隻在一分鐘後繼續分裂。小 J 想盡快找到殺菌草藥,然而可供行走的路并不多。山裡共有 n 個水池與 m 條路,每條路連接配接兩個水池,走過這條道路需要花費一定的時間。小 J 感染時在 s 号水池,殺菌草藥生長在 t 号水池裡。小 J 每經過一個水池時都要喝一口水來補充體力,但是細菌也會産生變化:現存所有細菌都會合體為一隻,重量為所有細菌重量之和,合體一分鐘後繼續分裂。然而,小 J 并不知道這一點,每經過一個水池,他依然會去喝水。你需要為小 J 畫出一條從 s 号水池到 t 号水池的路線,使得小 J 到達 t 号水池時身上的細菌重量最小。資料保證有且隻有一組解。

【輸入格式】

第一行四個整數 n m s t

接下來 m 行,每行三個整數 l r w,表示 l 号水池與 r 号水池間有一條道路,花費為 w 分鐘(喝水不花費時間)。同一對 l r 之間可能有多條道路

【輸出格式】

第一行一個整數 k,表示路線長度

接下來一行 k 個整數,依次表示你畫出的路線中經過的每個點

【樣例輸入】

4 4 1 4

1 2 0

1 3 2

3 4 1

2 4 4

【樣例輸出】

3

1 2 4

【資料範圍】

30%的資料保證 n ≤ 50; w ≤ 10

100%的資料保證 2 ≤ n ≤ 10000; 1 ≤ m ≤ 30000; 0 ≤ w ≤ 1000; s ≠ t; l ≠ r

很顯然一下就能轉換成 d[v]<=d[u]+d[u]*w[u, v]的三角不等式。但是對于這種資料，顯然是會爆表的。。。。。我們考慮這樣，

d[v]<=d[u]*(1+w[u, v]) -> 

log(d[v])<=log(d[u]*(1+w[u,v])) ->

log(d[v])<=log(d[u])+log(1+w[u,v])

那麼我們直接将邊權變成log然後相加就行了

分數規劃：

越獄

【題目描述】

某監獄有一排 n 個連續的房間,每個房間有硬度不一的鐵門,也關着個數不一的囚犯。一天,這些囚犯為了實作夢想而想籌劃越獄,他們準備讓一段連續的房間裡的人沖出鐵門控制獄卒,成功的可能性定義為暴動人數/鐵門硬度和。為了分散獄卒注意力,暴動房間數不能少于 L。你作為獄卒裡的内奸,需要制定一個成功的可能性最大的方案。若有多組解,輸出任意一種。

【輸入格式】

第一行兩個整數 n L

第二行 n 個整數,第 i 個整數a i 表示第 i 個房間裡的人數

第三行 n 個整數,第 i 個整數b i 表示第 i 個房間的鐵門的硬度

【輸出格式】

一行兩個整數 s t,表示讓s~t(包含 s,t)号房間的人暴動。

【樣例輸入】

3 2

1 2 3

3 2 1

【樣例輸出】

2 3

【資料範圍】

30%的資料保證n ≤ 1,000100%的資料保證1 ≤ L ≤ n ≤ 100,000; 1 ≤ a i , b i ≤ 10,000

其實一開始看到除法我就想到了分數規劃，但是不知道如何計算f(t)>=0。。。。

其實很簡單。。。。我們處理好所有a[i]-d*b[i]後，隻需要找>=L的區間的最大值即可。。。

而且O(n)就可以解決。。。就是維護一個字首和，隻需要每次維護一個最小字首和（根據sum[r]-sum[l-1]要最大嘛）然後在維護最大值。然後不要寫錯check啊。。。我的check的傳回值是bool然後在二分裡判斷check是<-eps。。。。Sad。。

說明區間給定長度求最值可以用字首和實作O(n)

分數規劃的話，還是老實自己推：

設B=sigma(a[i]*x[i])/sigma(b[i]*x[i])的b是最值（即最優解），這裡的x[i]表示第i個是否選擇，且a[i]和b[i]都是已知的。

我們設F(A)=sigma(a[i]*x[i])-A*sigma(b[i]*x[i])

當F(A)>0時（假設現在是求最大值B），我們發現

sigma(a[i]*x[i])-A*sigma(b[i]*x[i])>0 即存在一種方案X使得

sigma(a[i]*x[i])/sigma(b[i]*x[i])>A，那麼顯然這時左式比A要優，那麼A式就可以直接使用它（說明對于A來說，有更優的解，在二分裡邊的解釋就是，F(mid)>0那麼l=mid，即逼近下界）

我們再看一下F的變形

F(A)=sigma(a[i]*x[i])-A*sigma(b[i]*x[i])

=sigma((a[i]-A*b[i])*x[i])

顯然a[i]-A*b[i]是可以直接求出來的，那麼問題轉化為求出一種方案X使得F(A)>0，

最小值的話同理

數論：

有限小數

【題目描述】

小 J 是一個嚴謹的人,他隻能接受有限小數,而總有些數令他不爽,比如0.3 。一天,他發現0.3 在 3 進制下可以寫成 0.1,在 30 進制下可以寫成 0.A 等(A(30) = 10(10))。于是他堅信所有有理數都可以寫成有限小數。然而,不斷切換進制是很麻煩的工作,現在小 J 需要處理若幹有理數,你需要告訴他最少需要幾進制才能使它們都能寫成有限小數。

【輸入格式】

第一行一個整數 n。接下來 n 行,每行兩個十進制整數 a b,表示一個分數

a

b

【輸出格式】

一行一個十六進制整數,表示最小進制數

【樣例輸入】

2

1 33

1 99

【樣例輸出】

21

【資料範圍】

100%的資料保證n ≤ 1,000; 1 ≤ a, b ≤ 100,000,000

設r = p1*p2*..*pk (pi為互不相等的質數)

設B = {b|b=p1^t1*p2^t2*..*pk^tk (ti>=0)}

充分性：對于任意b∈B，a/b可以在r進制下寫成有限小數

必要性：對于任意c∉B，既約分數a/c不能在r進制下寫成有限小數

printf(“%X”)的%X通配符可以直接輸出16進制數。

計數：計數的話不是組合計數就是遞推計數，注意好遞推計數的抽象！

錯排公式

當n個編号元素放在n個編号位置，元素編号與位置編号各不對應的方法數用D(n)表示，那麼D(n-1)就表示n-1個編号元素放在n-1個編号位置，各不對應的方法數，其它類推.

第一步，把第n個元素放在一個位置，比如位置k，一共有n-1種方法；

第二步，放編号為k的元素，這時有兩種情況：

⑴把它放到位置n，那麼，對于剩下的n-1個元素，由于第k個元素放到了位置n，剩下n-2個元素就有D(n-2)種方法；

⑵第k個元素不把它放到位置n，這時，對于這n-1個元素，有D(n-1)種方法；

綜上得到

D(n) = (n-1) [D(n-2) + D(n-1)]

特殊地，D(1) = 0, D(2) = 1.

Stirling數

第一類Stirling數是有正負的，其絕對值是n個元素的項目分作k個環排列的方法數目。常用的表示方法有s(n,k),[nk]。

換個較生活化的說法，就是有n個人分成k組，每組内再按特定順序圍圈的分組方法的數目。例如s(4,2)：

{A,B},{C,D}

{A,C},{B,D}

{A,D},{B,C}

{A},{B,C,D}

{A},{B,D,C}

{B},{A,C,D}

{B},{A,D,C}

{C},{A,B,D}

{C},{A,D,B}

{D},{A,B,C}

{D},{A,C,B}

這可以用有向圖來表示。

給定s(n,0)=0,s(1,1)=1，有遞歸關系s(n+1,k)=s(n,k−1)+ns(n,k)

遞推關系的說明：考慮第n+1個物品，n+1可以單獨構成一個非空循環排列，這樣前n種物品構成k-1個非空循環排列，方法數為s(n,k-1)；也可以前n種物品構成k個非空循環排列，而第n+1個物品插入第i個物品的左邊，這有n*s(n,k)種方法。

即s(n,k)=s(n-1,k-1)+(n-1)*s(n-1,k)

第二類Stirling數是n個元素的集定義k個等價類的方法數目。常用的表示方法有S(n,k),S(k)n,{nk}。

換個較生活化的說法，就是有n個人分成k組的分組方法的數目。例如有甲、乙、丙、丁四人，若所有人分成1組，隻有所有人在同一組這個方法，是以S(4,1)=1；若所有人分成4組，隻可以人人獨立一組，是以S(4,4)=1；若分成2組，可以是甲乙一組、丙丁一組，或甲丙一組、乙丁一組，或甲丁一組、乙丙一組，或其中三人同一組另一人獨立一組，即是：

{A,B},{C,D}

{A,C},{B,D}

{A,D},{B,C}

{A},{B,C,D}

{B},{A,C,D}

{C},{A,B,D}

{D},{A,B,C}

是以S(4,2)=7。

給定S(n,n)=S(n,1)=1，有遞歸關系S(n,k)=S(n−1,k−1)+k*S(n−1,k)

遞推關系的說明：考慮第n個物品，n可以單獨構成一個非空集合，此時前n-1個物品構成k-1個非空的不可辨識的集合， 方法數為S(n-1,k-1)；也可以前n-1種物品構成k個非空的不可辨識的 集合，第n個物品放入任意一個中，這樣有k*S(n-1,k)種方法。

轉載于:https://www.cnblogs.com/iwtwiioi/p/4065717.html