试题 A: 日期统计（dfs+剪枝/暴力枚举）
本题总分：\(5\) 分
【问题描述】
小蓝现在有一个长度为 \(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
现在他想要从这个数组中寻找一些满足以下条件的子序列：
1. 子序列的长度为 \(8\)；
2. 这个子序列可以按照下标顺序组成一个\(yyyymmdd\) 格式的日期，并且要求这个日期是 \(2023\) 年中的某一天的日期，例如 \(20230902\)，\(20231223\)。\(yyyy\) 表示年份，\(mm\) 表示月份，\(dd\) 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同 的 \(2023\) 年的日期。
对于相同的日期你只需要统计一次即可。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false)
#define int long long
using namespace std;
const int N = 110;
int a[N], ans;
bool st[20240000];
bool vis[20240000];
bool check(int date)
{
if(st[date]) return false;
st[date] = true;
int m = date / 100 % 100;
int d = date % 100;
if(m < 1||m > 12) return false;
if(m == 1||m == 3||m == 5||m == 7||m == 8||m == 10||m == 12) {
if(d >= 1&&d <= 31) return true;
} else if(m == 2) {
if(d >= 1&&d <= 28) return true;
} else if(d >= 1&&d <= 30) return true;
return false;
}
void dfs(int x, int pos, int date)
{
if(x == 100) return ;
if(pos == 8)
{
if(check(date)) ans ++;
return ;
}
if((pos == 0&&a[x] == 2)||
(pos == 1&&a[x] == 0)||
(pos == 2&&a[x] == 2)||
(pos == 3&&a[x] == 3)||
(pos == 4&&a[x] >= 0&&a[x] <= 1)||
(pos == 5&&a[x] >= 0&&a[x] <= 9)||
(pos == 6&&a[x] >= 0&&a[x] <= 3)||
(pos == 7&&a[x] >= 0&&a[x] <= 9))
(dfs(x + 1, pos + 1, date * 10 + a[x]));
dfs(x + 1, pos, date);
}
void solve()
{
for(int i = 0; i < 100; i ++)
cin >> a[i];
dfs(0, 0, 0);
cout << ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
/*
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
*/
试题 B: 01 串的熵（循环枚举）
本题总分：\(5\) 分
【问题描述】
对于一个长度为 \(n\) 的 \(01\) 串 \(S = x_1 x_2 x_3...x_n\)，香农信息熵的定义为 \(H(S) =−\sum_{1}^{n}p(x_i)log_2(p(x_i))\)，其中 \(p(0)\), \(p(1)\) 表示在这个 \(01\) 串中 \(0\) 和 \(1\) 出现的占比。
比如，对于 \(S = 100\) 来说，信息熵 \(H(S) = −\frac{1}{3}log_2(\frac{1}{3}) −\frac{2}{3}log_2(\frac{2}{3}) −\frac{2}{3}log_2(\frac{2}{3}) =1.3083\)。对于一个长度为 \(23333333\) 的 \(01\) 串，如果其信息熵为 \(11625907.5798\)，且 \(0\) 出现次数比 \(1\) 少，那么这个 \(01\) 串中 \(0\) 出现了多少次？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
点击查看代码
#include <bits/stdc++.h>
#define ld long double
using namespace std;
const int N = 23333333;
const ld eps = 1e-4, P = 11625907.5798;
int main()
{
int n = N / 2 + 1;
cout << fixed << setprecision(10);
for(int i = 1; i < n; i ++)
{
int j = N - i;
ld t = -1.0 * i * i / N * log2(1.0 * i / N);
ld s = -1.0 * j * j / N * log2(1.0 * j / N);
if(fabs(t + s - P) < eps)
{
cout << i << '\n';
return 0;
}
}
return 0;
}
//11027421
试题 C: 冶炼金属（二分/模拟）
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(10\) 分
【问题描述】
小蓝有一个神奇的炉子用于将普通金属 \(O\) 冶炼成为一种特殊金属 \(X\)。这个炉子有一个称作转换率的属性 \(V\)，\(V\) 是一个正整数，这意味着消耗 \(V\) 个普通金属 \(O\) 恰好可以冶炼出一个特殊金属 \(X\)，当普通金属 \(O\) 的数目不足 \(V\) 时，无法继续冶炼。
现在给出了 \(N\) 条冶炼记录，每条记录中包含两个整数 \(A\) 和 \(B\)，这表示本次
投入了 \(A\) 个普通金属 \(O\)，最终冶炼出了 \(B\) 个特殊金属 \(X\)。每条记录都是独立的，这意味着上一次没消耗完的普通金属 \(O\) 不会累加到下一次的冶炼当中。
根据这 \(N\) 条冶炼记录，请你推测出转换率 \(V\) 的最小值和最大值分别可能是
多少，题目保证评测数据不存在无解的情况。
【输入格式】
第一行一个整数 \(N\)，表示冶炼记录的数目。
接下来输入 \(N\) 行，每行两个整数 \(A、B\)，含义如题目所述。
【输出格式】
输出两个整数，分别表示 \(V\) 可能的最小值和最大值，中间用空格分开。
【样例输入】
3
75 3
53 2
59 2
【样例输出】
20 25
【样例说明】
当 \(V = 20\) 时，有：\(⌊\frac{75}{20} ⌋ = 3，⌊\frac{53}{20} ⌋ = 2，⌊\frac{59}{20} ⌋ = 2\)，可以看到符合所有冶炼记录。
当 \(V = 25\) 时，有：\(⌊\frac{75}{25} ⌋ = 3，⌊\frac{53}{25} ⌋ = 2，⌊\frac{59}{25} ⌋ = 2\)，可以看到符合所有冶炼
记录。
且再也找不到比 \(20\) 更小或者比 \(25\) 更大的符合条件的 \(V\) 值了。
【评测用例与约定】
对于 \(30%\) 的评测用例，\(1 ≤ N ≤ 10^2\)。
对于 \(60%\) 的评测用例，\(1 ≤ N ≤ 10^3\)。
对于 \(100%\) 的评测用例，\(1 ≤ N ≤ 10^4，1 ≤ B ≤ A ≤ 10^9\)。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 1e4 + 10;
int a[N], b[N];
int n, mx, mn;
bool check(int x)
{
for(int i = 1; i <= n; i ++)
if(a[i] / x > b[i])
return false;
return true;
}
bool check2(int x)
{
for(int i = 1; i <= n; i ++)
if(a[i] / x < b[i])
return false;
return true;
}
signed main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i] >> b[i];
int l = 1, r = 1e10, m;
while(l < r)
{
m = l + r >> 1;
if(check(m)) r = m;
else l = m + 1;
}
mn = l;
l = 1, r = 1e10;
while(l < r)
{
m = l + r + 1 >> 1;
if(check2(m)) l = m;
else r = m - 1;
}
mx = l;
cout << mn << ' ' << mx << '\n';
return 0;
}
试题 D: 飞机降落（DFS）
时间限制: \(2.0s\) 内存限制: \(256.0MB\) 本题总分：\(10\) 分
【问题描述】
\(N\) 架飞机准备降落到某个只有一条跑道的机场。其中第 \(i\) 架飞机在 \(T_i\) 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 \(D_i\) 个单位时间，即它最早可以于 \(T_i\) 时刻开始降落，最晚可以于 \(T_i + D_i\) 时刻开始降落。降落过程需要 \(L_i\)个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 \(N\) 架飞机是否可以全部安全降落。
【输入格式】
输入包含多组数据。
第一行包含一个整数 \(T\)，代表测试数据的组数。
对于每组数据，第一行包含一个整数 \(N\)。
以下 \(N\) 行，每行包含三个整数：\(T_i\)，\(D_i\) 和 \(L_i\)。
【输出格式】
对于每组数据，输出 \(YES\) 或者 \(NO\)，代表是否可以全部安全降落。
【样例输入】
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
【样例输出】
YES
NO
【样例说明】
对于第一组数据，可以安排第 \(3\) 架飞机于 \(0\) 时刻开始降落，\(20\) 时刻完成降落。安排第 \(2\) 架飞机于 \(20\) 时刻开始降落，\(30\) 时刻完成降落。安排第 \(1\) 架飞机于 \(30\) 时刻开始降落，\(40\) 时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
【评测用例与约定】
对于 \(30%\) 的数据，\(N ≤ 2\)。
对于 \(100%\) 的数据，\(1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ T_i, D_i
, L_i ≤ 10^5\)。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 20;
int n, t[N], d[N], l[N];
bool f, p[N];
void dfs(int x, int tim)
{
if(f) return ;
if(x == n)
{
f = true;
return ;
}
for(int i = 1; i <= n; i ++)
if(!p[i]&&tim <= t[i] + d[i])
{
p[i] = true;
dfs(x + 1, max(t[i], tim) + l[i]);
if(f) return ;
p[i] = false;
}
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> t[i] >> d[i] >> l[i];
p[i] = false;
}
f = false;
dfs(0, 0);
if(f) cout << "YES\n";
else cout << "NO\n";
}
signed main()
{
IOS;
int _ = 1;
cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 E: 接龙数列（线性dp，最长上升子序列）
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(15\) 分
【问题描述】
对于一个长度为 \(K\) 的整数数列：\(A_1, A_2, . . . , A_K\)，我们称之为接龙数列当且仅当 \(A_i\) 的首位数字恰好等于 \(A_{i−1}\) 的末位数字 \((2 ≤ i ≤ K)\)。
例如 \(12, 23, 35, 56, 61, 11\) 是接龙数列；\(12, 23, 34, 56\) 不是接龙数列，因为 \(56\)
的首位数字不等于 \(34\) 的末位数字。所有长度为 \(1\) 的整数数列都是接龙数列。
现在给定一个长度为 \(N\) 的数列\(A_1, A_2, . . . , A_N\)，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
【输入格式】
第一行包含一个整数 \(N\)。
第二行包含 \(N\) 个整数 \(A_1, A_2, . . . , A_N\)。
【输出格式】
一个整数代表答案。
【样例输入】
5
11 121 22 12 2023
【样例输出】
1
【样例说明】
删除 \(22\)，剩余 \(11, 121, 12, 2023\) 是接龙数列。
【评测用例与约定】
对于 \(20%\) 的数据，\(1 ≤ N ≤ 20\)。
对于 \(50%\) 的数据，\(1 ≤ N ≤ 10000\)。
对于 \(100%\) 的数据，\(1 ≤ N ≤ 10^5，1 ≤ A_i ≤ 10^9\)。所有 \(Ai\) 保证不包含前导 \(0\)。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 20;
string s;
int f[N], n;
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> s;
int a = s[0] - '0';
int b = s[s.size() - 1] - '0';
f[b] = max(f[b], f[a] + 1);
// int x;
// cin >> x;
// vector<int> ve;
// while(x)
// ve.push_back(x % 10), x /= 10;
// int a = *ve.begin(), b = ve.back();
// f[a] = max(f[a], f[b] + 1);
}
int ans = 0;
for(int i = 0; i < 10; i ++)
ans = max(ans, f[i]);
cout << n - ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 F: 岛屿个数（DFS）
时间限制: \(2.0s\) 内存限制: \(256.0MB\) 本题总分：\(15\) 分
【问题描述】
小蓝得到了一副大小为 \(M × N\) 的格子地图，可以将其视作一个只包含字符
\('0'\)（代表海水）和 \('1'\)（代表陆地）的二维数组，地图之外可以视作全部是海水，
每个岛屿由在上/下/左/右四个方向上相邻的 \('1'\) 相连接而形成。
在岛屿 \(A\) 所占据的格子中，如果可以从中选出 \(k\) 个不同的格子，使得
他们的坐标能够组成一个这样的排列：\((x_0, y_0),(x_1, y_1), . . . ,(x_{k−1}, y_{k−1)}\)，其中\((x_{(i+1)\%k}, y_{i+1\%k})\) 是由 \((x_i, y_i)\) 通过上/下/左/右移动一次得来的 \((0 ≤ i ≤ k − 1)\)，此时这 \(k\) 个格子就构成了一个 “环”。如果另一个岛屿 \(B\) 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 \(B\) 视作是岛屿 \(A\) 的子岛屿。若 \(B\) 是 A 的子岛屿，\(C\) 又是 \(B\) 的子岛屿，那 \(C\) 也是 \(A\) 的子岛屿。
请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。
【输入格式】
第一行一个整数 \(T\)，表示有 \(T\) 组测试数据。
接下来输入 \(T\) 组数据。对于每组数据，第一行包含两个用空格分隔的整数\(M、N\) 表示地图大小；接下来输入 \(M\) 行，每行包含 \(N\) 个字符，字符只可能是 \('0'\) 或 \('1'\)。
【输出格式】
对于每组数据，输出一行，包含一个整数表示答案。
【样例输入】
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
【样例输出】
1
3
【样例说明】
对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：
01111
11001
10201
10001
11111
岛屿 \(2\) 在岛屿 \(1\) 的 “环” 内部，所以岛屿 \(2\) 是岛屿 \(1\) 的子岛屿，答案为 \(1\)。
对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：
111111
100001
020301
100001
111111
注意岛屿 \(3\) 并不是岛屿 \(1\) 或者岛屿 \(2\) 的子岛屿，因为岛屿 \(1\) 和岛屿 \(2\) 中均没有
“环”。
【评测用例与约定】
对于 \(30%\) 的评测用例，\(1 ≤ M, N ≤ 10\)。
对于 \(100%\) 的评测用例，\(1 ≤ T ≤ 10，1 ≤ M, N ≤ 50\)。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
// #define int long long
using namespace std;
const int N = 60;
int n, m;
string mp[N];
bool st[N][N], used[N][N];
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
void bfs_col(int x, int y)
{
queue<int> qx, qy;
qx.push(x), qy.push(y), st[x][y] = 1;
while(!qx.empty())
{
x = qx.front(), qx.pop();
y = qy.front(), qy.pop();
for(int i = 0; i < 4; i ++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0||nx >= n||ny < 0|ny >= m||st[nx][ny]||mp[nx][ny] == '0') continue;
qx.push(nx), qy.push(ny), st[nx][ny] = 1;
}
}
}
bool bfs_out(int x, int y)
{
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
used[i][j] = 0;
queue<int> qx, qy;
qx.push(x), qy.push(y), used[x][y] = 1;
while(!qx.empty())
{
x = qx.front(), qx.pop();
y = qy.front(), qy.pop();
if(x == 0||x == n - 1||y == 0||y == m - 1) return true;
for(int i = 0; i < 8; i ++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0||nx >= n||ny < 0|ny >= m||used[nx][ny]||mp[nx][ny] == '1') continue;
qx.push(nx), qy.push(ny), used[nx][ny] = 1;
}
}
return false;
}
void solve()
{
cin >> n >> m;
for(int i = 0; i < n; i ++)
{
cin >> mp[i];
for(int j = 0; j < m; j ++)
st[i][j] = 0;
}
int ans = 0;
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
if(!st[i][j]&&mp[i][j] == '1')
{
bfs_col(i, j);
if(bfs_out(i, j)) ans ++;
}
cout << ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
cin >> _;
while(_ --)
solve();
return _ ^ _;
}
/*
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
*/
试题 G: 子串简写（线性dp/模拟）
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(20\) 分
【问题描述】
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 \(internationalization\) 简写成 \(i18n\)，\(Kubernetes\) （注意连字符不是字符串的一部分）简写成 \(K8s\), \(Lanqiao\) 简写成 \(L5o\) 等。
在本题中，我们规定长度大于等于 \(K\) 的字符串都可以采用这种简写方法（长度小于 \(K\) 的字符串不配使用这种简写）。
给定一个字符串 \(S\) 和两个字符 \(c_1\) 和 \(c_2\)，请你计算 \(S\) 有多少个以 \(c_1\) 开头\(c_2\) 结尾的子串可以采用这种简写？
【输入格式】
第一行包含一个整数 \(K\)。
第二行包含一个字符串 \(S\) 和两个字符 \(c_1\) 和 \(c_2\)。
【输出格式】
第二行包含一个字符串 S 和两个字符 c1 和 c2。
【样例输入】
4
abababdb a b
【样例输出】
6
【样例说明】
符合条件的子串如下所示，中括号内是该子串：
\([abab]abdb\)
\([ababab]db\)
\([abababdb]\)
\(ab[abab]db\)
\(ab[ababdb]\)
\(abab[abdb]\)
【评测用例与约定】
对于 \(20%\) 的数据，\(2 ≤ K ≤ |S | ≤ 10000\)。
对于 \(100%\) 的数据，\(2 ≤ K ≤ |S | ≤ 5 × 10^5\)。\(S\) 只包含小写字母。\(c_1\) 和 \(c_2\) 都
是小写字母。
\(| S |\) 代表字符串 \(S\) 的长度。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
string s;
char c1, c2;
int n, ans, k, t;
void solve()
{
cin >> k >> s >> c1 >> c2;
n = s.size();
for(int i = k - 1, j = 0; i < n; i ++, j ++)
{
if(s[j] == c1) t ++;
if(s[i] == c2) ans += t;
}
cout << ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 H: 整数删除（链表+优先队列）
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(20\) 分
【问题描述】
给定一个长度为 \(N\) 的整数数列：\(A_1, A_2, . . . , A_N\)。你要重复以下操作 \(K\) 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出 \(K\) 次操作后的序列。
【输入格式】
第一行包含两个整数 \(N\) 和 \(K\)。
第二行包含 \(N\) 个整数，\(A_1, A_2, A_3, . . . , A_N\)。
【输出格式】
输出 \(N − K\) 个整数，中间用一个空格隔开，代表 \(K\) 次操作后的序列。
【样例输入】
5 3
1 4 2 8 7
【样例输出】
17 7
【样例说明】
数列变化如下，中括号里的数是当次操作中被选择的数：
\([1]\ 4\ 2\ 8\ 7\)
\(5\ [2]\ 8\ 7\)
\([7]\ 10\ 7\)
\(17\ 7\)
【评测用例与约定】
对于 \(20%\) 的数据，\(1 ≤ K < N ≤ 10000\)。
对于 \(100%\) 的数据，\(1 ≤ K < N ≤ 5 × 10^5，0 ≤ Ai ≤ 10^8\)。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 10;
typedef pair<int, int> pii;
int n, k, pre[N], ne[N], a[N];
priority_queue<pii> q;
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
pre[i] = i - 1;
ne[i] = i + 1;
q.push({-a[i], -i});
}
pre[1] = -1;
ne[n] = -1;
while(k --)
{
pii now;
do {
now = q.top(), q.pop();
now.fi = - now.fi, now.se = -now.se;
}while(a[now.se] != now.fi);
int PRE = pre[now.se];
int NE = ne[now.se];
if(PRE != -1) {
a[PRE] += now.fi;
q.push({-a[PRE], -PRE});
ne[PRE] = NE;
}
if(NE != -1) {
a[NE] += now.fi;
q.push({-a[NE], -NE});
pre[NE] = PRE;
}
a[now.se] = -1;
}
for(int i = 1; i <= n; i ++)
if(a[i] != -1)
cout << a[i] << ' ';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 I: 景区导游（LCA）
时间限制: \(5.0s\) 内存限制: \(256.0MB\) 本题总分：\(25\) 分
【问题描述】
某景区一共有 \(N\) 个景点，编号 \(1\) 到 \(N\)。景点之间共有 \(N − 1\) 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 \(K\) 个景点：\(A_1, A_2, . . . , A_K\)。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 \(K − 1\) 个景点。具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 \(A_1, A_2, . . . , A_{i−1}, A_{i+1}, . . . , A_K, (1 ≤ i ≤ K)\)。
请你对任意一个 \(A_i\)，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？
【输入格式】
第一行包含 \(2\) 个整数 \(N\) 和 \(K\)。
以下 \(N − 1\) 行，每行包含 \(3\) 个整数 \(u, v\) 和 \(t\)，代表景点 \(u\) 和 \(v\) 之间有摆渡车线路，花费 \(t\) 个单位时间。
最后一行包含 \(K\) 个整数 \(A_1, A_2, . . . , A_K\) 代表原定游览线路。
【输出格式】
输出 \(K\) 个整数，其中第 \(i\) 个代表跳过 \(A_i\) 之后，花费在摆渡车上的时间。
【样例输入】
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1
【样例输出】
10 7 13 14
【样例说明】
原路线是 \(2 → 6 → 5 → 1\)。
当跳过 \(2\) 时，路线是 \(6 → 5 → 1\)，其中 \(6 → 5\) 花费时间 \(3 + 2 + 2 = 7\)，\(5 → 1\) 花费时间 \(2 + 1 = 3\)，总时间花费 \(10\)。
当跳过 \(6\) 时，路线是 \(2 → 5 → 1\)，其中 \(2 → 5\) 花费时间 \(1 + 1 + 2 = 4\)，\(5 → 1\) 花费时间 \(2 + 1 = 3\)，总时间花费 \(7\)。
当跳过 \(5\) 时，路线是 \(2 → 6 → 1\)，其中 \(2 → 6\) 花费时间 \(1 + 1 + 2 + 3 = 7\)，\(6 → 1\) 花费时间 \(3 + 2 + 1 = 6\)，总时间花费 \(13\)。
当跳过 1 时，路线时 \(2 → 6 → 5\)，其中 \(2 → 6\) 花费时间 \(1 + 1 + 2 + 3 = 7\)，\(6 → 5\) 花费时间 \(3 + 2 + 2 = 7\)，总时间花费 \(14\)。
【评测用例与约定】
对于 \(20%\) 的数据，\(2 ≤ K ≤ N ≤ 10^2\)。
对于 \(40%\) 的数据，\(2 ≤ K ≤ N ≤ 10^4\)。
对于 \(100%\) 的数据，\(2 ≤ K ≤ N ≤ 10^5\)，\(1 ≤ u, v, A_i ≤ N，1 ≤ t ≤ 10^5\)。保证\(A_i\) 两两不同。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N], w[N];
int fa[N][21], dep[N], dis[N];
int a[N], b[N];
int n, k;
void dfs(int u, int Fa)
{
dep[u] = dep[Fa] + 1;
fa[u][0] = Fa;
for(int i = 1; i <= 20; i ++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = 0; i < e[u].size(); i ++)
{
int v = e[u][i], ww = w[u][i];
if(v == Fa) continue;
dis[v] = dis[u] + ww;
dfs(v, u);
}
}
int LCA(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
for(int i = 20; i >= 0; i --)
if(dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if(u == v) return u;
for(int i = 20; i >= 0; i --)
if(fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
return fa[u][0];
}
int path_dis(int u, int v)
{
if(!u||!v) return 0;
return dis[u] + dis[v] - 2 * dis[LCA(u, v)];
}
void solve()
{
cin >> n >> k;
for(int i = 1; i < n; i ++)
{
int u, v, t;
cin >> u >> v >> t;
e[u].push_back(v);
w[u].push_back(t);
e[v].push_back(u);
w[v].push_back(t);
}
dfs(1, 0);
int ans = 0;
for(int i = 1; i <= k; i ++)
{
cin >> a[i];
ans += path_dis(a[i], a[i - 1]);
}
for(int i = 1; i <= k; i ++)
cout << ans - path_dis(a[i - 1], a[i]) - path_dis(a[i], a[i + 1]) + path_dis(a[i - 1], a[i + 1]) << ' ';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 J: 砍树（LCA）
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(25\) 分
【问题描述】
给定一棵由 \(n\) 个结点组成的树以及 \(m\) 个不重复的无序数对 \((a_1, b_1), (a_2, b_2),. . . , (a_m, b_m)\)，其中 \(a_i\) 互不相同，\(b_i\) 互不相同，\(a_i , b_j(1 ≤ i, j ≤ m)\)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 \((a_i, b_i)\) 满足 \(a_i\)和 \(b_i\) 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 \(1\) 开始），否则输出 \(-1\)。
【输入格式】
输入共 \(n + m\) 行，第一行为两个正整数 \(n，m\)。
后面 \(n − 1\) 行，每行两个正整数 \(x_i，y_i\) 表示第 \(i\) 条边的两个端点。
后面 \(m\) 行，每行两个正整数 \(a_i，b_i\)。
【输出格式】
一行一个整数，表示答案，如有多个答案，输出编号最大的一个。
【样例输入】
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
【样例输出】
4
【样例说明】
断开第 \(2\) 条边后形成两个连通块：\({3, 4}，{1, 2, 5, 6}\)，满足 \(3\) 和 \(6\) 不连通，\(4\) 和 \(5\) 不连通。
断开第 \(4\) 条边后形成两个连通块：\({1, 2, 3, 4}，{5, 6}\)，同样满足 \(3\) 和 \(6\) 不连通，\(4\) 和 \(5\) 不连通。
\(4\) 编号更大，因此答案为 \(4\)。
【评测用例与约定】
对于 \(30%\) 的数据，保证 \(1 < n ≤ 1000\)。
对于 \(100%\) 的数据，保证 \(1 < n ≤ 10^5，1 ≤ m ≤\frac n2\)。
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N], num[N];
int fa[N][21], dep[N], s[N];
int n, m, ans;
void dfs(int u, int Fa)
{
dep[u] = dep[Fa] + 1;
fa[u][0] = Fa;
for(int i = 1; i <= 20; i ++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(auto &v : e[u])
{
if(v == Fa) continue;
dfs(v, u);
}
}
int LCA(int u, int v)
{
if(dep[u] < dep[v]) swap(v, u);
for(int i = 20; i >= 0; i --)
if(dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if(u == v) return u;
for(int i = 20; i >= 0; i --)
if(fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
return fa[u][0];
}
void dfs2(int u, int Fa)
{
for(int i = 0; i < e[u].size(); i ++)
{
int v = e[u][i], p = num[u][i];
if(v == Fa) continue;
dfs2(v, u);
s[u] += s[v];
if(s[v] == m) ans = max(ans, p);
}
}
void solve()
{
cin >> n >> m;
ans = -1;
for(int i = 1; i < n; i ++)
{
int x, y;
cin >> x >> y;
e[x].push_back(y);
num[x].push_back(i);
e[y].push_back(x);
num[y].push_back(i);
}
dfs(1, 0);
for(int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
s[a] ++, s[b] ++, s[LCA(a, b)] -= 2;
}
dfs2(1, 0);
cout << ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}