文章目录

• • • A. 日期统计
    • B. 01 串的熵
    • C. 冶炼金属
    • D. 飞机降落
    • E. 接龙数列
    • F. 岛屿个数
    • G. 子串简写
    • H. 整数删除
    • I. 景区导游
    • J. 砍树

今年比去年难好多= =

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";

	// 235

	return 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;
		}
	}
	// 11027421
	cout << 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;
}