【算法題解】部分洛谷題解(下)

前言

本篇為我做過的洛谷題的部分題解，大多是我認為比較具有代表性的或者比較有意思的題目，包含我自己的思考過程和想法。

[NOIP2001 提高組] 一元三次方程求解

題目描述

有形如： $a x^3 + b x^2 + c x + d = 0$ 這樣的一個一元三次方程。給出該方程中各項的系數（ $a, b, c, d$ 均為實數），并約定該方程存在三個不同實根（根的范圍在 $? 100$ 至 $100$ 之間），且根與根之差的絕對值 $\ge 1$ 。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數點后 $2$ 位。

提示：記方程 $f (x) = 0$ ，若存在 $2$ 個數 $x_1$ 和 $x_2$ ，且 $x_1 < x_2$ ， $f(x_1) \times f(x_2) < 0$ ，則在 $x_1, x_2)$ 之間一定有一個根。

輸入格式

一行， $4$ 個實數 $a, b, c, d$ 。

輸出格式

一行， $3$ 個實根，從小到大輸出，并精確到小數點后 $2$ 位。

樣例 #1

樣例輸入 #1

1 -5 -4 20

樣例輸出 #1

-2.00 2.00 5.00

提示

【題目來源】

NOIP 2001 提高組第一題

這題是典型的二分查找法，因為題目要求求出近似解(保留小數點后兩位，)，所以二分查找的邊界需要注意一下。是當r-l<eps時，這個eps指一個很小的值，要比0.01要小，這里eps=1e-4，就認為找到了近似解，但是此時f(mid)并不等于0。

開始先一個for循環，也是題目提示我們的，從-100到100，然后利用高中學的零點定理，判斷(i,i+1)這個區間內有沒有零點，然后再對這個區間使用二分查找法。

完整代碼

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define eps 1e-4
double a,b,c,d;
double f(double x){return a*x*x*x+b*x*x+c*x+d;
}
int main(){double y;cin>>a>>b>>c>>d;for(int i=-100;i<=100;i++){if(fabs(f(i*1.0))<eps){printf("%.2lf ",i*1.0);continue;}if(fabs(f((i+1)*1.0))<eps)continue;if(f(i)*f(i+1)<0){double l=i*1.0,r=(i+1)*1.0,mid;while(r-l>eps){mid=(l+r)/2;if(f(l)*f(mid)<0) r=mid;if(f(mid)*f(r)<0) l=mid;if(f(mid)==0) break;}printf("%.2lf ",mid);}}return 0;
}

NASA的食物計劃

題目背景

NASA（美國航空航天局）因為航天飛機的隔熱瓦等其他安全技術問題一直大傷腦筋，因此在各方壓力下終止了航天飛機的歷史，但是此類事情會不會在以后發生，誰也無法保證。所以，在遇到這類航天問題時，也許只能讓航天員出倉維修。但是過多的維修會消耗航天員大量的能量，因此 NASA 便想設計一種食品方案，使體積和承重有限的條件下多裝載一些高卡路里的食物。

題目描述

航天飛機的體積有限，當然如果載過重的物品，燃料會浪費很多錢，每件食品都有各自的體積、質量以及所含卡路里。在告訴你體積和質量的最大值的情況下，請輸出能達到的食品方案所含卡路里的最大值，當然每個食品只能使用一次。

輸入格式

第一行 $2$ 個整數，分別代表體積最大值 $h$ 和質量最大值 $t$ 。

第二行 $1$ 個整數代表食品總數 $n$ 。

接下來 $n$ 行每行 $3$ 個數體積 $h_i$ ，質量 $t_i$ ，所含卡路里 $k_i$ 。

輸出格式

一個數，表示所能達到的最大卡路里（int 范圍內）

樣例 #1

樣例輸入 #1

樣例輸出 #1

提示

對于 $100\%$ 的數據， $h,t,h_i,t_i \le 400$ ， $\le 50$ ， $k_i \le 500$ 。

這道題是一道多維背包問題，一個商品有價值，重量，體積三個屬性。把最初的01背包的二維數組改成三維數組即可。

這里使用了數組壓縮，簡單01背包變為一維數組，多重背包就是二維數組。注意代表重量的j和代表體積的k要從后往前循環。

完整代碼

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int MAX(int a,int b){if(a>b) return a;else return b;
}
int main(){int k,i,j,h,m,n,s[51],v[51],c[51],f[401][401];memset(f,0,sizeof(f));scanf("%d%d%d",&m,&h,&n);for(i=1;i<=n;i++)scanf("%d%d%d",&v[i],&s[i],&c[i]);for(i=1;i<=n;i++)for(j=m;j>=1;j--)if(v[i]<=j) for(k=h;k>=1;k--)if(s[i]<=k) f[j][k]=MAX(f[j][k],f[j-v[i]][k-s[i]]+c[i]);printf("%d",f[m][h]);	  return 0;	 
}

[NOIP2007 普及組] 守望者的逃離

題目背景

NOIP2007 普及組 T3

題目描述

惡魔獵手尤迪安野心勃勃，他背叛了暗夜精靈，率領深藏在海底的娜迦族企圖叛變。

守望者在與尤迪安的交鋒中遭遇了圍殺，被困在一個荒蕪的大島上。

為了殺死守望者，尤迪安開始對這個荒島施咒，這座島很快就會沉下去。到那時，島上的所有人都會遇難。

守望者的跑步速度為 $17 m / s$ ，以這樣的速度是無法逃離荒島的。慶幸的是守望者擁有閃爍法術，可在 $1 s$ 內移動 $60 m$ ，不過每次使用閃爍法術都會消耗魔法值 $10$ 點。守望者的魔法值恢復的速度為 $4$ 點每秒，只有處在原地休息狀態時才能恢復。

現在已知守望者的魔法初值 $M$ ，他所在的初始位置與島的出口之間的距離 $S$ ，島沉沒的時間 $T$ 。你的任務是寫一個程序幫助守望者計算如何在最短的時間內逃離荒島，若不能逃出，則輸出守望者在剩下的時間內能走的最遠距離。

注意：守望者跑步、閃爍或休息活動均以秒為單位，且每次活動的持續時間為整數秒。距離的單位為米。

輸入格式

輸入數據共一行三個非負整數，分別表示 $M$ ， $S$ ， $T$ 。

輸出格式

輸出數據共兩行。

第一行一個字符串 $\texttt{Yes}$ 或 $\texttt{No}$ ，即守望者是否能逃離荒島。

第二行包含一個整數。第一行為 $\texttt{Yes}$ 時表示守望者逃離荒島的最短時間；第一行為 $\texttt{No}$ 時表示守望者能走的最遠距離。

樣例 #1

樣例輸入 #1

39 200 4

樣例輸出 #1

No
197

樣例 #2

樣例輸入 #2

36 255 10

樣例輸出 #2

Yes
6

提示

對于 $30\%$ 的數據， $\le T \le 10$ ，$ 1 \le S \le 100$；

對于 $50\%$ 的數據， $\le T \le 10^3$ ，$ 1 \le S \le 10^4$；

對于 $100\%$ 的數據， $\le T \le 3\times 10^5$ ， $\le M \le 10^3$ ，$ 1 \le S \le 10^8$。

這道題應該屬于動態規劃，像是基于時間軸的動態規劃，不太常規，沒有一個大的動態規劃狀態轉移方程。

定義一個數組f[i]，代表第i秒能走的最遠距離。

首先能閃爍就閃爍，沒能量了就停下來休息回能，循環一遍時間t，記錄所有的f[i]。
然后再循環一遍時間t，這次循環用普通的走路(~~17m/s他簡直就是超人~~)。每次走路發現如果比閃爍方法更優(更遠)的話，就更新f[i]，可以用一個式子來表示就是f[i]=Max(f[i],f[i-1]+17)。如果到了終點就退出然后輸出Yes。

完整代碼

#include<cstdio>
#include<cstring>
using namespace std;
int Max(int a,int b){return a>b?a:b;
}
int main(){int m,t,s,f[300010];memset(f,0,sizeof(f));scanf("%d%d%d",&m,&s,&t);for(int i=1;i<=t;i++){if(m>=10){m-=10;f[i]=f[i-1]+60;}else{m+=4;f[i]=f[i-1];}}for(int i=1;i<=t;i++){f[i]=Max(f[i-1]+17,f[i]);if(f[i]>=s){printf("Yes\n%d",i);return 0;}}printf("No\n%d",f[t]);return 0;
}

[USACO10OCT] Lake Counting S

題面翻譯

由于近期的降雨，雨水匯集在農民約翰的田地不同的地方。我們用一個 $N\times M(1\leq N\leq 100, 1\leq M\leq 100)$ 的網格圖表示。每個網格中有水（W）或是旱地（.）。一個網格與其周圍的八個網格相連，而一組相連的網格視為一個水坑。約翰想弄清楚他的田地已經形成了多少水坑。給出約翰田地的示意圖，確定當中有多少水坑。

輸入第 $1$ 行：兩個空格隔開的整數： $N$ 和 $M$ 。

第 $2$ 行到第 $N + 1$ 行：每行 $M$ 個字符，每個字符是 W 或 .，它們表示網格圖中的一排。字符之間沒有空格。

輸出一行，表示水坑的數量。

題目描述

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

輸入格式

Line 1: Two space-separated integers: N and M * Lines 2…N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

輸出格式

Line 1: The number of ponds in Farmer John’s field.

樣例 #1

樣例輸入 #1

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

樣例輸出 #1

提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

很好的題目，使我英語水平提升

這個題目更是深搜和廣搜中的典中典。這里我用深搜來寫。

首先for循環遍歷整個地圖，遇到湖水就開始深搜并且ans++。dfs搜索九宮格的8個方向，把是湖水的地方，就把他改成陸地。遍歷整張地圖后ans就是湖泊的數量。

完整代碼

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,map[110][110]={0};
int dx[8]={0, 0, 1, 1, 1,-1,-1,-1};
int dy[8]={1,-1, 1,-1, 0, 0, 1,-1};
void dfs(int x,int y){for(int k=0;k<8;k++){int tx=x+dx[k];int ty=y+dy[k];if(tx<1 || ty<1 || tx>n || ty>m)continue;if(map[tx][ty]==1){map[tx][ty]=0;dfs(tx,ty);}	}
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){char ch;cin>>ch;if(ch=='W') map[i][j]=1;else map[i][j]=0;}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)
//			printf("%d",map[i][j]);
//		printf("\n");
//		}	int ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(map[i][j]==1){map[i][j]=0;ans++;dfs(i,j);}printf("%d",ans);return 0;
}

單詞方陣

題目描述

給一 $\times n$ 的字母方陣，內可能蘊含多個 yizhong 單詞。單詞在方陣中是沿著同一方向連續擺放的。擺放可沿著 $8$ 個方向的任一方向，同一單詞擺放時不再改變方向，單詞與單詞之間可以交叉，因此有可能共用字母。輸出時，將不是單詞的字母用 * 代替，以突出顯示單詞。

輸入格式

第一行輸入一個數 $n$ 。 $\le n \le 100)$ 。

第二行開始輸入 $\times n$ 的字母矩陣。

輸出格式

突出顯示單詞的 $\times n$ 矩陣。

樣例 #1

樣例輸入 #1

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

樣例輸出 #1

*******
*******
*******
*******
*******
*******
*******

樣例 #2

樣例輸入 #2

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

樣例輸出 #2

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

純純暴力枚舉，就是for循環有點多。

因為是字符輸入，輸入的時候記得把回車給過濾掉。

完整代碼

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){int n;char map[110][110];int b[110][110];memset(b,0,sizeof(b));const char str[] = "yizhong";const int len = 7;//cout<<str<<endl;scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cin>>map[i][j];getchar(); // 讀掉多余的回車 }int dx[8]={0,1,0,-1,1,-1,1,-1};int dy[8]={1,0,-1,0,1,1,-1,-1};for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(map[i][j]=='y'){for(int k=0;k<8;k++){int tx=i,ty=j;int flag = 0;for(int l=1;l<len;l++){tx += dx[k];ty += dy[k];if(tx <= 0 || ty <=0 || tx > n || ty > n){flag = 1;break;}if(map[tx][ty]!=str[l]){flag = 1;break;}}if(flag)continue;// 代表匹配出了一個yizhong tx=i,ty=j; //cout<<i<<" "<<j<<endl;for(int l=0;l<len;l++){b[tx][ty] = 1;tx += dx[k];ty += dy[k];}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(b[i][j])printf("%c",map[i][j]);elseprintf("*");printf("\n");}return 0;
}

[NOIP2000 提高組] 單詞接龍

題目背景

注意：本題為上古 NOIP 原題，不保證存在靠譜的做法能通過該數據范圍下的所有數據。

本題為搜索題，本題不接受 hack 數據。關于此類題目的詳細內容

NOIP2000 提高組 T3

題目描述

單詞接龍是一個與我們經常玩的成語接龍相類似的游戲，現在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍”中出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如 beast 和 astonish，如果接成一條龍則變為 beastonish，另外相鄰的兩部分不能存在包含關系，例如 at 和 atide 間不能相連。

輸入格式

輸入的第一行為一個單獨的整數 $n$ 表示單詞數，以下 $n$ 行每行有一個單詞，輸入的最后一行為一個單個字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在。

輸出格式

只需輸出以此字母開頭的最長的“龍”的長度。

樣例 #1

樣例輸入 #1

5
at
touch
cheat
choose
tact
a

樣例輸出 #1

提示

樣例解釋：連成的“龍”為 atoucheatactactouchoose。

$\le 20$ 。

這是一道關于字符串的搜索題，自然也要用上string的相關的函數，搜索用DFS。算上是一道好題。

完整代碼

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int n,book[30],ans=0,x;
char fletter;
string word[30];
bool check(string s1,string s2){int len1,len2;len1=s1.size();len2=s2.size();int j=0;for(int i=len1-1;i>=1;i--){j++;if(j==len2) break;if(s1.substr(i)==s2.substr(0,j)){x=j;return true;}				}return false;	
}
void dfs(int len,int last){if(len>ans) ans=len;for(int i=1;i<=n;i++)if(book[i]<2 && check(word[last],word[i])){book[i]++;dfs(len+word[i].size()-x,i);book[i]--;}	return ;
}
int main(){scanf("%d",&n);memset(book,0,sizeof(book));for(int i=1;i<=n;i++)cin>>word[i];cin>>fletter;for(int i=1;i<=n;i++)if(word[i][0]==fletter){book[i]=1;dfs(word[i].size(),i);memset(book,0,sizeof(book));}printf("%d",ans);	return 0;
}

迷宮

題目描述

給定一個 $\times M$ 方格的迷宮，迷宮里有 $T$ 處障礙，障礙處不可通過。

在迷宮中移動有上下左右四種方式，每次只能移動一個方格。數據保證起點上沒有障礙。

給定起點坐標和終點坐標，每個方格最多經過一次，問有多少種從起點坐標到終點坐標的方案。

輸入格式

第一行為三個正整數 $N, M, T$ ，分別表示迷宮的長寬和障礙總數。

第二行為四個正整數 $SX, S Y, FX, F Y$ ， $SX, S Y$ 代表起點坐標， $FX, F Y$ 代表終點坐標。

接下來 $T$ 行，每行兩個正整數，表示障礙點的坐標。

輸出格式

輸出從起點坐標到終點坐標的方案總數。

樣例 #1

樣例輸入 #1

2 2 1
1 1 2 2
1 2

樣例輸出 #1

提示

對于 $100\%$ 的數據， $\le N,M \le 5$ ， $\le T \le 10$ ， $\le SX,FX \le n$ ， $\le SY,FY \le m$ 。

也是一道典型的搜索題，這里我用DFS，把輸入數據轉換成一張map地圖，用01標記可以走和不可以走。用book數組標記是否走過這塊地方。

在dfs遞歸的地方一定要記得回溯，把book[tx][ty] = 0改回來。dfs深搜邊界就是xy到了終點，ans++。最后輸出ans。

還有一個坑，就是起點要標記為已經走過了，book[sx][sy] = 1。不然會有部分測試點過不了。

完整代碼

#include<cstdio>
#include<cstring>
using namespace std;
int map[10][10],book[10][10];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,fx,fy,ans=0;
void dfs(int x,int y){if(x==fx && y==fy){ans++;return ;}for(int k=0;k<4;k++){int tx = x + dx[k];int ty = y + dy[k];if(tx<=0 || ty<=0 || tx>n || ty>m)continue;if(map[tx][ty] == 0 && book[tx][ty] == 0){book[tx][ty] = 1;dfs(tx,ty);book[tx][ty] = 0;}}
}
int main(){int t,sx,sy;memset(map,0,sizeof(map));scanf("%d%d%d%d%d%d%d",&n,&m,&t,&sx,&sy,&fx,&fy);for(int i=1;i<=t;i++){int x,y;scanf("%d%d",&x,&y);map[x][y] = 1;}memset(book,0,sizeof(book));book[sx][sy] = 1; // 不然就會是40分 dfs(sx,sy);		printf("%d",ans);return 0;
}