今年比去年难好多= =
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. 接龙数列
和
L
I
S
LIS
LIS类似的DP吧, 可以做到
O
(
n
)
O(n)
O(n)的,但是脑抽了想了个
O
(
n
2
)
O(n^2)
O(n2)又瞎几把优化了一下,样例过了
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示选
a
i
a_i
ai以数字
j
j
j结尾的最长接龙数列,然后答案就是
n
n
n减去最长的.
f
[
i
]
[
j
]
=
max
j
≤
i
f
[
j
]
[
k
]
f[i][j] = \max_{j \le i} f[j][k]
f[i][j]=maxj≤if[j][k].然后我这里用树状数组优化成了
l
o
g
n
logn
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
)
(u,v)
(u,v)之间的最距离就是
d
i
s
t
[
u
]
+
d
i
s
t
[
v
]
−
2
∗
d
i
s
t
[
l
c
a
(
u
,
v
)
]
dist[u] + dist[v] - 2 * dist[lca(u,v)]
dist[u]+dist[v]−2∗dist[lca(u,v)],
d
i
s
t
[
u
]
dist[u]
dist[u]是根节点到
u
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
m对点，让你切断一条边，使得这
m
m
m对点都不连通。
对于一颗树上的两个点
u
,
v
u, v
u,v，他是一定联通的，并且它的路径是
u
−
>
l
c
a
(
u
,
v
)
−
>
v
u -> lca(u,v) -> v
u−>lca(u,v)−>v, 那么我们就可以利用差分的思想，让这
m
m
m对点的路径都加上
1
1
1，然后去看哪个边被加了
m
m
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;
}
