蓝桥杯刷题

P8802 [蓝桥杯 2022 国 B] 出差（迪杰斯特拉）

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, m;
const int N = 1010, M = 2 * 10010;
int a[N];
bool st[N]; 
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dist[N];
typedef pair<int, int>PII;
int dijkstra(){memset(dist, 0x3f, sizeof(dist));dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII> > heap;heap.push({0, 1});while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if(st[ver])continue;st[ver] = true;for(int i = h[ver]; i != -1; i = ne[i]){int j = e[i];int distt = w[i] + distance; if(j != n)distt += a[j];if(dist[j] > distt){dist[j] = distt;heap.push({dist[j], j});}}}if(dist[n] == 0x3f3f3f3f)return -1;else return dist[n];
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;memset(h, -1, sizeof(h));for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= m; i++){int u, v, c; cin >> u >> v >> c;add(u, v, c);add(v, u, c); }int t = dijkstra();cout << t << endl;return 0;
}

P8799 [蓝桥杯 2022 国 B] 齿轮

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n, q;
const int N = 200010;
int a[N], ans[N], mp[N];
int flag;
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> q;for(int i = 1; i <= n; i++){cin >> a[i];mp[a[i]]++;}sort(a + 1, a + n + 1);for(int i = 1; i <= n; i++){if(i > 1 && a[i] == a[i - 1]){flag = 1;continue;}for(int j = a[i]; j <= a[n]; j += a[i]){if(mp[j]){ans[j / a[i]] = 1;}}}while(q--){int x; cin >> x;if(x == 1){if(flag)cout << "YES" << endl;else cout << "NO" << endl;continue;}if(ans[x])cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

P9428 [蓝桥杯 2023 国 B] 逃跑

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, m;
const int N = 1000010;
double p, ans, dp[N];
int flag[N];//跳点 
struct node{int h, ne, e;
};
int h[N], ne[N << 1], e[N << 1], idx;
void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa, double pp){if(flag[fa])pp *= p;if(u != 1){if(flag[fa])dp[u] = dp[fa] + 1;else dp[u] = dp[fa] + pp;}ans += dp[u];for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa)continue;dfs(j, u, pp);}pp /= p;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m >> p;memset(h, -1, sizeof(h)); for(int i = 1; i < n; i++){int u, v; cin >> u >> v;add(u, v), add(v, u);} for(int i = 1; i <= m; i++){int u; cin >> u;flag[u] = true;}dfs(1, 0, 1);cout << fixed << setprecision(2) << ans / n << endl;return 0;
}

P8804 [蓝桥杯 2022 国 B] 故障

注意比较doule时候精度丢失

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, m, k;
const int N = 520;
double a[N], dp[N];
double b[N][N];
bool st[N];
struct node{int id;double ans;
}no[N];
bool cmp(node a, node b){if(fabs(a.ans - b.ans) > 1e-6)return a.ans > b.ans;return a.id < b.id;
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){double x; cin >> x;b[i][j] = x / 100;}}cin >> k;while(k--){int x; cin >> x;st[x] = true;}for(int i = 1; i <= n; i++){dp[i] = a[i];for(int j = 1; j <= m; j++){if(st[j])dp[i] *= b[i][j];else dp[i] *= (1 - b[i][j]);}}double sum = 0;for(int i = 1; i <= n; i++)sum += dp[i];for(int i = 1; i <= n; i++){no[i].id = i;no[i].ans = dp[i] * 100 / sum;}sort(no + 1, no + n + 1, cmp);for(int i = 1; i <= n; i++){cout << no[i].id << " " << fixed << setprecision(2) << no[i].ans << endl;}return 0;
}

P8800 [蓝桥杯 2022 国 B] 卡牌

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 200010;
int n, m;
struct node{int a, b;
}no[N];
int maxx, minn = 1e18;
bool cmp(node a, node b){if(a.a != b.a)return a.a < b.a;return a.b < b.b;
}
bool check(int x){int sum = 0;for(int i = 1; no[i].a < x && i <= n; i++){if(x - no[i].a <= no[i].b){sum += x - no[i].a;}else return false;}if(sum <= m)return true;return false;
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++)cin >> no[i].a;for(int i = 1; i <= n; i++){cin >> no[i].b;minn = min(minn, no[i].a);maxx = max(maxx,  no[i].b + no[i].a);}sort(no + 1, no + n + 1, cmp);int l = minn - 1, r = maxx + 1;while(l + 1 != r){int mid = l + r >> 1;if(check(mid))l = mid;else r = mid;}cout << l << endl;return 0;
}

P8806 [蓝桥杯 2022 国 B] 搬砖

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 200010;
int dp[N];
struct node{int w, v;
}no[N];
int n;
bool cmp(node a, node b){return a.v + a.w < b.v + b.w;
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i++)cin >> no[i].w >> no[i].v;sort(no + 1, no + n + 1, cmp);int ans = 0;for(int i = 1; i <= n; i++){for(int j = no[i].v + no[i].w; j >= no[i].w; j--){dp[j] = max(dp[j], dp[j - no[i].w] + no[i].v);ans = max(ans, dp[j]);}}cout << ans << endl;return 0;
}