C/C++編程（1~8級）全部真題?點這里

第1題：道路

N個以 1 … N 標號的城市通過單向的道路相連:。每條道路包含兩個參數：道路的長度和需要為該路付的通行費（以金幣的數目來表示）
Bob and Alice 過去住在城市 1.在注意到Alice在他們過去喜歡玩的紙牌游戲中作弊后，Bob和她分手了，并且決定搬到城市N。他希望能夠盡可能快的到那，但是他囊中羞澀。我們希望能夠幫助Bob找到從1到N最短的路徑，前提是他能夠付的起通行費。
時間限制：1000
內存限制：65536
輸入
第一行包含一個整數K, 0 <= K <= 10000, 代表Bob能夠在他路上花費的最大的金幣數。第二行包含整數N， 2 <= N <= 100, 指城市的數目。第三行包含整數R, 1 <= R <= 10000, 指路的數目. 接下來的R行，每行具體指定幾個整數S, D, L 和 T來說明關于道路的一些情況，這些整數之間通過空格間隔: S is 道路起始城市, 1 <= S <= N D is 道路終點城市, 1 <= D <= N L is 道路長度, 1 <= L <= 100 T is 通行費 (以金幣數量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起點和終點。
輸出
輸入結果應該只包括一行，即從城市1到城市N所需要的最小的路徑長度（花費不能超過K個金幣）。如果這樣的路徑不存在，結果應該輸出-1。
樣例輸入
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
樣例輸出
11

答案：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
struct Road
{int d,L,t;
};
int N,K,R;
vector < vector <Road> > G(110);//用二維數組表示臨界表，G[s]表示和s鄰接的路
int minLen;//全局變量，記錄最短的路徑長度
int totalCost;//當前狀態的花費
int totalLen;//當前狀態的長度
int visited[110];
int minL[110][10010];//minL[i][j]的意義是當到達i點是花費為j時的最短路徑
void Dfs(int s)
{if(s==N){minLen=min(minLen,totalLen);return ;}int len=G[s].size();for(int i=0;i<len;i++)//枚舉和s相鄰接額情況{Road r=G[s][i];if(!visited[r.d])//如果沒有被走過{/*下面三個if語句是三條剪枝條件*/if(totalCost+r.t>K)//如果當前花銷大于K了continue;if(totalLen+r.L>=minLen)//如果當前的路徑已經超過了已存在的最短路徑，那就沒必要往后dfs了continue;//如果存在兩種方式都到達同一點并且花銷相同，但是如果當前的長度大于另一種方式的長度，則continueif(totalLen+r.L>minL[r.d][totalCost+r.t])continue;minL[r.d][totalCost+r.t]=totalLen+r.L;visited[r.d]=1;totalCost+=r.t;totalLen+=r.L;Dfs(r.d);visited[r.d]=0;//因為可能存在多種方式的dfs的路徑，所以每次dfs之后都要還原到之前的狀態totalCost-=r.t;totalLen-=r.L;}}
}
int main()
{cin>>K>>N>>R;for(int i=0;i<R;i++){int s;Road r;cin>>s;cin>>r.d>>r.L>>r.t;G[s].push_back(r);}totalCost=0;totalLen=0;minLen=1<<30;//無窮大memset(visited,0,sizeof(visited));for(int i=1;i<=N;i++)for(int j=0;j<10010;j++)minL[i][j]=1<<30;visited[1]=1;Dfs(1);if(minLen<(1<<30))cout<<minLen<<endl;elsecout<<-1<<endl;return 0;
}

第2題：Freda的越野跑

Freda報名參加了學校的越野跑。越野跑共有N人參加，在一條筆直的道路上進行。這N個人在起點處站成一列，相鄰兩個人之間保持一定的間距。比賽開始后，這N個人同時沿著道路向相同的方向跑去。換句話說，這N個人可以看作x軸上的N個點，在比賽開始后，它們同時向x軸正方向移動。
假設越野跑的距離足夠遠，這N個人的速度各不相同且保持勻速運動，那么會有多少對參賽者之間發生“趕超”的事件呢？
時間限制：1000
內存限制：262144
輸入
第一行1個整數N。 第二行為N 個非負整數，按從前到后的順序給出每個人的跑步速度。 對于50%的數據，2<=N<=1000。 對于100%的數據，2<=N<=100000。
輸出
一個整數，表示有多少對參賽者之間發生趕超事件。
樣例輸入
5
1 3 10 8 5
樣例輸出
7
提示
我們把這5個人依次編號為A,B,C,D,E，速度分別為1,3,10,8,5。 在跑步過程中： B,C,D,E均會超過A，因為他們的速度都比A快； C,D,E都會超過B，因為他們的速度都比B快； C,D,E之間不會發生趕超，因為速度快的起跑時就在前邊。

答案：

#include <iostream>
#define N 100002
int a[N] = {0}, t[N] = {0};
long long c = 0;
void merge(int l, int m, int r) {int i = l, j = m + 1, k = l;while (i <= m && j <= r)if (a[i] > a[j])t[k++] = a[i++];else {t[k++] = a[j++];c += 1 + m - i;}while (i <= m)t[k++] = a[i++];while (j <= r)t[k++] = a[j++];for (i = l; i <= r; ++i)a[i] = t[i];
}
void divide(int l, int r) {int m;if (r > l) {m = (r + l) / 2;divide(l, m);divide(m + 1, r);merge(l, m, r);}
}
int main() {int n, i = 0;std::cin >> n;while (i < n)std::cin >> a[i++];divide(0, n - 1);std::cout << c;
}

第3題：Rainbow的商店

Rainbow開了一家商店，在一次進貨中獲得了N個商品。
已知每個商品的利潤和過期時間。
Rainbow每天只能賣一個商品，并且過期商品不能再賣。
Rainbow也可以選擇在每天出售哪個商品，并且一定可以賣出。
由于這些限制，Rainbow需要制定一份合理的售賣計劃。請你計算一下，Rainbow最終可以獲得的最大收益。
時間限制：1000
內存限制：262144
輸入
第一行兩個整數N。 接下來N行每行兩個整數，分別表示每個商品的利潤、過期時間。 1<=N,利潤,時間<=10000。
輸出
輸出一個整數，表示Rainbow最終可以獲得的最大收益。
樣例輸入
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10
樣例輸出
185
提示
第1天賣出20 第2天賣出100 第3天賣出10 第4天賣出50（實際上只要在第10天賣就可以） 第5天賣出5（實際上只要在第20天前賣就可以） 總計185 其它2件商品由于過期、每天只能賣一個的限制，在最優策略下應該不出售。

答案：

#include<iostream>
#include<algorithm>
#include<queue>
#pragma warning (disable:4996);
using namespace std;
int N;
struct Goods
{int w;int d;friend bool operator <(const Goods a, const Goods b){if (a.w != b.w){return a.w < b.w;//大的天數小的在前}else{return a.d > b.d;}}
}good[10005];
bool vis[10005] = {};
int main()
{cin >> N;priority_queue<Goods>que;int maxval=0;for (int i = 1; i <= N; i++){scanf("%d %d", &good[i].w, &good[i].d);que.push(good[i]);}while (!que.empty()){Goods now = que.top();que.pop();for (int i = now.d; i >= 1; i--){if (!vis[i]){vis[i] = 1;maxval += now.w;break;}}}printf("%d\n", maxval);return 0;
}

第4題：冰闊落

老王喜歡喝冰闊落。
初始時刻，桌面上有n杯闊落，編號為1到n。老王總想把其中一杯闊落倒到另一杯中，這樣他一次性就能喝很多很多闊落，假設杯子的容量是足夠大的。
有m 次操作，每次操作包含兩個整數x與y。
若原始編號為x 的闊落與原始編號為y的闊落已經在同一杯，請輸出"Yes"；否則，我們將原始編號為y 所在杯子的所有闊落，倒往原始編號為x 所在的杯子，并輸出"No"。
最后，老王想知道哪些杯子有冰闊落。
時間限制：10000
內存限制：65536
輸入
有多組測試數據，少于 5 組。 每組測試數據，第一行兩個整數 n, m (n, m<=50000)。接下來 m 行，每行兩個整數 x, y (1<=x, y<=n)。
輸出
每組測試數據，前 m 行輸出 “Yes” 或者 “No”。 第 m+1 行輸出一個整數，表示有闊落的杯子數量。 第 m+2 行有若干個整數，從小到大輸出這些杯子的編號。
樣例輸入
3 2
1 2
2 1
4 2
1 2
4 3
樣例輸出
No
Yes
2
1 3
No
No
2
1 4

答案：

#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000+5],cnt;
int root(int x)
{if(a[x]==x) return x;return root(a[x]);
}
void find(int l,int r)
{int ll=root(l),rr=root(r);if(ll==rr){printf("Yes\n");//cout<<"Yes"<<endl;}else{a[rr] =ll;cnt--;//cout<<"No"<<endl;printf("No\n");}
}
int main()
{int m,n,l,r;while(scanf("%d %d",&n,&m)!=EOF){cnt=n;for(int i=1;i<=n;i++){a[i]=i;}for(int i=1;i<=m;i++){scanf("%d %d",&l,&r);//cin>>l>>r;find(l,r);}printf("%d\n",cnt);//cout<<cnt<<endl;for(int i=1;i<=n;i++)if(a[i]==i) printf("%d ",i);//cout<<i<<" ";//cout<<endl;printf("\n");}return 0;}