目录
- 试题 A. 日期统计
-
- 1.题目描述
- 2.解题思路
- 3.模板代码
- 试题 B.01 串的熵
-
- 1.题目描述
- 2.解题思路
- 3.模板代码
- 试题 C. 冶炼金属
-
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 D. 飞机降落
-
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 E. 接龙数列
-
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 F. 岛屿个数
-
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 G. 子串简写
-
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 H.整数删除
-
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 I. 景区旅游
-
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 J. 砍树
-
- 1.题目描述
- 2. 解题思路
- 3. 模板代码
目前除 B、F题未补，其余题均已更完，经非官方数据测试均可AC。欢迎交流
试题 A. 日期统计
1.题目描述
小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的
范围之内。数组中的元素从左至右如下所示：
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
现在他想要从这个数组中寻找一些满足以下条件的子序列：
-
- 子序列的长度为
；
- 子序列的长度为
-
- . 这个子序列可以按照下标顺序组成一个
格式的日期，并且
要求这个日期是年中的某一天的日期，例如
。
表示年份，
表示月份，
表示天数，当月份或者天数的长度只
有一位时需要一个前导零补充。
- . 这个子序列可以按照下标顺序组成一个
请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。
对于相同的日期你只需要统计一次即可。
2.解题思路
考虑八层循环枚举一下，中间需要进行减枝加快搜索步骤，不建议写 dfs，不然就像我一样在考场写烂，注意答案需要去重，答案为235。
3.模板代码
暂更
试题 B.01 串的熵
1.题目描述
没学过数学，暂更
2.解题思路
3.模板代码
试题 C. 冶炼金属
1.题目描述
小蓝有一个神奇的炉子用于将普通金属 冶炼成为一种特殊金属
。这个
炉子有一个称作转换率的属性 ，
是一个正整数，这意味着消耗
个普通金
属 恰好可以冶炼出一个特殊金属
，当普通金属
的数目不足
时，无法
继续冶炼。
现在给出了 条冶炼记录，每条记录中包含两个整数
和
，这表示本次投入了
个普通金属
，最终冶炼出了
个特殊金属
。每条记录都是独立
的，这意味着上一次没消耗完的普通金属 不会累加到下一次的冶炼当中。
根据这 条冶炼记录，请你推测出转换率
的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
2. 解题思路
如果看过样例的话，显然答案两个上下界都是可以直接二分出来的。因为式子的结构都是 。
是不变的，我们先考虑二分求最小的
，因为需要保证所有式子的
都不变，如果
太小，显然会有某一组的
增大，所以需要保证每一组都符合
a[i]/x <= b[i]。反过来考虑求最大的 , 如果
太大，显然会有某一组的
变小，需要保证每一组都符合
a[i]/x >= B。
3.模板代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
int n;
int a[N], b[N];
bool check(LL x) {
for (int i = 1; i <= n; ++i) {
if (a[i] / x > b[i]) return false;
}
return true;
}
bool check2(LL x) {
for (int i = 1; i <= n; ++i) {
if (a[i] / x < b[i]) return false;
}
return true;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
LL l = 1, r = 1e9;
while (l < r) {
LL mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
int s = r;
l = 1, r = 1e9;
while (l < r) {
LL mid = l + r + 1 >> 1;
if (check2(mid)) l = mid;
else r = mid - 1;
}
cout << s << " " << r << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
试题 D. 飞机降落
1.题目描述
架飞机准备降落到某个只有一条跑道的机场。其中第
架飞机在
时刻到达机场上空，到达时它的剩余油料还可以继续盘旋
个单位时间，即它最早
可以于 时刻开始降落，最晚可以于
时刻开始降落。降落过程需要
个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不
能在前一架飞机完成降落前开始降落。
请你判断 架飞机是否可以全部安全降落。
2. 解题思路
看 最大为
10，T最大也为10，考虑全排列枚举所有的降落情况，只要有一种符合的情况即可，大概计算一下复杂度为 等于
3e8，理论可过 。
3.模板代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
int n;
int a[N], b[N], c[N];
void solve()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i];
std::vector<int> d(n);
auto check = [&]() {
int v = 0;
for (int i = 0; i < n; ++i) {
int x = d[i];
if (i == 0) {
v = a[x] + c[x];
} else {
if (a[x] + b[x] < v) return false;
v = max(v, a[x]) + c[x];
}
}
return true;
};
iota(all(d), 0);
bool f = false;
do {
if (check()) {
f = true;
break;
}
} while (next_permutation(all(d)));
if (f) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
试题 E. 接龙数列
1.题目描述
对于一个长度为 的整数数列：
，我们称之为接龙数列当且仅当
的首位数字恰好等于
的末位数字
。
例如 是接龙数列；
不是接龙数列，因为
的首位数字不等于
的末位数字。所有长度为
的整数数列都是接龙数列。
现在给定一个长度为 的数列
，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
2. 解题思路
考场读完题的时候感觉有点奇怪，发现思路还是比较简单的。首先一个数我们只需要关注其首位数字和末位数字，定以 为以数字
结尾的最长接龙序列的长度，
的范围是
。对于每个数字设其首位数字为
，末尾数字为
，则有转移方程：
最后在 取一个最大值
，答案则为
。
3.模板代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
int n;
int a[N], b[N];
int f[10];
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
b[i] = x % 10;
string s = to_string(x);
a[i] = s[0] - '0';
}
for (int i = 1; i <= n; ++i) {
f[b[i]] = max(f[b[i]], f[a[i]] + 1);
}
int ans = 0;
for (int i = 0; i <= 9; ++i) ans = max(ans, f[i]);
cout << n - ans << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
试题 F. 岛屿个数
1.题目描述
暂更，感觉不好写
2. 解题思路
3.模板代码
试题 G. 子串简写
1.题目描述
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 简写成
，
（注意连字符不是字符串的一部分）简写成
简写成
等。
在本题中，我们规定长度大于等于 的字符串都可以采用这种简写方法（长度小于
的字符串不配使用这种简写）。
给定一个字符串 和两个字符
和
，请你计算
有多少个以
开头
结尾的子串可以采用这种简写？
2. 解题思路
这道题放在 G 题感觉更奇怪了，一道前缀和模板题。假设下标为 的字符为
，那我们只需要统计在区间
有多少个
即可，前缀和预处理一下
字符，直接累加答案即可，注意答案会爆
int，复杂度
3.模板代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 500010;
int k;
string s;
char c1, c2;
int a[N];
void solve()
{
cin >> k >> s >> c1 >> c2;
int n = s.size();
s = '?' + s;
for (int i = 1; i <= n; ++i) {
a[i] = (s[i] == c2);
a[i] += a[i - 1];
}
LL ans = 0;
for (int i = 1; i + k - 2 < n; ++i) {
if (s[i] == c1) ans += a[n] - a[i + k - 2];
}
cout << ans << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
试题 H.整数删除
1.题目描述
给定一个长度为 的整数数列：
。你要重复以下操作
次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出 次操作后的序列。
2. 解题思路
感觉是比较典的题目，用优先队列维护，存入值和下标，再用一个数组cnt累计每个下标增加的和，当弹出最小的值下标为 i 时，如果此时cnt[i]不等于0，说明它实际的值需要加上cnt[i]，我们将其增加后再放回优先对列，注意需要清空cnt[i]。如果此时cnt[i]等于0，那我们就成功弹出当前最小元素，这时需要将其前一个元素和后一个元素值增加，我们需要模拟链表去记录每个元素的前后元素是谁，pre[i]表示下标为i的上一个元素是谁，ne[i]表示下标为 i 的下一个元素是谁，直到堆的元素个数只剩n-k时结束循环。不难想象，堆元素的出入次数是线性的。
3.模板代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 500010;
int n, k;
int pre[N], ne[N];
LL cnt[N];
void solve()
{
cin >> n >> k;
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>> >q;
for (int i = 1; i <= n; ++i) {
LL v;
cin >> v;
q.push({v, i});
pre[i] = i - 1;
ne[i] = i + 1;
}
int g = n - k;
while (q.size() > g) {
auto p = q.top(); q.pop();
LL v = p.first, ix = p.second;
if (cnt[ix]) {
q.push({v + cnt[ix], ix});
cnt[ix] = 0;
} else {
int l = pre[ix], r = ne[ix];
cnt[l] += v;
cnt[r] += v;
ne[l] = r;
pre[r] = l;
}
}
std::vector<LL> a(n + 1);
for (int i = 0; i < g; ++i) {
auto p = q.top(); q.pop();
a[p.second] = p.first + cnt[p.second];
}
for (int i = 1; i <= n; ++i) {
if (a[i]) cout << a[i] << " ";
}
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
试题 I. 景区旅游
1.题目描述
某景区一共有 个景点，编号
到
。景点之间共有
条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 个景点：
。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中
个景点。具体来说，如果小明选择跳过
，那么他会按顺序带游客游览
。
请你对任意一个 ，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？
2. 解题思路
模板题（问题是比赛写不出板子呢），首先肯定需要考虑求树上任意两点的距离。设点
的最近公共祖先为
，定义
为点
到根节点的距离，那么则有公式:
先求出不跳过任何的点时需要走的距离为ans以及任意相邻两个跳点的距离。假设我们跳过四个点分别为 。当跳过的点为
时，我们只需要用
ans减去到
的距离，当跳过的点为
时，我们只需要用
ans减去 到
的距离，这是首尾两个点的情况。
那么当跳过的点为中间点呢？比如我们跳过的是 ，那么则需要用
ans减去到
以及
到
的距离，并且还需要加上
到
的距离，其余的中间点处理同理。
3.模板代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s)
#define SZ(s) ((int)s.size())
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
int n, m;
std::vector<pair<int, LL>> e[N];
int depth[N], fa[N][32];
LL f[N];
int root;
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;
queue<int> q;
q.push(root);
while (!q.empty()) {
auto t = q.front();
q.pop();
for (auto [j, c] : e[t]) {
if (depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for (int k = 1; k <= 20; k++) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
void dfs(int u, int fa) {
for (auto [v, c] : e[u]) {
if (v == fa) continue;
f[v] = f[u] + c;
dfs(v, u);
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 20; k >= 0; k--) {
if (depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if (a == b) return a;
for (int k = 20; k >= 0; --k) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
LL calc(int u, int v) {
int z = lca(u, v);
return f[u] + f[v] - 2 * f[z];
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < n - 1; ++i) {
int u, v , c;
cin >> u >> v >> c;
e[u].push_back({v, c});
e[v].push_back({u, c});
}
bfs(1);
dfs(1, -1);
std::vector<LL> g(m + 1);
for (int i = 1; i <= m; ++i) cin >> g[i];
LL ans = 0;
for (int i = 1; i < m; ++i) {
ans += calc(g[i], g[i + 1]);
}
for (int i = 1; i <= m; ++i) {
if (i == 1) cout << ans - calc(g[i], g[i + 1]) << " ";
else if (i == m) cout << ans - calc(g[i - 1], g[i]) << " ";
else {
LL res = ans - calc(g[i], g[i + 1]) - calc(g[i - 1], g[i]) + calc(g[i - 1], g[i + 1]);
cout << res << " ";
}
}
}
signed main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
试题 J. 砍树
1.题目描述
给定一棵由 个结点组成的树以及
个不重复的无序数对
，其中
互不相同，
互不相同，
。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 满足
和
不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从
开始），否则输出
。
2. 解题思路
又是 模板题啊，但我之前没做过（反正也写不出
）。考虑一对无序数对的点
和
，如果我们砍掉某条边可以让这两个点不连通，那么这条边一定是从
到
路径上的一点，我们可以让从
到
路径的边权值都加
1。这个操作我们可以使用树上差分。 对于 个无序数对我们都如此操作，最后如果某条边的权值为
则说明它符合条件，我们选出符合条件编号最大的那条边就是答案，如果没有权值为
的边则说明无解。
3. 模板代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
int n, m;
std::vector<int> e[N];
int depth[N], fa[N][32];
int f[N];
int root;
int ans;
map<PII, int> mp;
void bfs(int root)
{
ms(depth, 0x3f);
depth[0] = 0, depth[root] = 1;
queue<int> q;
q.push(root);
while (!q.empty()) {
auto t = q.front();
q.pop();
for (int j : e[t]) {
if (depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for (int k = 1; k <= 15; k++) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k--) {
if (depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if (a == b) return a;
for (int k = 15; k >= 0; --k) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
int dfs(int u, int fa) {
int res = f[u];
for (auto v : e[u]) {
if (v == fa) continue;
int g = dfs(v, u);
if (g == m) {
ans = max(ans, mp[ {v, u}]);
}
res += g;
}
return res;
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
mp[ {u, v}] = mp[ {v, u}] = i + 1;
e[u].push_back(v);
e[v].push_back(u);
}
bfs(1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
int z = lca(u, v);
f[u]++;
f[v]++;
f[z] -= 2;
}
dfs(1, -1);
cout << (ans == 0 ? -1 : ans) << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
版权声明：本文为博主作者：执 梗原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/m0_57487901/article/details/130036113
