noip相關(guān)信息競(jìng)賽共享

貪心策略貪心方法的基本思想

貪心是一種解題策略，也是一種解題思想使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)利用貪心策略解題，需要解決兩個(gè)問題：該題是否適合于用貪心策略求解如何選擇貪心標(biāo)準(zhǔn)，以得到問題的最優(yōu)/較優(yōu)解引入:排隊(duì)打水問題有N個(gè)人同時(shí)排隊(duì)到R個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間為T1，T2，…，Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們所有人打水的時(shí)間總和最少？說明：每個(gè)人打水的時(shí)間包含他等待的時(shí)間。分析由于排隊(duì)時(shí)，越靠前面的計(jì)算的次數(shù)越多，顯然越小的排在越前面得出的結(jié)果越?。梢杂脭?shù)學(xué)方法簡(jiǎn)單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：將輸入的時(shí)間按從小到大排序；將排序后的時(shí)間按順序依次放入每個(gè)水龍頭的隊(duì)列中；統(tǒng)計(jì)，輸出答案。例1排序機(jī)器(Sort)有一個(gè)機(jī)器叫做排序機(jī)，他可以對(duì)一個(gè)無序序列排序。它有兩種操作，一種是將某個(gè)數(shù)，放到第一位；還有一種是將某個(gè)數(shù)放到最后一位。比如對(duì)于序列： {8,12,25,7,15,19} MOVEFRONT7{7,8,12,25,15,19} MOVEBACK25{7,8,12,15,19,25}

于是整個(gè)序列就排好序了?，F(xiàn)在請(qǐng)你寫個(gè)程序，計(jì)算某個(gè)序列需要最少多少次操作，才能變成從小到大排好序的序列。輸入格式

第一行一個(gè)數(shù)N，表示有N個(gè)元素有待排序。

第二行N個(gè)數(shù)，用空格隔開，表示要排序的N個(gè)數(shù)。

輸出格式

一行一個(gè)數(shù)表示需要的操作次數(shù)。排序機(jī)器(Sort)輸入樣例 6 8122571519

輸出樣例 2數(shù)據(jù)規(guī)模

對(duì)于30%的數(shù)據(jù)N≤50；

對(duì)于60%的數(shù)據(jù)N≤1000；

對(duì)于100%的數(shù)據(jù)N≤100000，要排序的每個(gè)數(shù)都不相同。分析首先可以發(fā)現(xiàn)一個(gè)顯然的結(jié)論：只要合理移動(dòng)，每個(gè)數(shù)最多移動(dòng)一次（因?yàn)槿绻粋€(gè)數(shù)移動(dòng)了超過一次，那么只有最后一次移動(dòng)是有效的）那么我們就要找到最大的不動(dòng)點(diǎn)集，假設(shè)為集合x，考慮到其余的點(diǎn)都移動(dòng)過，因此在最后set(x)的點(diǎn)是全部貼在一起的，因此需要滿足x中的所有點(diǎn)在最終結(jié)果（既將a排序后的序列）中是連續(xù)的。求出最大的集合只需掃一遍原數(shù)組即可。例2：停“房”(Parking)題目描述

在一棵N個(gè)節(jié)點(diǎn)的有根樹上，有一只蝸牛停在節(jié)點(diǎn)P上，其他還有K只蝸牛停在節(jié)點(diǎn)Si上。

現(xiàn)在這只停在P上的蝸牛，想要去根節(jié)點(diǎn)，將自己的房子停在那里。由于兩只蝸牛如果同時(shí)出現(xiàn)在一個(gè)節(jié)點(diǎn)上會(huì)造成危險(xiǎn)，所以你需要調(diào)度這些蝸牛，使得P到根的路徑上沒有別的蝸牛。可是蝸牛只能向葉子節(jié)點(diǎn)的方向爬，現(xiàn)在你希望知道所有蝸牛至少走幾步(走的步數(shù)總和最小)，才能使得根到P的路徑上沒有別的蝸牛。輸入樣例

第一行三個(gè)數(shù)N，P和K。

接下來N行，每行格式如下：

T

A1

A2…AT

第i+1行表示，第i個(gè)點(diǎn)有T個(gè)兒子，分別是A1~AT。

最后一行K個(gè)數(shù)，表示其他K蝸牛的停房地點(diǎn)，保證Si≠P。

輸出格式

一個(gè)數(shù)，表示其他蝸牛最少要移動(dòng)多少步。數(shù)據(jù)規(guī)模

對(duì)于40%的數(shù)據(jù)N≤20；

對(duì)于100%的數(shù)據(jù)2≤N≤5000，2≤P≤N，0≤K≤N-2。分析首先考慮到，蝸牛之間是沒有差別的，可以發(fā)現(xiàn)以下結(jié)論：在a->c的路徑上有b,那么a->b,b->c和a->c是沒有差別的，因此我們可以對(duì)每只蝸牛分開考慮。既在p->1的路徑上，如果存在某只擋路的蝸牛，那么只需在此蝸牛的子樹中找一個(gè)可行的離其最近的點(diǎn)即可，復(fù)雜度n^2例3：求最大得分對(duì)任意給定自然數(shù)集合W={m..n}(m,n≤100)若存在某個(gè)數(shù)p∈W;并且p至少是W中其他某個(gè)數(shù)的因數(shù);則刪除p和它的倍數(shù)后,得到p分;重復(fù)第2步,直到不能再刪除為止;求集合W的最大得分.例如W={3,4,5,6,7,8,9,10}刪除5,W={3,4,6,7,8,9}刪除4,W={3,6,7,9}刪除3,W={7}總得分為5+4+3=12基本思路初看這一問題，很容易想到用貪心策略來求解，即選擇集合中最大的可以刪除的數(shù)開始刪起，直到不能再刪除為止，而且通過一些簡(jiǎn)單的例子來驗(yàn)證，這一貪心標(biāo)準(zhǔn)似乎也是正確的，例如，當(dāng)m=2，n=10時(shí)，集合W＝{2,3,…,10}，運(yùn)用上述“貪心標(biāo)準(zhǔn)”可以得到這一問題的d=5＋4＋3＝121.a=5P={2,3,4,6,7,8,9}d=52.a=4P={2,3,6,7,9} d=5+4=93.a=3p={2,7} d=5+4+3=12分析但是，W={2,3,4,5,6,7,8,9,10}刪除5,W={2,3,4,6,7,8,9}刪除4,W={2,3,6,7,9}刪除2,W={3,7,9}刪除3,W={7}總得分為5+4+3+2=14問題出現(xiàn)在哪里呢??6既是3的倍數(shù)也是2的倍數(shù)!!算法改進(jìn)將原算法基礎(chǔ)上進(jìn)行改進(jìn)。下面給出新的算法：建立集合P={m..n}從ndiv2到m每數(shù)構(gòu)造一個(gè)集合c[i]，包含該數(shù)在P中的所有倍數(shù)（不包括i本身）從ndiv2起找到第一個(gè)元素個(gè)數(shù)最少但又不為空的集合c[i]在d分值中加上i把i及c[i]集合從P集中刪除，更新所有構(gòu)造集合的元素檢查所有構(gòu)造集合，若還有非空集合，則繼續(xù)3步驟，否則打印、結(jié)束思考題1:最大排列(Perm)問題描述

給一個(gè)長(zhǎng)度為N的序列，每個(gè)元素都不相同。每次可以交換相鄰兩個(gè)元素，現(xiàn)在你最多可以交換K次，問你可通過交換得到的字典序最大的序列是什么。

輸入格式

第一行兩個(gè)數(shù)N和K。

第一行N個(gè)數(shù)。

輸出格式

一行N個(gè)數(shù)字，表示字典序最大的序列。

最大排列(Perm)輸入樣例 71 10203040506070

輸出樣例 20103040506070

數(shù)據(jù)規(guī)模

對(duì)于30%的數(shù)據(jù)N≤50；

對(duì)于100%的數(shù)據(jù)N≤5000。思考題2:旅行家的預(yù)算一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱時(shí)空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途加油站數(shù)N（N可以為零），油站i離出發(fā)點(diǎn)的距離Di、每升汽油價(jià)格Pi（i=1，2，……，N）。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無法到達(dá)目的地，則輸出“NoSolution”。思考題3:刪數(shù)問題鍵盤輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按左右次序組成一個(gè)新的正整數(shù)。對(duì)給定的N和S，尋找一種刪數(shù)規(guī)則使得剩下得數(shù)字組成的新數(shù)最小。思考題4:數(shù)列極差問題