3 月 1 日测试题解
T1
题意
给你一个 \(n \times m\) 的 01 矩形，求一个面积最大的不包含数字 1 的矩形。
\(n,m \le 1000\)。
思路
首先，这道题的数据水到了什么程度呢？\(O(n ^ 3)\) 的暴力可以轻松跑过。所以我个人认为这道题没有任何价值。
\(\text{20pts(Maybe)}\)
我们考虑直接枚举矩形的上下与左右边界，显然这样做的复杂度为 \(O(n ^ 4)\)。
\(\text{60pts(Maybe)}\)
上边的做法有一个显而易见的优化：可以预处理出一个数组 \(f_{i, j}\)，表示从第 \(i\) 行第 \(j\) 列最多能向上走的格数，这样，我们可以不用枚举上边界，时间复杂度降为 \(O(n ^ 3)\)。
\(\text{100pts}\)
分析时间复杂度高在什么地方，发现枚举下边界的过程是无法优化的，于是只能从枚举左右边界的部分下手。
我们发现，枚举左右边界的部分实质上是在求从第 \(i\) 行第 \(j\) 列能够向左右拓展的最大宽度，也就是要在左右各找到第一个其 \(f\) 值小于 \(f_{i, j}\) 的一列。而求第一个比某个值小的值，我们不难想到使用单调栈来维护。这样，枚举左右边界的时间复杂度降为线性，总体时间复杂度为 \(O(n ^ 2)\)。
代码
\(\text{100pts}\)
我使用的方法跑了两遍单调栈，但事实上有只用一遍的更优秀做法。
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> v(n + 1, std::vector<int>(m + 1, 0));
std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
std::cin >> v[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (v[i][j] == 0) {
f[i][j] = f[i - 1][j] + 1;
}
}
}
int ans = 0;
std::vector<int> tmp(m + 1, 0);
std::stack<int> s1;
for (int i = 1; i <= n; i++) {
tmp.clear();
tmp.resize(m + 1, 0);
while (!s1.empty()) {
s1.pop();
}
for (int j = 1; j <= m; j++) {
int cur = f[i][j];
while (!s1.empty() && f[i][s1.top()] >= cur) {
s1.pop();
}
if (s1.empty()) {
tmp[j] = j;
} else {
tmp[j] = j - s1.top();
}
s1.push(j);
}
while (!s1.empty()) {
s1.pop();
}
for (int j = m; j >= 1; j--) {
int cur = f[i][j];
while (!s1.empty() && f[i][s1.top()] >= cur) {
s1.pop();
}
if (s1.empty()) {
tmp[j] += m - j;
} else {
tmp[j] += s1.top() - j - 1;
}
s1.push(j);
}
for (int j = 1; j <= m; j++) {
// std::cout << tmp[j] << " \n"[j == m];
ans = std::max(ans, tmp[j] * f[i][j]);
}
}
std::cout << ans << "\n";
return 0;
}
T2
题意
给你一棵 \(n\) 个节点的树，问每个节点到其余节点的最大距离。
\(n \le 10000\)。
思路
\(\text{60pts(Maybe)}\)
考虑枚举每个节点，并以其为根做一遍 DFS 求出其到其余节点的距离，然后在其中找出最大的。时间复杂度 \(O(n ^ 2)\)。
\(\text{100pts}\)
我们首先求出这棵树上的任意一条直径，对于直径上的点，其到其他端点的最大距离显然是其到直径左端点距离与到右端点距离的较大值，否则这条链无法成为直径。而对于不在直径上的节点，我们可以认为其是“挂”在直径上的某个点上的，于是对于这个点，要求的就是它与它的“挂载点”的距离与其“挂载点”的答案之和。这个也可以用反证法证明。时间复杂度为 \(O(n)\)。
但是这道题还有一个玄之又玄的树剖写法？反正我不会。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
static const int INF = 0x3f3f3f3f;
template<int N>
struct Tree {
int n;
std::vector<int> e[N], f[2], dis, ans, nxt;
std::vector<bool> vis;
int L, R, D;
Tree(int num) {
f[0].resize(N, 0);
f[1].resize(N, 0);
dis.resize(N, 0);
ans.resize(N, 0);
nxt.resize(N, 0);
vis.resize(N, 0);
n = num;
L = 0, R = 0, D = 0;
return;
}
void add(int u, int v) {
e[u].push_back(v);
return;
}
void dfs(int u, int from) {
dis[u] = dis[from] + 1;
nxt[u] = from;
for (auto v : e[u]) {
if (v == from) {
continue;
}
dfs(v, u);
}
return;
}
void get() {
dfs(1, 0);
for (int i = 1; i <= n; i++) {
if (dis[L] < dis[i]) {
L = i;
}
}
dfs(L, 0);
for (int i = 1; i <= n; i++) {
if (dis[R] < dis[i]) {
R = i;
}
}
D = dis[R] - dis[L];
return;
}
void dfs2(int u, int from, int pivot) {
for (auto v : e[u]) {
if (v == from || vis[v]) {
continue;
}
dis[v] = dis[u] + 1;
ans[v] = dis[v] + ans[pivot];
dfs2(v, u, pivot);
}
return;
}
void solve() {
int pivot = 0;
for (int i = R; i; i = nxt[i]) {
ans[i] = std::max(D - pivot, pivot);
dis[i] = 0;
vis[i] = true;
pivot++;
}
for (int i = R; i; i = nxt[i]) {
dfs2(i, 0, i);
}
for (int i = 1; i <= n; i++) {
std::cout << ans[i] << "\n";
}
return;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n;
Tree<10050> G(n);
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
G.add(u, v);
G.add(v, u);
}
G.get();
G.solve();
return 0;
}
T3
题意
给你一个 \(n\) 个点 \(m\) 条边的带权无向图与 \(k\) 条可能的从 \(1\) 到 \(n\) 的路径。你要判断哪条路径最短并输出这条路径的总长度。若无合法路径，输出 \(\texttt{Wrong}\)。
\(n \le 1000\)，\(m \le 500000\)，\(k \le 100\)，不保证没有重边，保证合法的路径经过的节点数不超过 \(1000\)。
思路
\(\text{100pts}\)
这道题只有一个做法：模拟。而且丝毫没有思维难度。这道题恶心的地方在于其中的众多陷阱。
- 题目没有保证输入一定合法，如 \(\texttt{I can't solve this!}\) 这种奇怪的字符串也是有可能出现的。
- 题目中只规定了所经过的节点数，但并未保证其互不相同，也有可能一直在兜圈子。
- 有的输入会在最后打一个空格，需要特殊处理。
这道题输入的毒瘤程度超乎了我的想象。调了将近半个小时才发现最后有一个空格。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
using vdb = std::vector<long double>;
static const long double INF = 1e18;
void read(int &x) {
x = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = 10 * x + c - '0', c= getchar();
}
int main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(0);
int n, m, k;
std::cin >> n >> m >> k;
std::vector<vdb> e(n + 1, vdb(n + 1, INF));
for (int i = 1; i <= n; i++) {
e[i][i] = 0;
}
for (int i = 1; i <= m; i++) {
int u, v;
long double w;
read(u);
read(v);
scanf("%llf", &w);
e[u][v] = std::min(e[u][v], w);
e[v][u] = e[u][v];
}
std::cin.get();
long double ans = INF;
for (int i = 1; i <= k; i++) {
std::vector<int> path;
std::string s;
std::getline(std::cin, s);
if (s[s.length() - 1] == ' ') {
s = s.substr(0, s.length() - 1);
}
int cnt = 0, len = s.length();
bool isBad = false;
for (int i = 0; i <= len; i++) {
if (i != len && !isdigit(s[i]) && s[i] != ' ') {
isBad = true;
break;
}
if (i == len || s[i] == ' ') {
if (path.empty() || cnt != *(path.end() - 1)) {
path.push_back(cnt);
}
cnt = 0;
} else {
cnt = cnt * 10 + s[i] - '0';
}
}
if (isBad) {
continue;
}
if (path[0] != 1 || *(path.end() - 1) != n) {
continue;
}
int lst = path[0], cur = 0;
long double curAns = 0;
bool flg = true;
for (int i = 1; i < path.size(); i++) {
cur = path[i];
if (cur > n || cur < 1 || e[lst][cur] == INF) {
flg = false;
break;
}
curAns += e[lst][cur];
lst = cur;
}
if (!flg) {
continue;
}
ans = std::min(curAns, ans);
}
if (ans == INF) {
std::cout << "Wrong" << "\n";
} else {
std::cout << std::fixed << std::setprecision(4) << ans << "\n";
}
return 0;
}
T4
题意
求长度为 \(n\) 的不包含超过 \(l\) 个 1 的第 \(i\) 个 01 串。
对于 \(40\%\) 的数据，\(1 \le n \le 100\)。
对于 \(100\%\) 的数据，\(1 \le l \le n \le 31\)，保证 \(i\) 有意义。
思路
又是一道没有意义的题。
\(\text{40pts}\)
我们考虑枚举每一个属于 \([1, n]\) 的正整数并判断其合法性。时间复杂度 \(O(n \log n)\)。
\(\text{100pts(Fake)}\)
我们知道 gcc 内置了一个函数叫做 __builtin_popcount()，可以在 \(O(1)\) 时间内计算出一个数的二进制表达中的 1 的个数。
仍然使用上边的做法，这样时间复杂度降为 \(O(n)\)。
什么？你不信这能过？LOJ 的机子跑 \(10^9\) 的数据只需要不到 400ms！
\(\text{100pts}\)
显然，答案是具有单调性的，但是不是严格单调。也就是说可以二分答案，然后用数位 DP 验证这个答案即可。
这个数位 DP 比板子还板子，应该不会错吧。
但这道题有个很恶心的地方，就是你这样二分出来的答案不一定是合法的，还要判断一下合法性，不合法的话要一直自增。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
static const int N = 60;
i64 f[N][2][N];
i64 n, L, I;
int nums[N], len;
i64 dfs(int pos, int cur, int all, bool isLimited) {
if (all > L) {
return 0;
}
if (!pos) {
return all <= L;
}
if (!isLimited && ~f[pos][cur][all]) {
return f[pos][cur][all];
}
int up = isLimited ? nums[pos] : 1;
i64 res = 0;
for (int i = 0; i <= up; i++) {
res += dfs(pos - 1, i, all + (i == 1), isLimited && i == up);
}
if (!isLimited) {
f[pos][cur][all] = res;
}
return res;
}
i64 calc(i64 mid) {
if (mid == 0) {
return 1;
}
len = 0;
i64 res = 0;
while (mid) {
nums[++len] = mid & 1;
mid >>= 1;
}
for (int i = 0; i <= nums[len]; i++) {
res += dfs(len - 1, i, i == 1, i == nums[len]);
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
memset(f, -1, sizeof(f));
std::cin >> n >> L >> I;
i64 l = 0, r = 1ll << n;
while (calc(l) + 1 < calc(r)) {
i64 mid = (l + r) >> 1;
if (calc(mid) > I) {
r = mid;
} else {
l = mid;
}
}
while (__builtin_popcount(l) > L && calc(l) < I - 1) {
l++;
}
std::vector<int> ans;
while (l) {
ans.push_back(l & 1);
l >>= 1;
}
while (ans.size() < n) {
ans.push_back(0);
}
std::reverse(ans.begin(), ans.end());
for (auto i : ans) {
std::cout << i;
}
std::cout << "\n";
return 0;
}