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();
}
![OmniParser:下一代纯视觉UI自动化测试先驱[特殊字符]](http://pic.xiahunao.cn/nshx/OmniParser:下一代纯视觉UI自动化测试先驱[特殊字符])
