4 月 21 日测试题解
T1 \({\color{green}{\text{100pts}}}\text{/100pts}\)
题意
给出平面上的两条线段，求线段之间的距离。
\(\text{|线段端点坐标|} \le 10^4\)。
思路
一开始想的是分讨，但是又怕自己写挂了，所以就写了三分套三分。至少这个不怕少讨论一个情况。
既然是三分套三分，那就没什么可说的了，其实就是三分的板子。
大致思路就是先在一条线段上三分出一个点，然后再在另外一条线段上三分出与它距离最小的点。
代码
#include <bits/stdc++.h>
using i64 = long long;
using f80 = long double;
namespace myFile {
void useFileIO() {
freopen("segment.in", "r", stdin);
freopen("segment.out", "w", stdout);
return;
}
}
struct Point {
f80 x, y;
Point() {}
Point(f80 x, f80 y) : x(x), y(y) {}
Point operator= (const Point &rhs) {
x = rhs.x, y = rhs.y;
return *this;
}
};
bool operator< (const Point &lhs, const Point &rhs) {
if (lhs.x == rhs.x) {
return lhs.y < rhs.y;
} else {
return lhs.x < rhs.x;
}
}
int main() {
myFile::useFileIO();
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout << std::fixed << std::setprecision(4);
static const f80 EPS = 1e-8;
std::vector<Point> points(4);
for (int i = 0; i < 4; i++) {
std::cin >> points[i].x >> points[i].y;
}
std::sort(points.begin(), points.begin() + 2);
std::sort(points.begin() + 2, points.end());
auto getMinDis = [&](const Point &u) -> f80 {
Point l(points[2].x, points[2].y), r(points[3].x, points[3].y);
if (l.x == r.x && l.y == r.y) {
return std::hypot(l.x - u.x, l.y - u.y);
}
f80 res = LONG_LONG_MAX;
int d;
if (l.y <= r.y) {
d = 1;
} else {
d = -1;
}
while (std::hypot(l.x - r.x, l.y - r.y) > EPS) {
Point lmid(l.x + std::fabs(r.x - l.x) / 3, l.y + d * std::fabs(r.y - l.y) / 3);
Point rmid(r.x - std::fabs(r.x - l.x) / 3, r.y - d * std::fabs(r.y - l.y) / 3);
f80 d1 = std::hypot(lmid.x - u.x, lmid.y - u.y);
f80 d2 = std::hypot(rmid.x - u.x, rmid.y - u.y);
if (d1 > d2 + EPS) {
l = lmid;
res = std::min(res, d2);
} else {
r = rmid;
res = std::min(res, d1);
}
}
return res;
};
Point l(points[0].x, points[0].y), r(points[1].x, points[1].y);
int d;
if (l.y <= r.y) {
d = 1;
} else {
d = -1;
}
f80 res = LONG_LONG_MAX;
if (l.x == r.x && l.y == r.y) {
std::cout << getMinDis(l) << "\n";
return 0;
}
while (std::hypot(l.x - r.x, l.y - r.y) > EPS) {
Point lmid(l.x + std::fabs(r.x - l.x) / 3, l.y + d * std::fabs(r.y - l.y) / 3);
Point rmid(r.x - std::fabs(r.x - l.x) / 3, r.y - d * std::fabs(r.y - l.y) / 3);
f80 d1 = getMinDis(lmid), d2 = getMinDis(rmid);
if (d1 > d2 + EPS) {
l = lmid;
res = std::min(res, d2);
} else {
r = rmid;
res = std::min(res, d1);
}
}
std::cout << res << "\n";
return 0;
}
T2 \({\color{orange}{\text{60pts}}}\text{/100pts}\)
题意
给出一棵二叉树，树上的非叶子节点都有其对应的一个逻辑运算（与、或、非三种之一），节点的值为其两个子节点做对应逻辑运算后得到的值，给出所有叶子结点的初始值，问至少要修改几个叶子节点的值，才能改变树根结点的值。
\(1 \le n \le 2^{17} - 1\)。
思路
这道题基本上就是树形 DP 的裸题，题目中的信息明显在暗示根节点的答案是由子树的答案合并得到的。
于是我们就可以写出方程，记当前节点指定的逻辑算符为 \(\delta\)，\(f_i\) 为改变当前节点的最小改动个数，\(pre_i\) 为节点 \(i\) 开始的值，则有：
\[f_i = \begin{cases} 1 & i \text{ is a leaf;} \\ \min(f_{lc_i}, f_{rc_i}) & \begin{cases} \delta = \wedge \text{ and } pre_i = 1; \\ \delta = \vee \text{ and } pre_i = 0; \\ \delta = \oplus; \\ \end{cases} \\ [pre_{lc_i} = 0] \times f_{lc_i} + [pre_{rc_i} = 0] \times f_{rc_i} & \delta = \wedge \text{ and } pre_i = 0; \\ [pre_{lc_i} = 1] \times f_{lc_i} + [pre_{rc_i} = 1] \times f_{rc_i} & \delta = \vee \text{ and } pre_i = 1. \\ \end{cases} \]有了方程，代码就很容易写了，具体就是两遍 DFS，一遍求出 \(pre\)，另一遍做 DP。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
namespace myFile {
void useFileIO() {
freopen("logical.in", "r", stdin);
freopen("logical.out", "w", stdout);
return;
}
}
struct Tree {
int n;
std::vector<std::vector<int>> ch;
std::vector<int> type, f, pre;
Tree(int n) : n(n + 1) {
ch.resize(n + 1);
type.resize(n + 1, 0);
f.resize(n + 1, 0);
pre.resize(n + 1, 0);
return;
}
bool add(int u, int lc, int rc) {
ch[u].resize(2);
ch[u][0] = lc, ch[u][1] = rc;
return true;
}
void dfs(int u) {
if (ch[u].empty()) {
return;
}
int lc = ch[u][0], rc = ch[u][1];
dfs(lc), dfs(rc);
if (type[u] == 1) {
pre[u] = pre[lc] & pre[rc];
} else if (type[u] == 2) {
pre[u] = pre[lc] | pre[rc];
} else {
pre[u] = pre[lc] ^ pre[rc];
}
return;
}
void solve(int u) {
if (ch[u].empty()) {
f[u] = 1;
return;
}
int lc = ch[u][0], rc = ch[u][1];
solve(lc), solve(rc);
if (type[u] == 1) {
if (pre[u]) {
f[u] = std::min(f[lc], f[rc]);
} else {
f[u] = (!pre[lc]) * f[lc] + (!pre[rc]) * f[rc];
}
} else if (type[u] == 2) {
if (pre[u]) {
f[u] = pre[lc] * f[lc] + pre[rc] * f[rc];
} else {
f[u] = std::min(f[lc], f[rc]);
}
} else {
f[u] = std::min(f[lc], f[rc]);
}
return;
}
};
int main() {
// myFile::useFileIO();
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
Tree tree(n);
int root = 1;
for (int i = 0; i < n; i++) {
int x, y, z, a;
std::cin >> x >> y >> z >> a;
if (!z) {
root = i + 1;
}
x == 0 || tree.add(i + 1, x, y);
tree.type[i + 1] = a;
}
for (int i = 0; i < m; i++) {
int x, y;
std::cin >> x >> y;
tree.pre[x] = y;
}
tree.dfs(root), tree.solve(root);
std::cout << tree.f[root] << "\n";
return 0;
}
T3 \({\color{red}{\text{10pts}}}\text{/100pts}\)
题意
给出 \(n\) 个元素的字符串序列 \(s\)，每个字符串有一个偏爱值 \(a_i\)，现在要求构造一个长度为 \(l\) 的字符串，记一种方法所使用的字符串下标集合为 \(S\)，则这种构造方案的喜爱值为：
\[\sum_{s \in S} a_s \]求喜爱值的最大值。
\(n \le 1000\)，\(|s_i| \le 50\)，\(l \le 100\)。
思路
\(\text{30pts}\)
这部分数据保证 \(n = 1\)。
考虑递推，由于只有一个串，我们容易想到KMP 构造 \(nxt\) 数组，由于 \(nxt\) 是最长公共前后缀，所以我们可以用 \(nxt\) 来状态转移。时间复杂度为 \(O(\alpha l)\)，其中 \(\alpha\) 是常数，表示 \(nxt\) 能跳的最大次数。
\(\text{100pts}\)
仍然使用递推，考虑对 \(s\) 中的串建出 AC 自动机，记自动机中的转移数组为 \(nxt\)，定义状态为 \(f_{i, j}\)，表示构造的字符串的第 \(i\) 位使用字典树中标号为 \(j\) 的字符所能得到的最大喜爱值，则有：
\[f_{i + 1, j} = \max_{k \in fa} f_{i, k} + val \]其中 \(fa\) 为能够转移到 \(j\) 的集合,\(val\) 为转移过程中累加的喜爱值。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
using i64u = unsigned long long;
using f80 = long double;
namespace MyFile {
void useFileInuput() {
#ifndef ONLINE_JUDGE
freopen("tmp.in", "r", stdin);
freopen("tmp.out", "w", stdout);
#endif
return;
}
}
struct ACAM {
std::vector<std::vector<int>> tree;
std::vector<int> end, fail;
ACAM() {
tree.emplace_back(26, 0);
end.push_back(0), fail.push_back(0);
return;
}
void insert(const std::string &s, const int &val) {
int pivot = 0;
for (int i = 0; i < s.length(); i++) {
int d = s[i] - 'a';
if (!tree[pivot][d]) {
tree[pivot][d] = tree.size();
tree.emplace_back(26, 0);
end.push_back(0), fail.push_back(0);
}
pivot = tree[pivot][d];
}
end[pivot] += val;
return;
}
void build() {
static std::queue<int> q;
for (int i = 0; i < 26; i++) {
if (tree[0][i]) {
q.push(tree[0][i]);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
int &v = tree[u][i];
if (v) {
if (u) {
fail[v] = tree[fail[u]][i];
}
q.push(v);
} else {
v = tree[fail[u]][i];
}
}
}
return;
}
void solve(const int &l) {
std::vector f(2, std::vector<int>(tree.size(), INT_MIN));
f[0][0] = 0;
int cur = 0;
for (int i = 0; i < l; i++) {
for (int j = 0; j < 26; j++) {
for (int k = 0; k < tree.size(); k++) {
int tmp = 0;
for (int pivot = k; pivot; pivot = fail[pivot]) {
tmp += end[pivot];
}
f[cur ^ 1][tree[k][j]] = std::max(f[cur ^ 1][tree[k][j]], f[cur][k] + tmp);
}
}
for (int i = 0; i < tree.size(); i++) {
f[cur][i] = INT_MIN;
}
cur ^= 1;
}
int ans = INT_MIN;
for (int i = 0; i < tree.size(); i++) {
ans = std::max(ans, f[cur][i]);
}
std::cout << ans << "\n";
return;
}
};
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, l;
std::cin >> n >> l;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
ACAM acam;
for (int i = 0; i < n; i++) {
std::string s;
std::cin >> s;
acam.insert(s, a[i]);
}
acam.build();
acam.solve(l + 1);
return 0;
}