第十三屆藍橋杯B組c++國賽

A - 2022：

題目：

筆記：

一道經典的dp題：

（1）明確dp數組含義：

dp[i][j][k]: 表示前i個數字中選擇j個湊成k的方法數。

（2）確定狀態轉移方程：

dp[i][j][k] = dp[i - 1][j - 1][k - i] + dp[i - 1][j][k]

有兩種情況，如果當前遍歷到的數字i大于背包容量則肯定不取，如果小于則可以取。

（3）初始化：

由于后續的所有方法數都是依賴于底層組成0的方法數：

所以將第一層容量為0的背包都設置為1。

（4）遍歷順序：

就是從小到大遍歷即可，并未涉及狀態壓縮：

#include<bits/stdc++.h>
using namespace std;int main(){long long dp[2023][11][2023] = {0};for(int i = 0; i < 2023; i++){dp[i][0][0] = 1;}for(int i = 1; i < 2023; i++){for(int j = 1; j <= 10; j++){for(int k = 1; k < 2023; k++){if(i <= k){dp[i][j][k] = dp[i - 1][j - 1][k - i] + dp[i - 1][j][k];}else{dp[i][j][k] = dp[i - 1][j][k];}}}}cout << dp[2022][10][2022] << endl;return 0;
}

?B - 鐘表：

題目：

筆記：

簡單模擬題：

#include <bits/stdc++.h>
using namespace std;
int main()
{// 時針：// 360 / 12 = 30°// 30 / 60 = 0.5°// 0.5 / 60 = 1/120°// 分針：// 360 / 60 = 6°// 6 / 60 = 0.1°// 秒針：// 360 / 60 = 6°for(int i = 0; i <= 6; i++){for(int j = 0; j < 60; j++){for(int k = 0; k < 60; k++){double h = i * 30.0 + j / 2.0 + k / 120.0; // 6點附近double m = j * 6.0 + k / 10;double s = k * 6.0;double a = abs(m - h);double b = abs(s - m);if(a > 180){a = 360 - a;}if(b > 180){b = 360 - b;}if(a == 2 * b){if(i == 0 && j == 0 && k == 0){continue;}cout << i << " " << j << " " << k;}}}}return 0;
}

C - 0卡牌：

題目：

筆記：

這道題目有點貪心的意思：

我們的思路是優先將已有牌中數目最少的牌補齊：所以我們需要有一個數組來存儲已有牌的數目以及對應最多能夠補幾張：然后我們對該數組進行排序，優先補齊數量最少的牌查看是否能夠湊齊指定套數的牌：

D - 最大數字：

題目：

筆記：

為了更好地處理，我們先將數字轉換成字符串類型進行處理：

明確我們的目的：將數字改的盡可能的大，我們的限制條件是：opt_1操作次數不能超過A次，opt_2操作不能超過B次：我們可以先判斷opt_2的數量是否大于當前數字cur + 1，如果不大于就只選擇opt_1不再進行opt_2操作，如果當opt_2的數量大于cur + 1，那么就優先將opt_2的數量消耗掉，因為opt_2只能通過正好將cur變成9才會變大，而opt_1無論怎樣都會使數字變大。

#include <iostream>
#include <sstream>
using namespace std;
typedef long long ll;int main() {ll n, a, b;cin >> n >> a >> b;stringstream ss;ss << n;string str = ss.str();for (ll i = 0; i < str.size(); i++) {ll digit = str[i] - '0'; // 將字符轉換為整數if (b >= digit + 1) {b -= (digit + 1);str[i] = '9';} else {if (a <= 0) break;ll need = 9 - digit;if (need <= a) {str[i] = '9';a -= need;} else {str[i] = digit + a + '0'; // 將整數轉換回字符a = 0;break;}}}// 使用 stringstream 將字符串轉換為整數ll result;stringstream(str) >> result;cout << result << endl;return 0;
}

但是這么寫只過90%，

E - 出差：

這道題就是一個迪杰斯特拉的模板題,讓我們找到一條從城市1出發到達城市n的最短路徑，

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define int long long
typedef pair<int,int>PII;
const int N=1e5+5,M=2*N;
int h[N],e[M],ne[M],w[M],a[N],dist[N],vis[N],idx;
void add(int x,int y,int z){e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;//數組e是代表當前邊的終點//數組w是代表當前邊的權重//數組ne表示next的指針是只想同一起點的邊的下標
}
void dijkstra(){memset(dist,0x3f,sizeof dist);priority_queue<PII,vector<PII>,greater<PII> >q;q.push({0,1});dist[1]=0;while(q.size()){int dis=q.top().first;int s=q.top().second;q.pop();if(vis[s])continue;vis[s]=1;for(int i=h[s];~i;i=ne[i]){int j=e[i];if(dist[j]>dis+w[i]){dist[j]=dis+w[i];q.push({dist[j],j});}}}
}
signed main(){memset(h,-1,sizeof h);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];while(m--){int x,y,z;cin>>x>>y>>z;add(x,y,z+a[y]);add(y,x,z+a[x]); }dijkstra();cout<<dist[n]-a[n]<<endl;return 0;
}

#include<bits/stdc++.h>
using namespace std;int main(){int n, m;cin >> n >> m;vector<int> t(n + 1, 0);for(int i = 1; i <= n; i++){cin >> t[i];}// 存圖：vector<vector<int>> grid(n + 1, vector(n + 1, INT_MAX));for(int i = 1; i <= m; i++){int start, end, cost;cin >> start >> end >> cost;grid[start][end] = cost + t[end];grid[end][start] = cost + t[start];}priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;vector<bool> visited(n + 1, false);que.push(make_pair(0, 1));vector<int> mindist(n + 1, INT_MAX);mindist[1] = 0;while(!que.empty()){pair<int, int> cur = que.top(); que.pop();int end = cur.first;int start = cur.second;if(visited[start])  continue;visited[start] = true;for(int i = 1; i <= n; i++){if(!visited[i] && grid[start][i] != INT_MAX && mindist[start] + grid[start][i] < mindist[i]){mindist[i] = grid[start][i] + mindist[start];que.push(make_pair(mindist[i], i));}}}if(mindist[n] == INT_MAX){cout << -1;}else{cout << mindist[n] - t[n];}return 0;
}

注意優先隊列中元素排列的順序。

F - 費用報銷：

題目：

筆記：

#include <bits/stdc++.h>
using namespace std;const int N = 1010;
int f[N][N * 5];
int s[N], last[N];
int d[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};//每個月份的天數
int n, m, k;
struct Node
{int m, d, v, t;
} p[N];// 定義一個日期結構體：包含月份，天數，價值，相對年初的天數bool cmp(Node &a, Node &b)
{return a.t < b.t;
}int main()
{scanf("%d%d%d", &n, &m, &k);for (int i = 2; i <= 12; i++) s[i] = s[i - 1] + d[i - 1];// 前綴和計算當前月相對年初的天數// 為每一個日期結構體的t日期進行賦值：for (int i = 1; i <= n; i++){scanf("%d%d%d", &p[i].m, &p[i].d, &p[i].v);p[i].t = s[p[i].m] + p[i].d;}// 按日期結構的天數進行升序排列sort(p + 1, p + 1 + n, cmp);// 找出距離當前項目最近的可以選擇的項目的編號,因為當你遍歷到一個日期需要查看預支配對的上一個可行的日期。for (int i = 1; i <= n; i++)for (int j = 0; j < i; j++)if (p[i].t - p[j].t >= k)last[i] = j;for (int i = 1; i <= n; i++)for (int j = 0; j <= m; j++){    f[i][j] = f[i - 1][j]; // 不選第i個，狀態則為i-1if (p[i].v <= j && (p[i].t - p[i - 1].t) >= k)  // 如果選第i個，則要看背包是否裝得下才比較f[i][j] = max(f[i][j], f[i - 1][j - p[i].v] + p[i].v);}cout << f[n][m];return 0;
}

耗費大量精力也是終于復刻出來了：

這道題歸根到底就是一道01背包的題目，但是我們需要注意的是在我們對當前物品取與不取的選擇中，如果我們選擇取那么記憶化搜索調用上一個物品的最大金額dp[i - 1][j - v],這里并不僅僅是上一個物品，因為我們的限制條件是天數要大于等于k，所以上一個日期可能并沒有達到k，可能需要用到上上個日期或者上上上個日期，所以我們就需要注意到底是取哪一個日期作為i- 1，這里我們用到了一個last數組記錄每一個日期對應的上一個可選擇日期，我們利用一個快慢指針搜索距離當前日期最近的可選日期。然后就可以按正常的邏輯進行dp：

dp[i][j] = max(dp[i - 1][j], dp[last[i]][j - value] + value):

#include<bits/stdc++.h>
using namespace std;
struct date_m{int m, d, v, t;// t表示當前日期與年初的天數
};
// 用于結構體排序，將日期按距離年初的天數從小到大排序
bool com(date_m& a, date_m& b){return a.t < b.t;
}
// 每個月的日期，用來計算當前日期距年初的天數
int mon[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int sum(int x){int a = 0;for(int i = 1; i < x; i++){a += mon[i];}return a;
}int main(){int n, m, k;cin >> n >> m >> k;vector<date_m> date(n + 1);for(int i = 1; i <= n; i++){cin >> date[i].m >> date[i].d >> date[i].v;date[i].t = sum(date[i].m) + date[i].d;}sort(date.begin(), date.end(), com);//cout << date[4].t << endl;vector<int> last(n + 1, 0);for(int i = 2; i <= n; i++){for(int j = 1; j < i; j++){if((date[i].t - date[j].t) >= k){last[i] = j;}}}vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));for(int i = 1; i <= n; i++){for(int j = 0;j <= m; j++){dp[i][j] = dp[i - 1][j];if(j >= date[i].v){dp[i][j] = max(dp[i - 1][j], dp[last[i]][j - date[i].v] + date[i].v);}}}cout << dp[n][m] << endl;return 0;
}

H - 機房：

題目：

筆記：

就是迪杰斯特拉的模板題：

#include<bits/stdc++.h>
using namespace std;
const int Max = 1e5 + 5;int main(){int n, m;cin >> n >> m;vector<int> edge[Max];// 讀取 m 條邊for(int i = 0 ; i < n - 1; i++){int a, b;cin >> a >> b;edge[a].push_back(b);edge[b].push_back(a);}vector<int> res(m, 0);for(int i = 0; i < m; i++){int u, v;cin >> u >> v;priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;vector<int> mindist(n + 1, INT_MAX); // 使用 INT_MAX 初始化mindist[u] = 0;vector<bool> vis(n + 1, false);que.push(make_pair(0, u));while(!que.empty()){pair<int, int> cur = que.top(); que.pop();int cost = cur.first;int start = cur.second;if(vis[start])  continue;vis[start] = true;int len = edge[start].size();for(int j = 0; j < len; j++){int dot = edge[start][j];if( mindist[dot] > mindist[start] + len){mindist[dot] = mindist[start] + len;que.push(make_pair(mindist[dot], dot)); // 更新優先隊列}}}// 檢查是否存在路徑if(mindist[v] != INT_MAX) {res[i] = mindist[v] + edge[v].size();} else {res[i] = -1; // 如果不存在路徑，輸出 -1}}for(int i = 0; i < m; i++){cout << res[i] << endl;}return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int Max = 1e5 + 5;int main(){int n, m;cin >> n >> m;vector<int> edge[Max];// 讀取 m 條邊for(int i = 0 ; i < n - 1; i++){int a, b;cin >> a >> b;edge[a].push_back(b);edge[b].push_back(a);}vector<int> res(m, 0);for(int i = 0; i < m; i++){int u, v;cin >> u >> v;priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;vector<int> mindist(n + 1, INT_MAX); // 使用 INT_MAX 初始化mindist[u] = 0;vector<bool> vis(n + 1, false);que.push(make_pair(0, u));while(!que.empty()){pair<int, int> cur = que.top(); que.pop();int cost = cur.first;int start = cur.second;if(vis[start])  continue;vis[start] = true;int len = edge[start].size();for(int j = 0; j < len; j++){int dot = edge[start][j];if(!vis[dot] && mindist[dot] > mindist[start] + len){mindist[dot] = mindist[start] + len;que.push(make_pair(mindist[dot], dot)); // 更新優先隊列}}}// 檢查是否存在路徑if(mindist[v] != INT_MAX) {res[i] = mindist[v] + edge[v].size();} else {res[i] = -1; // 如果不存在路徑，輸出 -1}}for(int i = 0; i < m; i++){cout << res[i] << endl;}return 0;
}