蓝桥杯训练 补题

devtools/2025/2/26 22:05:32/

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/devtools/162897.html

相关文章

如何禁用uniapp,vue页面下拉刷新功能

如何禁用uniapp,vue页面下拉刷新功能

在小程序开发中&#xff0c;enablePullDownRefresh 是一个常用的配置项&#xff0c;用来控制页面是否允许下拉刷新。但是&#xff0c;有时即使在 pages.json 中将其设置为 false&#xff0c;下拉刷新依然可能未被完全禁用。 1. enablePullDownRefresh: false 配置无效 enable…
阅读更多...
Postman学习总结

Postman学习总结

1、基本操作&#xff1a; 【2023全网最牛教程】10分钟快速上手Postman&#xff08;建议收藏&#xff09;_macbook postman打开慢-CSDN博客 接口测试—Postman详解-CSDN博客 新手如何使用postman&#xff08;新手使用&#xff0c;简单明了&#xff09;_postman教程-CSDN博客 …
阅读更多...
【无标题】网络安全公钥密码体制

【无标题】网络安全公钥密码体制

第一节 网络安全 概述 一、基本概念 网络安全通信所需要的基本属性“ 机密性&#xff1b;消息完整性&#xff1b;可访问性与可用性&#xff1b;身份认证。 二、网络安全威胁 窃听&#xff1b;插入&#xff1b;假冒&#xff1b;劫持&#xff1b;拒绝服务Dos和分布式拒绝服务…
阅读更多...
上证50股指期货一手多少钱？

上证50股指期货一手多少钱？

先说结论&#xff0c;一手上证50股指期货的钱数&#xff0c;主要看两个东西&#xff1a;指数点位 和 保证金比例。 &#xff08;一&#xff09;合约金额怎么算&#xff1f; 上证50股指期货的规则是&#xff1a;每一点指数值300块钱。比如&#xff0c;现在上证50指数是2700点&…
阅读更多...
804 唯一摩斯密码词

804 唯一摩斯密码词

国际摩尔斯密码定义一种标准编码方式&#xff0c;将每个字母对应于一个由一系列点和短线组成的字符串&#xff0c; 比如: a 对应 ".-" &#xff0c;b 对应 "-..." &#xff0c;c 对应 "-.-." &#xff0c;以此类推。 为了方便&#xff0c;所有…
阅读更多...
JavaWeb基础专项复习6——AJAX

JavaWeb基础专项复习6——AJAX

系列文章目录 1、JavaWeb基础专项复习1——XML文件-CSDN博客 2、JavaWeb基础专项复习2——JSP文件-CSDN博客 3、JavaWeb基础专项复习2——Servlet相关知识-CSDN博客 4、JavaWeb基础专项复习4——会话对象Session and Cookie-CSDN博客 5、JavaWeb基础专项复习5——请求对象…
阅读更多...
栈和STL —— stack 【复习笔记】

栈和STL —— stack 【复习笔记】

1. 栈 1.1 栈的概念和相关术语 栈是一种特殊的线性表&#xff0c;它只允许在表的一端进行插入和删除操作。这使栈具有 “后进先出”&#xff08;Last In First Out&#xff0c;LIFO&#xff09;的特性 栈顶&#xff1a;栈中允许进行插入和删除操作的一端 栈底&#xff1a;栈…
阅读更多...
【多模态处理篇三】【DeepSeek语音合成：TTS音色克隆技术揭秘】

【多模态处理篇三】【DeepSeek语音合成：TTS音色克隆技术揭秘】

最近帮某明星工作室做AI语音助手时遇到魔幻需求——要求用5秒的咳嗽声克隆出完整音色！传统TTS系统直接翻车，生成的语音像得了重感冒的电音怪物。直到祭出DeepSeek的TTS音色克隆黑科技，才让AI语音从"机器朗读"进化到"声临其境"。今天我们就来扒开这个声音…
阅读更多...
最新文章

Copyright @ 2022~2023