第14届蓝桥杯C++B组省赛

今年比去年难好多= =

Update 2023.4.10 反转了，炼金二分没写错，可以AC了

Update 2023.4.9 rnm退钱，把简单的都放后面是吧。在C语言网测了一下民间数据，地址在这里。果然，二分写错了0分qwq，更新一个正确做法。飞机场不知道为什么也T了（很对的时间复杂度啊）。最后再更新一下J题把，这个题就是一个最简单的树上差分题。

A. 日期统计

直接8个for，然后剪枝一下（只取2023）开头的，跑起来还是很快的，自己电脑100ms，机房1s左右
我算的答案是235,不一定对qwq

#include <bits/stdc++.h>
using namespace std;
map<string, int> f;
int m[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int res;
void check(string s) {if(f.count(s)) return;int mon = (s[0] - '0') * 10 + s[1] - '0';int day = (s[2] - '0') * 10 + s[3] - '0';if(mon < 1 || mon > 12) return ;if (day < 1 || day > m[mon] ) return ;f[s] = 1;res ++;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int a[101];for (int i = 1; i <= 100; i ++) {cin >> a[i];}for (int y1 = 1; y1 <= 100; y1 ++) {for (int y2 = y1 + 1; y2 <= 100; y2 ++) {for (int y3 = y2 + 1; y3 <= 100; y3 ++) {for (int y4 = y3 + 1; y4 <= 100; y4 ++) {string year = "";year += char(a[y1] + '0');year += char(a[y2] + '0');year += char(a[y3] + '0');year += char(a[y4] + '0');if(year != "2023") {continue;}for (int m1 = y4 + 1; m1 <= 100; m1 ++) {for (int m2 = m1 + 1; m2 <= 100; m2 ++) {for (int d1 = m2 + 1; d1 <= 100; d1 ++) {for (int d2 = d1 + 1; d2 <= 100; d2 ++) {string s = "";s += char(a[m1] + '0');s += char(a[m2] + '0');s += char(a[d1] + '0');s += char(a[d2] + '0');check(s);}}}}}}}}cout << res << "\n";// 235return 0;}

B. 01 串的熵

枚举一下1的个数，然后算一下，c++自带log函数的 我算的结果是11027421,不知道对不对qwq

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);double ans = 11625907.5798;int n = 23333333, t = -1;for (int i = 1; i <= n; i ++) {double x1 = 1.0 * i / n;double x2 = 1.0 * (n - i) / n;double res = -1.0 * i * x1 * log2(x1) - 1.0 * (n - i) * x2 * log2(x2);if(fabs(res - ans) < 1e-4) {t = min(i, n - i);break;}}// 11027421cout << t << "\n";}

C. 冶炼金属

瞎几把二分,过样例就没管了。二分没错！
下面是看群友写的，可以过C语言网民间数据

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;int a = 0, b = 1e9;for (int i = 0; i < n; i ++) {int x, y;cin >> x >> y;b = min(b, x / y);a = max(a, x / (y + 1) + 1);}cout << a << " " << b << "\n";return 0;}

二分这样写：

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n), b(n);for (int i = 0; i < n; i ++) {cin >> a[i] >> b[i];}int l = 1, r = 1e9;while (l < r) {int mid = (l + r) >> 1;int t = 0;for (int i = 0; i < n; i ++) {if(a[i] / mid > b[i]) t --;else if(a[i] / mid < b[i]) t ++;}if(t >= 0) r = mid;else l = mid + 1;}cout << l << " ";l = 1, r = 1e9;while (l < r) {int mid = (l + r + 1) >> 1;int t = 0;for (int i = 0; i < n; i ++) {if(a[i] / mid > b[i]) t --;else if(a[i] / mid < b[i]) t ++;}if(t <= 0) l = mid;else r = mid - 1;}cout << l << "\n";return 0;}

D. 飞机降落

看到数据量就只有10,直接就是全排列去判断合不合法了。C语言网TLE了呜呜呜

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct P{int t, d, l;
};
void solve() {int n;cin >> n;vector<P> a(n);for (int i = 0; i < n; i ++) {cin >> a[i].t >> a[i].d >> a[i].l;}vector<int> p(n);iota(p.begin(), p.end(), 0);bool ok = false;do {bool ft = true;int s = a[p[0]].t + a[p[0]].l;for (int i = 1; i < n; i ++) {auto [t, d, l] = a[p[i]];if(t + d < s) ft = false;else {s += l;}}if(ft) ok = true;} while (next_permutation(p.begin(), p.end()));if(ok) {cout << "YES\n";} else {cout << "NO\n";}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t --) {solve();}return 0;
}

E. 接龙数列

和$LIS$类似的DP吧, 可以做到$O(n)$的,但是脑抽了想了个$O(n^2)$又瞎几把优化了一下,样例过了
$f[i][j]$表示选$a_i$以数字$j$结尾的最长接龙数列,然后答案就是$n$减去最长的.
$f[i][j]={\max }_{j\le i}f[j][k]$.然后我这里用树状数组优化成了 $logn$,应该能过.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct BIT {int c[N];int lowbit(int x) {return x & -x;}void add(int x, int v) {while (x < N) {c[x] = max(c[x], v);x += lowbit(x);}}int sum(int x) {int res = 0;while (x) {res = max(res, c[x]);x -= lowbit(x);}return res;}
};
BIT bit[10];
int f[N][10];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;for (int i = 1; i <= n; i ++) {string s;cin >> s;int a = s[0] - '0', b = s.back() - '0';f[i][b] = 1;f[i][b] = max(f[i][b], bit[a].sum(i - 1) + 1);bit[b].add(i, f[i][b]);}int res = 0;for (int i = 1; i <= n; i ++)for (int j = 0; j < 10; j ++) {res = max(res, f[i][j]);}cout << n - res << "\n";return 0;
}

F. 岛屿个数

不会 看了几分钟没思路就看后面去了.
看了一些群佬的思路:大致是,从海开始dfs,遇到了岛就去dfs岛然后标记,这么想确实很对,代码还没写

G. 子串简写

我宣布这是最简单的, 比赛前一天晚上的牛客小白月赛D和这个极其类似
如果一个位置是c2,那么看前面有多少c1就可以了.注意要判断一下距离,用前缀和搞一下就行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int f[N];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int k;cin >> k;string s;char c1, c2;cin >> s >> c1 >> c2;int n = s.size();for (int i = 0; i < n; i ++) {f[i + 1] = f[i] + (s[i] == c1);}ll res = 0;for (int i = k - 1; i < n; i ++) {int l = i - k + 1;if(s[i] == c2) {res += f[l + 1];}}cout << res << "\n";return 0;
}

H. 整数删除

不会, 据说是set+优先队列乱搞)

I. 景区导游

对于树上两个点$(u,v)$之间的最距离就是$dist[u]+dist[v]-2\ast dist[lca(u,v)]$, $dist[u]$是根节点到$u$的距离.
然后就好做了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;vector<vector<pair<int,int>>> adj(n + 1);for (int i = 0; i < n - 1; i ++) {int u, v, w;cin >> u >> v >> w;adj[u].emplace_back(v, w);adj[v].emplace_back(u, w);}vector<int> t(k);for (int i = 0; i < k; i ++) {cin >> t[i];}vector f(n + 1, vector<int>(22));vector<ll> dist(n + 1), dep(n + 1);function<void(int, int)> dfs = [&](int u, int p) {f[u][0] = p;dep[u] = dep[p] + 1;for (int i = 1; i <= 20; i ++) {f[u][i] = f[f[u][i - 1]][i - 1];}for (auto &[v, w] : adj[u]) {if(v == p) continue;dist[v] = dist[u] + w;dfs(v, u);}};function<int(int,int)> lca = [&](int x, int y) -> int{if(dep[x] < dep[y]) swap(x, y);for (int i = 20; i >= 0; i --) {if (dep[f[x][i]] >= dep[y]) {x = f[x][i];}}if(x == y) return x;for (int i = 20; i >= 0; i --) {if(f[x][i] != f[y][i]) {x = f[x][i];y = f[y][i];}}return f[x][0];};dfs(1, 0);auto go = [&](int u, int v) -> ll {return dist[u] + dist[v] - 2 * dist[lca(u, v)];};ll alls = 0;for (int i = 0; i + 1 < k; i ++) {alls += go(t[i], t[i + 1]);}for (int i = 0; i < k;i ++) {if(i == 0) {cout << alls - go(t[0], t[1]) << " ";} else if(i ==  k - 1) {cout << alls - go(t[k - 2], t[k - 1]) << "\n";} else {cout << alls - go(t[i - 1], t[i]) - go(t[i], t[i + 1]) + go(t[i - 1], t[i + 1]) << " ";}}return 0;
}

J. 砍树

这个题其实很简单。它的题意是，给出一棵树，然后$m$对点，让你切断一条边，使得这$m$对点都不连通。
对于一颗树上的两个点$u,v$，他是一定联通的，并且它的路径是$u->lca(u,v)->v$, 那么我们就可以利用差分的思想，让这$m$对点的路径都加上$1$，然后去看哪个边被加了$m$次，那么把这个点切断那就可以满足题意了。具体可以看代码

另外，这个题又是一个lca，难不成今年蓝桥杯要成lca杯了吗雾

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<vector<pair<int,int>>> adj(n + 1);for (int i = 0; i < n - 1; i ++) {int u, v;cin >> u >> v;adj[u].emplace_back(v, i + 1);adj[v].emplace_back(u, i + 1);}vector<vector<int>> f(n + 1, vector<int>(21));vector<int> d(n + 1), dep(n + 1);function<void(int,int)> dfs1 = [&](int u, int p) {dep[u] = dep[p] + 1;f[u][0] = p;for (int i = 1; i <= 20; i ++) {f[u][i] = f[f[u][i - 1]][i - 1];}for (auto &[v, id] : adj[u]) {if(v == p) continue;dfs1(v, u);}};auto lca = [&](int u, int v) -> int {if(dep[u] < dep[v]) swap(u, v);for (int i = 20; i >= 0; i --) {if(dep[f[u][i]] >= dep[v]) {u = f[u][i];}}if(u == v) return u;for (int i = 20; i >= 0; i --) {if(f[u][i] != f[v][i]) {u = f[u][i];v = f[v][i];}}return f[u][0];};int ans = -1;function<int(int,int)> dfs = [&](int u, int p) -> int {int res = d[u];for (auto &[v, id] : adj[u]) {if(v == p) continue;int s = dfs(v, u);if(s == m) {ans = max(ans, id);}res += s;}return res;};dfs1(1, 0);for (int i = 0; i < m; i ++) {int u, v;cin >> u >> v;d[u] ++;d[v] ++;d[lca(u, v)] -= 2; }dfs(1, 0);cout << ans << "\n";return 0;
}