DAY2 每日5題

前情提要：請(qǐng)移步www.luogu.com.cn/blog/zhaoyihang/day-two/

---------------------------------------------------------------------------------------------------------------------

tips:還沒(méi)更完，丟個(gè)鏈接先

P1031 [NOIP2002 提高組] 均分紙牌

題目大意:

有N堆牌，一定能均分成N份，其中除了1號(hào)堆與N號(hào)堆以外，都可以向左或向右的相鄰牌堆任意移動(dòng)牌，1號(hào)堆只能向右移動(dòng)牌，N號(hào)堆只能向左移動(dòng)牌

現(xiàn)給出N和N堆牌的牌數(shù)，求使用最少的移動(dòng)次數(shù)可讓每堆牌的個(gè)數(shù)相同

當(dāng)然，你可以倒著來(lái)，也可以正著來(lái)

但是需要注意的是，在移動(dòng)的過(guò)程中，某個(gè)牌堆里的數(shù)可能為負(fù)，但是我們可以先假設(shè)他成立，再?gòu)挠疫吶∨品胚M(jìn)該牌堆中

為了方便，我們只維護(hù)a[i]的右邊元素

$tips:$也并不存在到第N個(gè)的時(shí)候N != aeg 因?yàn)橹灰覀兦懊娴牟襟E正確，N的值就一定正確

題目分析

我們可以將本題分成幾個(gè)小部分:

1、讀入牌堆

2、處理牌堆，計(jì)算答案

3、輸出答案

1、讀入牌堆

2、處理牌堆，計(jì)算答案

牌堆與牌堆之間的狀態(tài)無(wú)非就3種:

代碼實(shí)現(xiàn):

3、輸出答案

完整AC代碼

一定要記得初始化變量，筆者寫(xiě)的時(shí)候沒(méi)有初始化，導(dǎo)致一直輸出4，心態(tài)快炸掉了

P1036 [NOIP2002 普及組] 選數(shù)

本題的題解區(qū)千萬(wàn)不要看

我也不太會(huì)這個(gè)題，如會(huì)！

數(shù)據(jù)范圍：

不同尋常的我將數(shù)據(jù)范圍先寫(xiě)到了前面

1≤n≤20,k<n

看這個(gè)數(shù)據(jù)范圍，可能用dfs

題目大意:

給定n個(gè)整數(shù)，求其中的k個(gè)整數(shù)之和，求出和為質(zhì)數(shù)的數(shù)的個(gè)數(shù)

可以使用搜索的方式來(lái)解

搜索寫(xiě)法

完整AC代碼

P1060 [NOIP2006 普及組] 開(kāi)心的金明

一眼背包

開(kāi)玩笑的，這題筆者也是如會(huì)的狀態(tài)

題目大E：

物品有價(jià)值v[j]和重要度w[j],那價(jià)值就是v[j]?w[j],金明想買(mǎi)走價(jià)格盡可能高的物品

輸入總錢(qián)數(shù)與希望購(gòu)買(mǎi)的物品個(gè)數(shù)

輸出能購(gòu)買(mǎi)的物品信息：物品的v[j]與w[j]

題目分析：

這道題可以轉(zhuǎn)換為背包問(wèn)題，盡可能拿走多的價(jià)值

核心部分就這些:

完整AC代碼：