最后一道題WA了，用了貪心，忘了這是一道線段覆蓋的問題。
(translate.pas/c/cpp) 【問題描述】 小晨的電腦上安裝了一個(gè)機(jī)器翻譯軟件，他經(jīng)常用這個(gè)軟件來翻譯英語文章。這個(gè)翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個(gè)英文單詞用對應(yīng)的中文含義來替換。對于每個(gè)英文單詞，軟件會先在內(nèi)存中查找這個(gè)單詞的中文含義，如果內(nèi)存中有，軟件就會用它進(jìn)行翻譯；如果內(nèi)存中沒有，軟件就會在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個(gè)單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。 假設(shè)內(nèi)存中有M 個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過M?1，軟件會將新單詞存入一個(gè)未使用的內(nèi)存單元；若內(nèi)存中已存入M 個(gè)單詞，軟件會清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來，存放新單詞。 假設(shè)一篇英語文章的長度為N 個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多 少次詞典？假設(shè)在翻譯開始前，內(nèi)存中沒有任何單詞。 【輸入】 輸入文件名為translate.in，輸入文件共2 行。每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。 第一行為兩個(gè)正整數(shù)M 和N，代表內(nèi)存容量和文章的長度。 第二行為N 個(gè)非負(fù)整數(shù)，按照文章的順序，每個(gè)數(shù)（大小不超過1000）代表一個(gè)英文單詞。文章中兩個(gè)單詞是同一個(gè)單詞，當(dāng)且僅當(dāng)它們對應(yīng)的非負(fù)整數(shù)相同。 【輸出】 輸出文件translate.out 共1 行，包含一個(gè)整數(shù)，為軟件需要查詞典的次數(shù)。
【輸入輸出樣例1】 translate.in 3 7 1 2 1 5 4 4 1 translate.out 5
【輸入輸出樣例 1 說明】 整個(gè)查字典過程如下：每行表示一個(gè)單詞的翻譯，冒號前為本次翻譯后的內(nèi)存狀況： 空：內(nèi)存初始狀態(tài)為空。 1． 1：查找單詞1 并調(diào)入內(nèi)存。 2． 1 2：查找單詞2 并調(diào)入內(nèi)存。 3． 1 2：在內(nèi)存中找到單詞1。 4． 1 2 5：查找單詞5 并調(diào)入內(nèi)存。 5． 2 5 4：查找單詞4 并調(diào)入內(nèi)存替代單詞1。 6． 2 5 4：在內(nèi)存中找到單詞4。 7． 5 4 1：查找單詞1 并調(diào)入內(nèi)存替代單詞2。 共計(jì)查了5 次詞典。
【輸入輸出樣例2】 translate.in 2 10 8 824 11 78 11 78 11 78 8 264 translate.out 6
【數(shù)據(jù)范圍】 對于10%的數(shù)據(jù)有M=1，N≤ 5。 對于100%的數(shù)據(jù)有0
set+queue亂搞就行了，水水水！！！
#include<set>#include<queue>#include<cstdio>#include<iostream>using namespace std;queue<int> q;set<int> p;int tot=0,ans=0,m,n;int main(){ freopen("translate.in","r",stdin); freopen("translate.out","w",stdout); scanf("%d%d",&m,&n); for(int x,i=1;i<=n;i++){ scanf("%d",&x); if(p.find(x)==p.end()){ p.insert(x);q.push(x); tot++;ans++; } if(tot>m){ x=q.front();q.pop(); p.erase(x);tot--; } } cout<<ans<<endl; return 0;}(tortoise.pas/c/cpp) 【問題描述】 小明過生日的時(shí)候，爸爸送給他一副烏龜棋當(dāng)作禮物。 烏龜棋的棋盤是一行N 個(gè)格子，每個(gè)格子上一個(gè)分?jǐn)?shù)（非負(fù)整數(shù)）。棋盤第1 格是唯一 的起點(diǎn)，第N 格是終點(diǎn)，游戲要求玩家控制一個(gè)烏龜棋子從起點(diǎn)出發(fā)走到終點(diǎn)。 …… 1 2 3 4 5 …… N 烏龜棋中M 張爬行卡片，分成4 種不同的類型（M 張卡片中不一定包含所有4 種類型的卡片，見樣例），每種類型的卡片上分別標(biāo)有1、2、3、4 四個(gè)數(shù)字之一，表示使用這種卡片后，烏龜棋子將向前爬行相應(yīng)的格子數(shù)。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片，控制烏龜棋子前進(jìn)相應(yīng)的格子數(shù)，每張卡片只能使用一次。 游戲中，烏龜棋子自動獲得起點(diǎn)格子的分?jǐn)?shù)，并且在后續(xù)的爬行中每到達(dá)一個(gè)格子，就得到該格子相應(yīng)的分?jǐn)?shù)。玩家最終游戲得分就是烏龜棋子從起點(diǎn)到終點(diǎn)過程中到過的所有格子的分?jǐn)?shù)總和。 很明顯，用不同的爬行卡片使用順序會使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多。 現(xiàn)在，告訴你棋盤上每個(gè)格子的分?jǐn)?shù)和所有的爬行卡片，你能告訴小明，他最多能得到 多少分嗎？ 【輸入】 輸入文件名tortoise.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。 第1 行2 個(gè)正整數(shù)N 和M，分別表示棋盤格子數(shù)和爬行卡片數(shù)。 第2 行N 個(gè)非負(fù)整數(shù)，a1, a2, ……, aN，其中ai 表示棋盤第i 個(gè)格子上的分?jǐn)?shù)。 第3 行M 個(gè)整數(shù)，b1,b2, ……, bM，表示M 張爬行卡片上的數(shù)字。 輸入數(shù)據(jù)保證到達(dá)終點(diǎn)時(shí)剛好用光M 張爬行卡片，即N?1=
【輸入輸出樣例1】 tortoise.in 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 tortoise.out 73
【輸入輸出樣例 1 說明】 小明使用爬行卡片順序?yàn)?，1，3，1，2，得到的分?jǐn)?shù)為6+10+14+8+18+17=73。注意， 由于起點(diǎn)是1，所以自動獲得第1 格的分?jǐn)?shù)6。
【輸入輸出樣例2】 tortoise.in 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1 tortoise.out 455
【數(shù)據(jù)范圍】 對于30%的數(shù)據(jù)有1 ≤ N≤ 30，1 ≤M≤ 12。 對于50%的數(shù)據(jù)有1 ≤ N≤ 120，1 ≤M≤ 50，且4 種爬行卡片，每種卡片的張數(shù)不會超 過20。 對于100%的數(shù)據(jù)有1 ≤ N≤ 350，1 ≤M≤ 120，且4 種爬行卡片，每種卡片的張數(shù)不會 超過40；0 ≤ ai ≤ 100，1 ≤ i ≤ N；1 ≤ bi ≤ 4，1 ≤ i ≤M。輸入數(shù)據(jù)保證N?1=N?1=
因?yàn)槊糠N牌的數(shù)量小于40，所以就可以用四維dp秒解。 以f[i][j][k][p]來表示四種牌去i,j,k,p張是的最大收益就可以了。
#include<cstdio>#include<iostream>#define res(x,y) for(int x=0;x<=y;x++)using namespace std;int n,m,f[45][45][45][45],a[400],c[5];int main(){ freopen("tortoise.in","r",stdin); freopen("tortoise.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int x,i=1;i<=m;i++)scanf("%d",&x),c[x]++; res(i,c[1])res(j,c[2])res(k,c[3])res(p,c[4]){ int a1=i==0?0:f[i-1][j][k][p]; int a2=j==0?0:f[i][j-1][k][p]; int a3=k==0?0:f[i][j][k-1][p]; int a4=p==0?0:f[i][j][k][p-1]; int t=max(max(a1,a2),max(a3,a4)); f[i][j][k][p]=t+a[1*i+2*j+3*k+4*p+1]; } cout<<f[c[1]][c[2]][c[3]][c[4]]<<endl; return 0;}(PRison.pas/c/cpp) 【問題描述】 S 城現(xiàn)有兩座監(jiān)獄，一共關(guān)押著N 名罪犯，編號分別為1~N。他們之間的關(guān)系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時(shí)可能爆發(fā)沖突。我們用“怨氣值”（一個(gè)正整數(shù)值）來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為c 的罪犯被關(guān)押在同一監(jiān)獄，他們倆之間會發(fā)生摩擦，并造成影響力為c 的沖突事件。 每年年末，警察局會將本年內(nèi)監(jiān)獄中的所有沖突事件按影響力從大到小排成一個(gè)列表，然后上報(bào)到S 城Z 市長那里。公務(wù)繁忙的Z 市長只會去看列表中的第一個(gè)事件的影響力，如果影響很壞，他就會考慮撤換警察局長。 在詳細(xì)考察了N 名罪犯間的矛盾關(guān)系后，警察局長覺得壓力巨大。他準(zhǔn)備將罪犯們在 兩座監(jiān)獄內(nèi)重新分配，以求產(chǎn)生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設(shè)只要處于同一監(jiān)獄內(nèi)的某兩個(gè)罪犯間有仇恨，那么他們一定會在每年的某個(gè)時(shí)候發(fā)生摩擦。那么，應(yīng)如何分配罪犯，才能使Z 市長看到的那個(gè)沖突事件的影響力最小？這個(gè)最小值是多少？ 【輸入】 輸入文件名為prison.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。 第一行為兩個(gè)正整數(shù)N 和M，分別表示罪犯的數(shù)目以及存在仇恨的罪犯對數(shù)。 接下來的M 行每行為三個(gè)正整數(shù)aj，bj，cj，表示aj 號和bj 號罪犯之間存在仇恨，其怨 氣值為 cj。數(shù)據(jù)保證 a b N j j 1 ≤ < ≤ ，0 < ≤ 1,000,000,000 j c ，且每對罪犯組合只出現(xiàn)一 次。 【輸出】 輸出文件prison.out 共1 行，為Z 市長看到的那個(gè)沖突事件的影響力。如果本年內(nèi)監(jiān)獄中未發(fā)生任何沖突事件，請輸出0。
【輸入輸出樣例】 prison.in、 4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 prison.out 3512
【輸入輸出樣例說明】 罪犯之間的怨氣值如下面左圖所示，右圖所示為罪犯的分配方法，市長看到的沖突事件 
影響力是3512（由2 號和3 號罪犯引發(fā)）。其他任何分法都不會比這個(gè)分法更優(yōu)。 【數(shù)據(jù)范圍】 對于30%的數(shù)據(jù)有N≤ 15。 對于70%的數(shù)據(jù)有N≤ 2000，M≤ 50000。 對于100%的數(shù)據(jù)有N≤ 20000，M≤ 100000。
二分暴力可以過，然而我用并查集。開一個(gè)鏡像 N來代表當(dāng)f[x]!=f[y]時(shí)若將其連接的情況。
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int f[60010],n,m;struct node{ int x,y,z; bool Operator < (const node &rhs)const {return z>rhs.z;}}p[100010];int find(int x){return f[x]==x?x:x=find(f[x]);}int main(){ freopen("prison.in","r",stdin);freopen("prison.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n*2+10;i++)f[i]=i; for(int i=1;i<=m;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z); sort(p+1,p+1+m); for(int i=1;i<=m;i++){ int x=find(p[i].x),y=find(p[i].y); if(x==y){cout<<p[i].z<<endl;return 0;} f[x]=find(p[i].y+n),f[y]=find(p[i].x+n); } cout<<0<<endl; return 0;}
(flow.pas/c/cpp) 【問題描述】 在一個(gè)遙遠(yuǎn)的國度，一側(cè)是風(fēng)景秀美的湖泊，另一側(cè)則是漫無邊際的沙漠。該國的行政區(qū)劃十分特殊，剛好構(gòu)成一個(gè) N 行 M 列的矩形，如上圖所示，其中每個(gè)格子都代表一座城市，每座城市都有一個(gè)海拔高度。 為了使居民們都盡可能飲用到清澈的湖水，現(xiàn)在要在某些城市建造水利設(shè)施。水利設(shè)施有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此，只有與湖泊毗鄰的第 1 行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經(jīng)建有水利設(shè)施。 由于第 N 行的城市靠近沙漠，是該國的干旱區(qū)，所以要求其中的每座城市都建有水利設(shè)施。那么，這個(gè)要求能否滿足呢？如果能，請計(jì)算最少建造幾個(gè)蓄水廠；如果不能，求干旱區(qū)中不可能建有水利設(shè)施的城市數(shù)目。
【輸入】
輸入文件名為flow.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。 輸入的第一行是兩個(gè)正整數(shù) N 和 M，表示矩形的規(guī)模。 接下來 N 行，每行 M 個(gè)正整數(shù)，依次代表每座城市的海拔高度。 【輸出】 輸出文件名為flow.out。 輸出有兩行。如果能滿足要求，輸出的第一行是整數(shù) 1，第二行是一個(gè)整數(shù)，代表最少建造幾個(gè)蓄水廠；如果不能滿足要求，輸出的第一行是整數(shù)0，第二行是一個(gè)整數(shù)，代表有幾座干旱區(qū)中的城市不可能建有水利設(shè)施。
【輸入輸出樣例1】 flow.in 2 5 9 1 5 4 3 8 7 6 1 2 flow.out 1 1 【樣例1 說明】
只需要在海拔為9 的那座城市中建造蓄水廠，即可滿足要求。
【輸入輸出樣例2】 flow.in 3 6 8 4 5 6 4 4 7 3 4 3 3 3 3 2 2 1 1 2 flow.out 1 3
【樣例2 說明】
上圖中，在 3 個(gè)粗線框出的城市中建造蓄水廠，可以滿足要求。以這3 個(gè)蓄水廠為源頭
在干旱區(qū)中建造的輸水站分別用 3 種顏色標(biāo)出。當(dāng)然，建造方法可能不唯一。
【數(shù)據(jù)范圍】
本題共有10 個(gè)測試數(shù)據(jù)，每個(gè)數(shù)據(jù)的范圍如下表所示： 
新聞熱點(diǎn)
疑難解答
