蓝桥杯训练 补题

server/2025/3/1 7:41:21/

P8605 [蓝桥杯 2013] 网络寻路

        这个题之前写过，但是后面数据加强了，直接dfs是会超时的，这是就要用另外的解法了，题目要求只要三条边，那么就可以找中间的边，对于每组边，把他们作为中间边，对于总共的贡献就是(d[u[i]] - 1) * (d[v[i]] - 1) * 2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const double eps = 1e-8;int d[N] ,u[N] ,v[N];void solve() {int n ,m;cin >> n >> m;for (int i = 0 ; i < m ; i++) {cin >> u[i] >> v[i];d[u[i]]++;d[v[i]]++;}int ans = 0;for (int i = 0 ; i < m ; i++) {if (d[u[i]] > 1 and d[v[i]] > 1) ans += (d[u[i]] - 1) * (d[v[i]] - 1) * 2;}cout << ans << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}

P10429 [蓝桥杯 2024 省 B] 拔河

        求前缀和，然后对于每个前缀和进行判断，计算过的放入set，用lower_bound来找最接近和，然后更新ans

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const double eps = 1e-8;int sum[N];void solve() {int n;cin >> n;vector<int> a(n);for (int i = 0 ; i < n ; i++) {cin >> a[i];if (!i) sum[i] = a[i];else sum[i] = sum[i - 1] + a[i];}set<int> s;s.insert(sum[0]);int ans = LLONG_MAX;for (int i = 1 ; i < n ; i++) {for (int j = i ; j < n ; j++) {auto t = s.lower_bound(sum[j] - sum[i - 1]);if (t != s.end()) ans = min(ans ,*t - (sum[j] - sum[i - 1]));if (t != s.begin()) t-- ,ans = min(ans ,(sum[j] - sum[i - 1]) - *t);s.insert(sum[j] - sum[i - 1]);}}cout << ans << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}

P8804 [蓝桥杯 2022 国 B] 故障

        概率论，贝叶斯公式

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 105;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const double eps = 1e-8;struct Node {int x;double pp;
} ans[N];
double P[N] ,p[N][N];
bool vis[N];
int cmp(Node x ,Node y) {if (x.pp == y.pp) return x.x < y.x;return x.pp > y.pp;
}
void solve() {int n ,m ,k;cin >> n >> m;for (int i = 1 ; i <= n ; i++) cin >> P[i];for (int i = 1 ; i <= n ; i++) {for (int j = 1 ; j <= m ; j++) {cin >> p[i][j];}}cin >> k;for (int i = 0 ; i < k ; i++) {int x;cin >> x;vis[x] = 1;}double sum = 0;for (int i = 1 ; i <= n ; i++) {ans[i].x = i ,ans[i].pp = P[i];for (int j = 1 ; j <= m ; j++) {if (vis[j]) ans[i].pp *= p[i][j];else ans[i].pp *= (100 - p[i][j]);}sum += ans[i].pp;}sort(ans + 1, ans + n + 1 , cmp);for (int i = 1 ; i <= n ; i++) cout << ans[i].x << " " << fixed << setprecision(2) << ans[i].pp / sum * 100 << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}

P10909 [蓝桥杯 2024 国 B] 立定跳远

        二分，check函数写的有点问题，应该是当前桩和前一个桩之间的距离 ÷ 当前二分的跳跃距离向上取整，跳双倍距离可以视作多加一个桩

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};int n ,m;
int a[N];
bool check(int x) {int num = 0;for (int i = 1 ; i <= n ; i++) {if (a[i] - a[i - 1] <= x) continue;else {int cnt = (int)ceil((a[i] - a[i - 1]) * 1.0) / x;num += cnt - 1;}}return num <= m + 1;
}void solve() {cin >> n >> m;for (int i = 1 ; i <= n ; i++) cin >> a[i];int l = 0 ,r = a[n] + 1 ,ans;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) {r = mid - 1;ans = mid;}else l = mid + 1;}cout << ans << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}

P10418 [蓝桥杯 2023 国 A] 相连的边

        树形dp ，赛事写的只有95分，wa了一个点，后面用dfs写了一遍

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
struct Node {int v ,w;
};
vector<Node> g[N];
bool vis[N];
int ans = 0 ,res = 0;
void dfs(int x ,int step ,int fa) {if (step == 3) {ans = max(ans ,res);return;}for (auto [v,w] : g[x]) {if (v == fa) continue;res += w;dfs(v ,step + 1 ,x);res -= w;}
}
void solve() {int n;cin >> n;for (int i = 1 ; i < n ; i++) {int v ,w;cin >> v >> w;g[i + 1].push_back({v,w});g[v].push_back({i + 1, w});}for (int i = 1 ; i <= n ; i++) {res = 0;dfs(i ,0 ,-1);if (g[i].size() >= 3) {sort(g[i].begin() ,g[i].end() ,[](Node x ,Node y) {return x.w > y.w;});ans = max(ans ,g[i][0].w + g[i][1].w + g[i][2].w);}}cout << ans << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}

P9231 [蓝桥杯 2023 省 A] 平方差

        思维题，赛时的思路是对的，就是从2开始，每加4都不满足，但是没有考虑到内存，交了一发爆内存了，后面发现是可以直接计算的

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};void solve() {int l ,r;cin >> l >> r;cout << ((r + 1) / 2 - l / 2) + (r / 4 - (l - 1) / 4) << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}

P8700 [蓝桥杯 2019 国 B] 解谜游戏

又是一道思维题，这个赛时也是发现了的，但是全局数组忘记初始化了，而且是多组输入，导致wa了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 150;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const double eps = 1e-8;int y[4] ,g[4] ,r[4];void solve() {memset(y ,0 ,sizeof y); //***//memset(g ,0 ,sizeof g); //***//memset(r ,0 ,sizeof r); //***//string a ,b ,c;cin >> a >> b >> c;for (int i = 0 ; i < a.size() ; i++) {if (a[i] == 'Y') y[i % 4]++;else if (a[i] == 'G') g[i % 4]++;else r[i % 4]++;}for (int i = 0 ; i < b.size() ; i++) {if (b[i] == 'Y') y[i % 4]++;else if (b[i] == 'G') g[i % 4]++;else r[i % 4]++;}for (int i = 0 ; i < c.size() ; i++) {if (c[i] == 'Y') y[i % 4]++;else if (c[i] == 'G') g[i % 4]++;else r[i % 4]++;}for (int i = 0 ; i < 4 ; i++) {if (y[i] != 1 or r[i] != 2 or g[i] != 3) {cout << "NO" << endl;return;}}cout << "YES" << endl;
}
signed main(){IOSint O_O = 1;cin >> O_O;while(O_O--) solve();
}

P8769 [蓝桥杯 2021 国 C] 巧克力

赛时时间不多了，就直接交了发贪心，没想到拿了90分，赛后看一眼题解发现只要再加一个特判就能满分了，对于每一个当前的巧克力，我们先判断当前的巧克力是否比下一个的保质期长，是的话先把下一个买了 ，这样就能过了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const double eps = 1e-8;struct Node {int a ,b ,c;
};
int cmp(Node x ,Node y) {if (x.a == y.a) return x.b > y.b;return x.a < y.a;
}
void solve() {int n ,x;cin >> x >> n;vector<Node> a(n + 1);for (int i = 1 ; i <= n ; i++) cin >> a[i].a >> a[i].b >> a[i].c;sort(a.begin() + 1 ,a.end() ,cmp);int ans = 0 ,now = 0;for (int i = 1 ; i <= n ; i++) {if (a[i].b > a[i + 1].b) {while (now < a[i + 1].b and a[i + 1].c > 0) {ans += a[i + 1].a;a[i + 1].c--;now++;if(now >= x) {cout << ans << endl;return;}}}while (now < a[i].b and a[i].c > 0) {ans += a[i].a;a[i].c--;now++;if(now >= x) {cout << ans << endl;return;}}}cout << -1 << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}

P10579 [蓝桥杯 2024 国 A] 最长子段

这题赛时也是暴力骗了60pts，正解是前缀和加二分，固定r ，来找l ，满足条件的就更新答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define PII pair<int,int>
#define PSI pair<string,int>
#define PVI pair<vector<int>,int>
#define endl '\n'
#define mk make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define Pi acos(-1.0)
#define ull unsigned long long
int ls(int p){ return (p << 1) ;}
int rs(int p){ return (p << 1 | 1) ;}
inline int lowbit(int x) { return x & (-x) ;}
//(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const double eps = 1e-8;int a[N] ,sum[N] ,b[N];void solve() {int n ,x ,y ,z;cin >> n >> x >> y >> z;b[0] = LLONG_MAX;for (int i = 1 ; i <= n ; i++) {cin >> a[i];sum[i] = sum[i - 1] + a[i];b[i] = min(b[i - 1] ,sum[i - 1] - x * z * i);}int ans = 0;for (int i = 1 ; i <= n ; i++) {int res = sum[i] - x * y * i;int l = 0 ,r = i + 1 ,mid;while (l < r) {mid = (l + r) >> 1;if (b[mid] < res) r = mid;else l = mid + 1;}if(r <= i) ans = max(ans ,i - r + 1);}cout << ans << endl;
}
signed main(){IOSint O_O = 1;// cin >> O_O;while(O_O--) solve();
}


http://www.ppmy.cn/server/171147.html

相关文章

spring boot 连接FTP实现文件上传

spring boot 连接FTP实现文件上传

spring boot　连接FTP实现文件上传 maven&#xff1a; <!--ftp--><dependency><groupId>commons-net</groupId><artifactId>commons-net</artifactId><version>3.8.0</version></dependency>接口示例&#xff1a; ApiO…
阅读更多...
本地部署 DeepSeek-R1大模型详细教程(桌面客户端美观UI)

本地部署 DeepSeek-R1大模型详细教程(桌面客户端美观UI)

大家好&#xff01;今天我来分享一篇超级详细的教程&#xff0c;教你如何在本地部署 DeepSeek-R1 大模型&#xff0c;让你的电脑也能成为一个强大的 AI 工作站&#xff01;这篇文章会从零开始&#xff0c;手把手带你完成所有步骤&#xff0c;适合小白操作。废话不多说&#xff…
阅读更多...
智合同：数字化转型下的法律科技新引擎

智合同：数字化转型下的法律科技新引擎

在数字化转型的浪潮下&#xff0c;人工智能&#xff08;AI&#xff09;技术正深刻改变各行各业的运作方式&#xff0c;法律领域也不例外。作为法律科技的重要组成部分&#xff0c;“智合同”&#xff08;合同智能应用品牌&#xff0c;数字化工具&#xff09;正在成为企业降本增…
阅读更多...
SeaCMS V9海洋影视管理系统报错注入

SeaCMS V9海洋影视管理系统报错注入

漏洞背景 SQL 注入攻击是当前网络安全中最常见的一种攻击方式&#xff0c;攻击者可以利用该漏洞访问或操作数据库&#xff0c;造成数据泄露或破坏。通常发生在开发人员未能正确处理用户输入时。 在 SeaCMS V9 中&#xff0c;用户输入&#xff08;如登录、评论、分页、ID 等&a…
阅读更多...
机器学习--（随机森林，线性回归）

机器学习--（随机森林，线性回归）

一、集成学习方法之随机森林 集成学习的基本思想就是将多个分类器组合&#xff0c;从而实现一个预测效果更好的集成分类器。集成算法可以说从一方面验证了中国的一句老话&#xff1a;三个臭皮匠&#xff0c;赛过诸葛亮。集成算法大致可以分为&#xff1a;Bagging&#xff0c;B…
阅读更多...
腾讯云cos 临时密钥 适用于前端直传等临时授权场景

腾讯云cos 临时密钥 适用于前端直传等临时授权场景

composer添加 "qcloud_sts/qcloud-sts-sdk": "^3.0","tencentcloud/sts": "^3.0"执行 composer require qcloud_sts/qcloud-sts-sdk composer require tencentcloud/sts然后就可以直接使用了 $params参数可以看官网去设置&#xff1…
阅读更多...
深度学习（5）-卷积神经网络

深度学习（5）-卷积神经网络

我们将深入理解卷积神经网络的原理&#xff0c;以及它为什么在计算机视觉任务上如此成功。我们先来看一个简单的卷积神经网络示例&#xff0c;它用干对 MNIST数字进行分类。这个任务在第2章用密集连接网络做过&#xff0c;当时的测试精度约为 97.8%。虽然这个卷积神经网络很简单…
阅读更多...
【Python爬虫(67)】Python爬虫实战：探秘旅游网站数据宝藏

【Python爬虫(67)】Python爬虫实战：探秘旅游网站数据宝藏

【Python爬虫】专栏简介：本专栏是 Python 爬虫领域的集大成之作，共 100 章节。从 Python 基础语法、爬虫入门知识讲起，深入探讨反爬虫、多线程、分布式等进阶技术。以大量实例为支撑，覆盖网页、图片、音频等各类数据爬取，还涉及数据处理与分析。无论是新手小白还是进阶开发…
阅读更多...
最新文章

Copyright @ 2022~2023