自測(cè)：8:27——11:51

實(shí)際得分：100+60+20=180

期望得分：100+60+40=200

T3讀錯(cuò)題，失20

http://cogs.pro/cogs/page/page.php?aid=16

T1 鋪地毯

【問(wèn)題描述】?
為了準(zhǔn)備一個(gè)獨(dú)特的頒獎(jiǎng)典禮，組織者在會(huì)場(chǎng)的一片矩形區(qū)域（可看做是平面直角坐標(biāo)系的第一象限）鋪上一些矩形地毯。一共有 n張地毯，編號(hào)從 1 到n?，F(xiàn)在將這些地毯按照編號(hào)從小到大的順序平行于坐標(biāo)軸先后鋪設(shè)，后鋪的地毯覆蓋在前面已經(jīng)鋪好的地毯之上。
地毯鋪設(shè)完成后，組織者想知道覆蓋地面某個(gè)點(diǎn)的最上面的那張地毯的編號(hào)。注意：在矩形地毯邊界和四個(gè)頂點(diǎn)上的點(diǎn)也算被地毯覆蓋。?

【輸入】?
輸入文件名為 carpet.in。?
輸入共 n+2行。?
第一行，一個(gè)整數(shù) n，表示總共有 n張地毯。?
接下來(lái)的 n行中，第 i+1行表示編號(hào) i的地毯的信息，包含四個(gè)正整數(shù) a，b，g，k，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，分別表示鋪設(shè)地毯的左下角的坐標(biāo)（a，b）以及地毯在 x 軸和 y軸方向的長(zhǎng)度。?
第 n+2 行包含兩個(gè)正整數(shù) x 和 y，表示所求的地面的點(diǎn)的坐標(biāo)（x，y） 。?
【輸出】?
輸出文件名為 carpet.out。?
輸出共 1 行，一個(gè)整數(shù)，表示所求的地毯的編號(hào)；若此處沒(méi)有被地毯覆蓋則輸出-1。?

【輸入輸出樣例 1】

carpet.in

3?
1 0 2 3?
0 2 3 3?
2 1 3 3?
2 2

carpet.out

3

【輸入輸出樣例說(shuō)明】?
如下圖，1 號(hào)地毯用實(shí)線(xiàn)表示，2 號(hào)地毯用虛線(xiàn)表示，3 號(hào)用雙實(shí)線(xiàn)表示，覆蓋點(diǎn)（2，2）的最上面一張地毯是 3 號(hào)地毯。

?

【輸入輸出樣例 2】

carpet.in

3?
1 0 2 3?
0 2 3 3?
2 1 3 3?
4 5

carpet.out

-1

【輸入輸出樣例說(shuō)明】?
如上圖，1 號(hào)地毯用實(shí)線(xiàn)表示，2 號(hào)地毯用虛線(xiàn)表示，3 號(hào)用雙實(shí)線(xiàn)表示，點(diǎn)（4，5）
沒(méi)有被地毯覆蓋，所以輸出-1。?

【數(shù)據(jù)范圍】?
對(duì)于 30%的數(shù)據(jù)，有 n≤2；?
對(duì)于 50%的數(shù)據(jù)，0≤a, b, g, k≤100；?
對(duì)于 100%的數(shù)據(jù)，有 0≤n≤10,000，0≤a, b, g, k≤100,000。

從后往前枚舉判斷

時(shí)間復(fù)雜度：O（n）

?

#include<cstdio> #define N 10001 using namespace std; int a,b,g,k,x,y,n; int x1[N],x2[N],y1[N],y2[N]; int main() {freopen("carpet.in","r",stdin);freopen("carpet.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d%d",&a,&b,&g,&k);x1[i]=a;x2[i]=a+g;y1[i]=b;y2[i]=b+k;}scanf("%d%d",&x,&y);for(int i=n;i;i--){if(x>=x1[i]&&x<=x2[i]&&y>=y1[i]&&y<=y2[i]) {printf("%d",i);fclose(stdin); fclose(stdout);return 0;}}printf("-1");fclose(stdin);fclose(stdout);return 0; } View Code

?

?

?

?

T2 選擇客棧

時(shí)間限制：1 s?? 內(nèi)存限制：128 MB

【問(wèn)題描述】

?

麗江河邊有n 家很有特色的客棧，客棧按照其位置順序從1 到n 編號(hào)。每家客棧都按照某一種色調(diào)進(jìn)行裝飾（總共k 種，用整數(shù)0 ~ k-1 表示），且每家客棧都設(shè)有一家咖啡店，每家咖啡店均有各自的最低消費(fèi)。
兩位游客一起去麗江旅游，他們喜歡相同的色調(diào)，又想嘗試兩個(gè)不同的客棧，因此決定分別住在色調(diào)相同的兩家客棧中。晚上，他們打算選擇一家咖啡店喝咖啡，要求咖啡店位于兩人住的兩家客棧之間（包括他們住的客棧），且咖啡店的最低消費(fèi)不超過(guò)p。
他們想知道總共有多少種選擇住宿的方案，保證晚上可以找到一家最低消費(fèi)不超過(guò)p元的咖啡店小聚。

?

【輸入】
輸入文件hotel.in，共n+1 行。
第一行三個(gè)整數(shù)n，k，p，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，分別表示客棧的個(gè)數(shù)，色調(diào)的數(shù)目和能接受的最低消費(fèi)的最高值；
接下來(lái)的n 行，第i+1 行兩個(gè)整數(shù)，之間用一個(gè)空格隔開(kāi)，分別表示i 號(hào)客棧的裝飾色調(diào)和i 號(hào)客棧的咖啡店的最低消費(fèi)。

?

【輸出】
輸出文件名為hotel.out。

?

輸出只有一行，一個(gè)整數(shù)，表示可選的住宿方案的總數(shù)。

?

【輸入輸出樣例1】

?

hotel.in

?

5 2 3
0 5
1 3
0 2
1 4
1 5

?

hotel.out

?

3

?

【輸入輸出樣例說(shuō)明】

?

客棧編號(hào)	①	②	③	④	⑤
色調(diào)	0	1	0	1	1
最低消費(fèi)	5	3	2	4	5

?

2 人要住同樣色調(diào)的客棧，所有可選的住宿方案包括：住客棧①③，②④，②⑤，④⑤，但是若選擇住4、5 號(hào)客棧的話(huà)，4、5 號(hào)客棧之間的咖啡店的最低消費(fèi)是4，而兩人能承受的最低消費(fèi)是3 元，所以不滿(mǎn)足要求。因此只有前3 種方案可選。

?

【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，有n≤100；
對(duì)于50%的數(shù)據(jù)，有n≤1,000；
對(duì)于100%的數(shù)據(jù)，有2≤n≤200,000, 0≤K≤50，0≤P≤100， 0≤最低消費(fèi)≤100, K≤50，0≤P≤100，

法一、O（nk+n）

same[i][j]表示前i個(gè)客棧中，色調(diào)為j的個(gè)數(shù)

pre[i]表示前i個(gè)客棧中，最后一個(gè)消費(fèi)<=p的客棧

O（nk）預(yù)處理same[]

然后枚舉客棧i

如果pre[i]=i，說(shuō)明客棧i的消費(fèi)<=p，那么 i 與 i前面任意一個(gè)色調(diào)為color[i]的客棧 都是合法的

所以ans+=sum[i][color[i]]-1

如果pre[i]!=i,說(shuō)明客棧i的消費(fèi)>p，那么 i 與 pre[i]前面任意一個(gè)色調(diào)為color[i]的客棧（包括pre[i]） 都是合法的

所以ans+=sum[pre[i]][color[i]]

#include<cstdio> #define N 200001 using namespace std; int n,k,p; int same[N][51],sum[51],pre[N],last,co[N]; long long ans; int main() {freopen("hotel.in","r",stdin);freopen("hotel.out","w",stdout);scanf("%d%d%d",&n,&k,&p);int x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);sum[x]++;co[i]=x;for(int j=0;j<=k;j++) same[i][j]=sum[j]; if(y<=p) last=i;pre[i]=last;}for(int i=1;i<=n;i++)if(pre[i]==i) ans+=same[i][co[i]]-1;else ans+=same[pre[i]][co[i]];printf("%lld",ans); } View Code

法二、O（n）

last[i]=j 表示當(dāng)前顏色為i的 所有客棧中，最后一個(gè)的是j

lastt 表示當(dāng)前所有客棧中，最后一個(gè)消費(fèi)<=p的客棧

sum_tot[i]=j ?表示當(dāng)前顏色為i的客棧共有j個(gè)

sum[i]=j 表示當(dāng)前與 顏色為i的這個(gè)客棧 可以組成的合法方案數(shù)

直接看代碼吧。。

#include<cstdio> #define N 200001 using namespace std; int n,k,p; int last[51],lastt,sum_tot[51],sum[51]; long long ans; int main() {freopen("hotel.in","r",stdin);freopen("hotel.out","w",stdout);scanf("%d%d%d",&n,&k,&p);int x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(y<=p) lastt=i;if(last[x]<=lastt) sum[x]=sum_tot[x];sum_tot[x]++; last[x]=i;ans+=sum[x]; }printf("%lld",ans); } View Code

自測(cè)時(shí)打的n2的暴力 60分

#include<cstdio> #include<algorithm> #define N 200001 using namespace std; int n,k,p; int sum[N]; long long ans,tmp; struct node {int id,color; }e[N]; int main() {freopen("hotel.in","r",stdin);freopen("hotel.out","w",stdout);scanf("%d%d%d",&n,&k,&p);int x;for(int i=1;i<=n;i++){e[i].id=i; scanf("%d",&e[i].color);scanf("%d",&x);sum[i]=sum[i-1]+(x<=p);}for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)if(e[i].color==e[j].color&&sum[e[j].id]-sum[e[i].id-1]) ans++;printf("%lld",ans); } View Code

為什么沒(méi)想出來(lái)？

1、一開(kāi)始讀錯(cuò)題，看成了選的喝咖啡的地方不同也是不同的方案

不認(rèn)真讀題，難道覺(jué)得自己可以輕松應(yīng)對(duì)NOIP了嗎？

記住SDOI2017的教訓(xùn)

2、開(kāi)始想到的：

令f表示當(dāng)前合法的方案總數(shù)，那么如果當(dāng)前客棧的花費(fèi)<=p，那么f中的每一種方案，拿出一個(gè)客棧都可與當(dāng)前客棧形成新的方案

但這樣不對(duì)，比如1 2 ，1 3， 1 4， 2 3， 2 4,3 4 各拿出一個(gè)是1 1 1 2 2 ?3，總之有重復(fù)

然后就不繼續(xù)想了

下次思路出現(xiàn)問(wèn)題不要棄療，改

?

T3 mayan游戲

時(shí)間限制：3 s?? 內(nèi)存限制：128 MB

【問(wèn)題描述】
Mayan puzzle 是最近流行起來(lái)的一個(gè)游戲。游戲界面是一個(gè)7 行5 列的棋盤(pán)，上面堆放著一些方塊，方塊不能懸空堆放，即方塊必須放在最下面一行，或者放在其他方塊之上。游戲通關(guān)是指在規(guī)定的步數(shù)內(nèi)消除所有的方塊，消除方塊的規(guī)則如下：
1、 每步移動(dòng)可以且僅可以沿橫向（即向左或向右）拖動(dòng)某一方塊一格：當(dāng)拖動(dòng)這一方塊時(shí)，如果拖動(dòng)后到達(dá)的位置（以下稱(chēng)目標(biāo)位置）也有方塊，那么這兩個(gè)方塊將交換位置（參見(jiàn)輸入輸出樣例說(shuō)明中的圖6 到圖7）；如果目標(biāo)位置上沒(méi)有方塊，那么被拖動(dòng)的方塊將從原來(lái)的豎列中抽出，并從目標(biāo)位置上掉落（直到不懸空，參見(jiàn)下面圖1 和圖2）；

2、 任一時(shí)刻，如果在一橫行或者豎列上有連續(xù)三個(gè)或者三個(gè)以上相同顏色的方塊，則它們將立即被消除（參見(jiàn)圖1 到圖3）。

注意：
a) 如果同時(shí)有多組方塊滿(mǎn)足消除條件，幾組方塊會(huì)同時(shí)被消除（例如下面圖4，三個(gè)顏色為1 的方塊和三個(gè)顏色為2 的方塊會(huì)同時(shí)被消除，最后剩下一個(gè)顏色為2 的方塊）。
b) 當(dāng)出現(xiàn)行和列都滿(mǎn)足消除條件且行列共享某個(gè)方塊時(shí)，行和列上滿(mǎn)足消除條件的所有方塊會(huì)被同時(shí)消除（例如下面圖5 所示的情形，5 個(gè)方塊會(huì)同時(shí)被消除）。

3、 方塊消除之后，消除位置之上的方塊將掉落，掉落后可能會(huì)引起新的方塊消除。注意：掉落的過(guò)程中將不會(huì)有方塊的消除。

上面圖1 到圖3 給出了在棋盤(pán)上移動(dòng)一塊方塊之后棋盤(pán)的變化。棋盤(pán)的左下角方塊的坐標(biāo)為（0, 0），將位于（3, 3）的方塊向左移動(dòng)之后，游戲界面從圖1 變成圖2 所示的狀態(tài)，此時(shí)在一豎列上有連續(xù)三塊顏色為4 的方塊，滿(mǎn)足消除條件，消除連續(xù)3 塊顏色為4 的方塊后，上方的顏色為3 的方塊掉落，形成圖3 所示的局面。

【輸入】
輸入文件mayan.in，共6 行。
第一行為一個(gè)正整數(shù)n，表示要求游戲通關(guān)的步數(shù)。
接下來(lái)的5 行，描述7*5 的游戲界面。每行若干個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，每行以一個(gè)0 結(jié)束，自下向上表示每豎列方塊的顏色編號(hào)（顏色不多于10 種，從1 開(kāi)始順序編號(hào)，相同數(shù)字表示相同顏色）。
輸入數(shù)據(jù)保證初始棋盤(pán)中沒(méi)有可以消除的方塊。

【輸出】
輸出文件名為mayan.out。

如果有解決方案，輸出n 行，每行包含3 個(gè)整數(shù)x，y，g，表示一次移動(dòng)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，其中（x，y）表示要移動(dòng)的方塊的坐標(biāo)，g 表示移動(dòng)的方向，1 表示向右移動(dòng)，-1 表示向左移動(dòng)。注意：多組解時(shí)，按照x 為第一關(guān)健字，y 為第二關(guān)健字，1優(yōu)先于-1，給出一組字典序最小的解。游戲界面左下角的坐標(biāo)為（0，0）。
如果沒(méi)有解決方案，輸出一行，包含一個(gè)整數(shù)-1。

【輸入輸出樣例1】

mayan.in

3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0

mayan.out

2 1 1
3 1 1
3 0 1

【輸入輸出樣例說(shuō)明】
按箭頭方向的順序分別為圖6 到圖11

樣例輸入的游戲局面如上面第一個(gè)圖片所示，依次移動(dòng)的三步是：（2，1）處的方格向右移動(dòng)，（3，1）處的方格向右移動(dòng)，（3，0）處的方格向右移動(dòng)，最后可以將棋盤(pán)上所有方塊消除。

【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，初始棋盤(pán)上的方塊都在棋盤(pán)的最下面一行；
對(duì)于100%的數(shù)據(jù)，0 < n≤5。

?

模擬、dfs

貌似好像只有一個(gè)剪枝：

若當(dāng)前有某種顏色的方塊數(shù)量為1或2，則reutrn

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[5][7],k[11],ans[6][4]; int n,tot[11]; bool ok; void clear(); void down()//可與消除形成連鎖反應(yīng)的下降 {int sum;bool okk=false;for(int i=0;i<5;i++){sum=0;for(int j=0;j<7;j++){if(sum==k[i]) break;if(a[i][j]){sum++;continue;}else{int k=j;while(!a[i][k]) k++;swap(a[i][j],a[i][k]);sum++;okk=true;}}}if(okk) clear(); } void down2()//左移右移的下降，不消除 {int sum;for(int i=0;i<5;i++){sum=0;for(int j=0;j<7;j++){if(sum==k[i]) break;if(a[i][j]){sum++;continue;}else{int k=j;while(!a[i][k]) k++;swap(a[i][j],a[i][k]);sum++;}}} } void left_down(int x,int y)//左移 {swap(a[x][y],a[x-1][y]);k[x-1]++;k[x]--;down2(); } void right_down(int x,int y)//右移 {swap(a[x][y],a[x+1][y]);k[x+1]++;k[x]--;down2(); } void clear() {bool ok1,ok2,ok3=false;for(int i=0;i<5;i++)for(int j=0;j<k[i];j++){if(!a[i][j]) continue;ok1=ok2=false;int r=i+1,u=j+1;for(;r<5;r++) if(a[r][j]!=a[i][j]) break; r--;//橫著 for(;u<5;u++) if(a[i][u]!=a[i][j]) break; u--;//豎著 if(r-i+1>=3) ok1=true;if(u-j+1>=3) ok2=true;if(ok1){ok3=true;int down,up;for(int s=i;s<=r;s++) {for(down=j-1;down>=0;down--)//只有橫著的時(shí)候才有可能出現(xiàn)與豎著的共用的情況 if(a[s][j]!=a[s][down]) break;down++;for(up=j+1;up<7;up++)if(a[s][j]!=a[s][up]) break;up--;a[s][j]=0,k[s]--;if(up-down+1>=3) for(int t=down;t<=up;t++) if(a[s][t])a[s][t]=0,k[s]--;}}if(ok2){ok3=true;for(int t=j;t<=u;t++) if(a[i][t]){a[i][t]=0; k[i]--;}}}if(ok3) down();} bool empty() {for(int i=0;i<5;i++)for(int j=0;j<7;j++)if(a[i][j]) return false;return true; } bool check1()//若一種顏色的數(shù)量為1或2，則不合法 {memset(tot,0,sizeof(tot));for(int i=0;i<5;i++)for(int j=0;j<7;j++)tot[a[i][j]]++;for(int i=1;i<=10;i++) if(tot[i]==1||tot[i]==2) return false;return true; } void dfs(int now) {if(ok) return;if(now==n+1){if(empty()){for(int i=1;i<=n;i++)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]);ok=true;}return;}if(!check1()) return;int b[5][7];int c[11];memcpy(b,a,sizeof b);memcpy(c,k,sizeof c);for(int i=0;i<5;i++)for(int j=0;j<k[i];j++){if(!a[i][j]) continue;if(i!=4&&a[i+1][j]&&a[i][j]!=a[i+1][j])//向右交換 {ans[now][3]=1;ans[now][1]=i;ans[now][2]=j;swap(a[i][j],a[i+1][j]);clear();dfs(now+1);memcpy(a,b,sizeof a);memcpy(k,c,sizeof k);}else if(i!=4&&a[i+1][j]==0&&a[i][j]!=a[i+1][j]) //向右移 {ans[now][3]=1;ans[now][1]=i;ans[now][2]=j;right_down(i,j);clear();dfs(now+1);memcpy(a,b,sizeof a);memcpy(k,c,sizeof k);}if(i==4&&a[i-1][j]&&a[i][j]!=a[i-1][j])//向左交換 {ans[now][3]=-1;ans[now][1]=i;ans[now][2]=j;swap(a[i][j],a[i-1][j]);clear();dfs(now+1);memcpy(a,b,sizeof a);memcpy(k,c,sizeof k);} else if(i&&a[i-1][j]==0&&a[i-1][j]!=a[i][j]) //向左移 {ans[now][3]=-1;ans[now][1]=i;ans[now][2]=j;left_down(i,j);clear();dfs(now+1);memcpy(a,b,sizeof a);memcpy(k,c,sizeof k);}} } int main() {/*freopen("mayan.in","r",stdin);freopen("mayan.out","w",stdout);*/scanf("%d",&n);int x,j;for(int i=0;i<5;i++){j=0;while(1){scanf("%d",&x);if(!x) {k[i]=j;//橫坐標(biāo)為i的方塊數(shù)量 break;}a[i][j]=x;j++;} }dfs(1);if(!ok) printf("-1");return 0; } View Code

輸出先輸出坐標(biāo)，在輸出移動(dòng)方向

不看好題，先輸出了方向

轉(zhuǎn)載于:https://www.cnblogs.com/TheRoadToTheGold/p/6693781.html

總結(jié)

以上是生活随笔為你收集整理的NOIP2011 提高组 Day1的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。