首先，我只是一個(gè)剛剛接觸信息學(xué)的渣渣，很多東西都還沒(méi)有掌握，甚至未曾聽(tīng)聞。今天做了七年前的Noip，感覺(jué)血脈膨脹，不能自已！
***1．機(jī)器翻譯*** (translate.pas/c/cpp) 【問(wèn)題描述】 小晨的電腦上安裝了一個(gè)機(jī)器翻譯軟件，他經(jīng)常用這個(gè)軟件來(lái)翻譯英語(yǔ)文章。 這個(gè)翻譯軟件的原理很簡(jiǎn)單，它只是從頭到尾，依次將每個(gè)英文單詞用對(duì)應(yīng)的中文含義來(lái)替換。對(duì)于每個(gè)英文單詞，軟件會(huì)先在內(nèi)存中查找這個(gè)單詞的中文含義，如果內(nèi)存中有，軟件就會(huì)用它進(jìn)行翻譯；如果內(nèi)存中沒(méi)有，軟件就會(huì)在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個(gè)單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。 假設(shè)內(nèi)存中有M 個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過(guò)M?1，軟件會(huì)將新單詞存入一個(gè)未使用的 內(nèi)存單元；若內(nèi)存中已存入M 個(gè)單詞，軟件會(huì)清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來(lái)，存放新單詞。 假設(shè)一篇英語(yǔ)文章的長(zhǎng)度為N 個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開(kāi)始前，內(nèi)存中沒(méi)有任何單詞。 【輸入】 輸入文件名為translate.in，輸入文件共2 行。每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第一行為兩個(gè)正整數(shù)M 和N，代表內(nèi)存容量和文章的長(zhǎng)度。 第二行為N 個(gè)非負(fù)整數(shù)，按照文章的順序，每個(gè)數(shù)（大小不超過(guò)1000）代表一個(gè)英文單詞。文章中兩個(gè)單詞是同一個(gè)單詞，當(dāng)且僅當(dāng)它們對(duì)應(yīng)的非負(fù)整數(shù)相同。 【輸出】 輸出文件translate.out 共1 行，包含一個(gè)整數(shù)，為軟件需要查詞典的次數(shù)。 【輸入輸出樣例1】 translate.in translate.out 3 7 1 2 1 5 4 4 1 5 【輸入輸出樣例 1 說(shuō)明】 整個(gè)查字典過(guò)程如下：每行表示一個(gè)單詞的翻譯，冒號(hào)前為本次翻譯后的內(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 translate.out 2 10 8 824 11 78 11 78 11 78 8 264 6 【數(shù)據(jù)范圍】 對(duì)于10%的數(shù)據(jù)有M=1，N≤ 5。 對(duì)于100%的數(shù)據(jù)有0
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;int m,n,a[1005],b[105],tot=0;int head=1,tail=0,queue[1005];int main(){ freopen("translate.in","r",stdin); freopen("translate.out","w",stdout); memset(queue,0,sizeof(queue)); scanf("%d%d",&n,&m); while(m--) { int t; scanf("%d",&t); for (int i=head;i<=tail;i++) if (queue[i]==t) goto h; tot++; queue[++tail]=t; if (tail-head+1>n) head++; h:; } 還是不難的哈哈。。。輕松拿到100分。***2．烏龜棋*** (tortoise.pas/c/cpp) 【問(wèn)題描述】 小明過(guò)生日的時(shí)候，爸爸送給他一副烏龜棋當(dāng)作禮物。 烏龜棋的棋盤(pán)是一行N 個(gè)格子，每個(gè)格子上一個(gè)分?jǐn)?shù)（非負(fù)整數(shù)）。棋盤(pán)第1 格是唯一 的起點(diǎn)，第N 格是終點(diǎn)，游戲要求玩家控制一個(gè)烏龜棋子從起點(diǎn)出發(fā)走到終點(diǎn)。 …… 1 2 3 4 5 …… N 烏龜棋中M 張爬行卡片，分成4 種不同的類(lèi)型（M 張卡片中不一定包含所有4 種類(lèi)型的卡片，見(jiàn)樣例），每種類(lèi)型的卡片上分別標(biāo)有1、2、3、4 四個(gè)數(shù)字之一，表示使用這種卡片后，烏龜棋子將向前爬行相應(yīng)的格子數(shù)。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒(méi)有使用過(guò)的爬行卡片，控制烏龜棋子前進(jìn)相應(yīng)的格子數(shù)，每張卡片只能使用一次。 游戲中，烏龜棋子自動(dòng)獲得起點(diǎn)格子的分?jǐn)?shù)，并且在后續(xù)的爬行中每到達(dá)一個(gè)格子，就得到該格子相應(yīng)的分?jǐn)?shù)。玩家最終游戲得分就是烏龜棋子從起點(diǎn)到終點(diǎn)過(guò)程中到過(guò)的所有格子的分?jǐn)?shù)總和。 很明顯，用不同的爬行卡片使用順序會(huì)使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多。 現(xiàn)在，告訴你棋盤(pán)上每個(gè)格子的分?jǐn)?shù)和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？ 【輸入】 輸入文件名tortoise.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第1 行2 個(gè)正整數(shù)N 和M，分別表示棋盤(pán)格子數(shù)和爬行卡片數(shù)。 第2 行N 個(gè)非負(fù)整數(shù)，a1, a2, ……, aN，其中ai 表示棋盤(pán)第i 個(gè)格子上的分?jǐn)?shù)。 第3 行M 個(gè)整數(shù)，b1,b2, ……, bM，表示M 張爬行卡片上的數(shù)字。 輸入數(shù)據(jù)保證到達(dá)終點(diǎn)時(shí)剛好用光M 張爬行卡片。 【輸出】 輸出文件名tortoise.out。 輸出只有1 行，1 個(gè)整數(shù)，表示小明最多能得到的分?jǐn)?shù)。 【輸入輸出樣例1】 tortoise.in tortoise.out 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 7 3 【輸入輸出樣例 1 說(shuō)明】 小明使用爬行卡片順序?yàn)?，1，3，1，2，得到的分?jǐn)?shù)為6+10+14+8+18+17=73。注意，由于起點(diǎn)是1，所以自動(dòng)獲得第1 格的分?jǐn)?shù)6。 【輸入輸出樣例2】 tortoise.in tortoise.out 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1 4 5 5 【數(shù)據(jù)范圍】 對(duì)于30%的數(shù)據(jù)有1 ≤ N≤ 30，1 ≤M≤ 12。 對(duì)于50%的數(shù)據(jù)有1 ≤ N≤ 120，1 ≤M≤ 50，且4 種爬行卡片，每種卡片的張數(shù)不會(huì)超 過(guò)20。 對(duì)于100%的數(shù)據(jù)有1 ≤ N≤ 350，1 ≤M≤ 120，且4 種爬行卡片，每種卡片的張數(shù)不會(huì)超過(guò)40；0 ≤ ai ≤ 100，1 ≤ i ≤ N；1 ≤ bi ≤ 4，1 ≤ i ≤M。
剛開(kāi)始試過(guò)深搜，結(jié)果，超時(shí)。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;int n,m,maxn=-1,tot=0;int score[355],card[125],flag[125];int max(int x,int y){ if(x>=y) return x; else return y;}void dfs(int pos){ if(pos==n) { maxn=max(tot,maxn);//不得使用tot，要更改 return ; } for(int i=1;i<=m;i++) { int now=pos+card[i];//位置 if(flag[i]==0&&now<=n)//邊界 { flag[i]=1; tot+=score[now];//初始化 dfs(now); flag[i]=0; tot-=score[now];//還原回去 } }}int main(){ freopen("tortoise.in","r",stdin); freopen("tortoise.out","w",stdout); memset(flag,0,sizeof(flag)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&score[i]); for(int i=1;i<=m;i++) scanf("%d",&card[i]); tot+=score[1];//最開(kāi)頭 dfs(1); printf("%d",maxn); return 0;}后來(lái)想到了dp。。迷了這很明顯是dp啊！
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=40+5;int n,m,dp[N][N][N][N],card[5],a[500];int main(){ memset(card,0,sizeof(card)); 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 i=1;i<=m;i++) { int x; scanf("%d",&x); card[x]++; } dp[0][0][0][0]=a[1]; for(int l1=0;l1<=card[1];l1++) for(int l2=0;l2<=card[2];l2++) for(int l3=0;l3<=card[3];l3++) for(int l4=0;l4<=card[4];l4++) { int s=l1+l2*2+l3*3+l4*4+1; if(l1) dp[l1][l2][l3][l4]=max(dp[l1][l2][l3][l4],dp[l1-1][l2][l3][l4]+a[s]); if(l2) dp[l1][l2][l3][l4]=max(dp[l1][l2][l3][l4],dp[l1][l2-1][l3][l4]+a[s]); if(l3) dp[l1][l2][l3][l4]=max(dp[l1][l2][l3][l4],dp[l1][l2][l3-1][l4]+a[s]); if(l4) dp[l1][l2][l3][l4]=max(dp[l1][l2][l3][l4],dp[l1][l2][l3][l4-1]+a[s]); } printf("%d/n",dp[card[1]][card[2]][card[3]][card[4]]); return 0;}一下子就過(guò)了，又是100分。
***3．關(guān)押罪犯*** (prison.pas/c/cpp) 【問(wèn)題描述】 S 城現(xiàn)有兩座監(jiān)獄，一共關(guān)押著N 名罪犯，編號(hào)分別為1~N。他們之間的關(guān)系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀(guān)條件具備則隨時(shí)可能爆發(fā)沖突。我們用“怨氣值”（一個(gè)正整數(shù)值）來(lái)表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為c 的罪犯被關(guān)押在同一監(jiān)獄，他們倆之間會(huì)發(fā)生摩擦，并造成影響力為c 的沖突事件。 每年年末，警察局會(huì)將本年內(nèi)監(jiān)獄中的所有沖突事件按影響力從大到小排成一個(gè)列表，然后上報(bào)到S 城Z 市長(zhǎng)那里。公務(wù)繁忙的Z 市長(zhǎng)只會(huì)去看列表中的第一個(gè)事件的影響力，如果影響很壞，他就會(huì)考慮撤換警察局長(zhǎng)。 在詳細(xì)考察了N 名罪犯間的矛盾關(guān)系后，警察局長(zhǎng)覺(jué)得壓力巨大。他準(zhǔn)備將罪犯?jìng)冊(cè)趦勺O(jiān)獄內(nèi)重新分配，以求產(chǎn)生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設(shè)只要處于同一監(jiān)獄內(nèi)的某兩個(gè)罪犯間有仇恨，那么他們一定會(huì)在每年的某個(gè)時(shí)候發(fā)生摩擦。那么，應(yīng)如何分配罪犯，才能使Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力最小？這個(gè)最小值是多少？ 【輸入】 輸入文件名為prison.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第一行為兩個(gè)正整數(shù)N 和M，分別表示罪犯的數(shù)目以及存在仇恨的罪犯對(duì)數(shù)。 接下來(lái)的M 行每行為三個(gè)正整數(shù)aj，bj，cj，表示aj 號(hào)和bj 號(hào)罪犯之間存在仇恨，其怨氣值為 cj。數(shù)據(jù)保證 a b N j j 1 ≤ < ≤ ，0 < ≤ 1,000,000,000 j c ，且每對(duì)罪犯組合只出現(xiàn)一次。 【輸出】 輸出文件prison.out 共1 行，為Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力。如果本年內(nèi)監(jiān)獄中未發(fā)生任何沖突事件，請(qǐng)輸出0。 【輸入輸出樣例】 prison.in prison.out 4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 3512 【輸入輸出樣例說(shuō)明】 罪犯之間的怨氣值如下面左圖所示，右圖所示為罪犯的分配方法，市長(zhǎng)看到的沖突事件影響力是3512（由2 號(hào)和3 號(hào)罪犯引發(fā)）。其他任何分法都不會(huì)比這個(gè)分法更優(yōu)。
起初想到了并查集的方法，然而。。。并沒(méi)有成功實(shí)現(xiàn)。于是暴力，無(wú)奈暴力水平太低。。。只有20分。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;int n,m,map[500][500],a[50000],b[50000];int tota=0,totb=0,maxn;void findmax(){ maxn=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if (map[i][j]>=maxn) { maxn=map[i][j]; break; } }}int judgeA(){ for (int i=1;i<=tota;i++) for (int j=1;j<=tota;j++) if (a[i]==a[j]&&a[i]!=0) return 0; else return 1;}int judgeB(){ for (int i=1;i<=totb;i++) for (int j=1;j<=totb;j++) if (b[i]==b[j]&&b[i]!=0) return 0; else return 1;}void woork(){ tota++; totb++; for (int g=1;g<=n;g++) for (int h=1;h<=n;h++) { if (map[g][h]==maxn) { int aa=0,bb=0; for (int d=1;d<=tota;d++) { if (a[d]!=0) aa++; if (b[d]!=0) bb++; } if (aa+bb>=n) break; else { int maxa=0,maxb=0; for (int p=1;p<=tota;p++) maxa=max(map[p][g],maxa); for (int q=1;q<=totb;q++) maxb=max(map[q][h],maxb); if (maxa<=maxb/*&&judgeA()==1&&judgeB()==1*/) a[tota]=g,b[totb]=h; else a[tota]=h,b[totb]=g; map[g][h]=0; map[h][g]=0; } } }}int main(){ freopen("prison.in","r",stdin); freopen("prison.out","w",stdout); memset(map,0,sizeof(map)); scanf("%d%d",&n,&m); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); map[a][b]=c; map[b][a]=c; } for (int i=1;i<=n;i++) { findmax(); woork();// judge(); } int maxaa=0,maxbb=0; for (int w=1;w<=tota;w++) for (int e=1;e<=tota;e++) maxaa=max(maxaa,map[a[w]][a[e]]); for (int w=1;w<=tota;w++) for (int e=1;e<=tota;e++) maxbb=max(maxbb,map[b[w]][b[e]]); if (maxaa>=maxbb) printf("%d ",maxaa); else printf("%d ",maxbb); return 0; }后來(lái)發(fā)現(xiàn)確實(shí)是是并查集，代碼如下：
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;struct edge{ int x,y,v;}cr[100050];bool cmp(edge a,edge b) { return a.v>b.v;}int n,m;int an[20050],pr[20050],en[20050];int father(int x){ if(pr[x]==x) return x; pr[x]=father(pr[x]); return pr[x];}void Union(int x,int y){ int fx=father(x); int fy=father(y); if(fx!=fy) pr[fx]=fy;}int main(){ freopen("prison.in","r",stdin); freopen("prison.out","w",stdout); memset(pr,0,sizeof(pr)); memset(en,0,sizeof(en)); scanf("%d%d",&n,&m); int x,y,v; for(int i=1;i<=m;i++) { scanf("%d%d%d",&cr[i].x,&cr[i].y,&cr[i].v); } sort(cr+1,cr+m+1,cmp); for(int i=1;i<=n;i++) {pr[i]=i;en[i]=0;} for(int i=1;i<=m;i++) { x=cr[i].x; y=cr[i].y; int fx=father(x); int fy=father(y); if(fx==fy) { printf("%d/n",cr[i].v); return 0; } if(en[x]==0) en[x]=y; else Union(y,en[x]); if(en[y]==0) en[y]=x; else Union(x,en[y]); } printf("0/n"); return 0;}一下子就滿(mǎn)分了。***4.引水入城*** (flow.pas/c/cpp) 【問(wèn)題描述】 在一個(gè)遙遠(yuǎn)的國(guó)度，一側(cè)是風(fēng)景秀美的湖泊，另一側(cè)則是漫無(wú)邊際的沙漠。該國(guó)的行政區(qū)劃十分特殊，剛好構(gòu)成一個(gè)N 行M 列的矩形，如上圖所示，其中每個(gè)格子都代表一座城市，每座城市都有一個(gè)海拔高度。 為了使居民們都盡可能飲用到清澈的湖水，現(xiàn)在要在某些城市建造水利設(shè)施。水利設(shè)施有兩種，分別為蓄水廠(chǎng)和輸水站。蓄水廠(chǎng)的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此，只有與湖泊毗鄰的第1 行的城市可以建造蓄水廠(chǎng)。而輸水站的功能則是通過(guò)輸水管線(xiàn)利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經(jīng)建有水利設(shè)施。由第N 行的城市靠近沙漠，是該國(guó)的干旱區(qū)，所以要求其中的每座城市都建有水利 設(shè)施。那么，這個(gè)要求能否滿(mǎn)足呢？如果能，請(qǐng)計(jì)算最少建造幾個(gè)蓄水廠(chǎng)；如果不能，求干旱區(qū)中不可能建有水利設(shè)施的城市數(shù)目。 【輸入】 輸入文件名為flow.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 輸入的第一行是兩個(gè)正整數(shù)N 和M，表示矩形的規(guī)模。 接下來(lái)N 行，每行M 個(gè)正整數(shù)，依次代表每座城市的海拔高度。 【輸出】 輸出文件名為flow.out。 輸出有兩行。如果能滿(mǎn)足要求，輸出的第一行是整數(shù)1，第二行是一個(gè)整數(shù)，代表最少建造幾個(gè)蓄水廠(chǎng)；如果不能滿(mǎn)足要求，輸出的第一行是整數(shù)0，第二行是一個(gè)整數(shù)，代表有幾座干旱區(qū)中的城市不可能建有水利設(shè)施。 【輸入輸出樣例1】 flow.in flow.out 2 5 9 1 5 4 3 8 7 6 1 2 1 1 【樣例1 說(shuō)明】 只需要在海拔為9 的那座城市中建造蓄水廠(chǎng)，即可滿(mǎn)足要求。 【輸入輸出樣例2】 flow.in flow.out 3 6 8 4 5 6 4 4 7 3 4 3 3 3 3 2 2 1 1 2 1 3 【樣例2 說(shuō)明】 湖泊 8 4 5 6 4 4 7 3 4 3 3 3 3 2 2 1 1 2 沙漠 上圖中，在3 個(gè)粗線(xiàn)框出的城市中建造蓄水廠(chǎng)，可以滿(mǎn)足要求。以這3 個(gè)蓄水廠(chǎng)為源頭在干旱區(qū)中建造的輸水站分別用3 種顏色標(biāo)出。當(dāng)然，建造方法可能不唯一。 【數(shù)據(jù)范圍】 本題共有10 個(gè)測(cè)試數(shù)據(jù)，每個(gè)數(shù)據(jù)的范圍如下表所示： 測(cè)試數(shù)據(jù)編號(hào)能否滿(mǎn)足要求 N M 1 不能 ≤ 10 ≤ 10 2 不能 ≤ 100 ≤ 100 3 不能 ≤ 500 ≤ 500 4 能 = 1 ≤ 10 5 能 ≤ 10 ≤ 10 6 能 ≤ 100 ≤ 20 7 能 ≤ 100 ≤ 50 8 能 ≤ 100 ≤ 100 9 能 ≤ 200 ≤ 200 10 能 ≤ 500 ≤ 500 對(duì)于所有的10 個(gè)數(shù)據(jù)，每座城市的海拔高度都不超過(guò)106。
暴力！（不會(huì)。。），這個(gè)只有10分，所以以后會(huì)了更新吧。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=500+5;int n,m;int a[N][N]={0};int main(){ freopen("flow.in","r",stdin); freopen("flow.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); if(n==1) { int tot=0; for(int i=1;i<=m;i++) if(a[1][i]>=a[1][i-1]&&a[1][i]>=a[1][i+1]) tot++; printf("1/n%d",tot); } else { int tot=0; for(int j=1;j<=m;j++) for(int i=1;i<=m;i++) if(a[n][i]>=a[n][i-1]&&a[n][i]>=a[n][i+1]&&a[n][i]>=a[n-1][i]) { tot++; a[n][i]=-1; } printf("0/n%d",tot); } return 0;}這個(gè)代碼就不要看了。
這就是這次模擬的心得體會(huì)，分?jǐn)?shù)一般，重要的是知識(shí)與經(jīng)驗(yàn)的積累。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
