前言
题解
这其实是第二届大学生算法大赛(清华社杯)的真题,之前比赛的时候,C题(洞穴探险)没做出来,这次终于把它补上了,理清楚思路,还是蛮简单的。
A. 变化的矩形
签到题
一个矩阵,其长扩大50%,高缩小50%,则最后的面积为多少?
S ′ = w ∗ 1.5 ∗ h ∗ 0.5 = w ∗ h ∗ 0.75 = 0.75 ∗ S S' = w * 1.5 * h * 0.5 = w * h * 0.75 = 0.75 * S S′=w∗1.5∗h∗0.5=w∗h∗0.75=0.75∗S
对于控制小数的个数的输出,可以借助setpercision来实现
有也可以借助 scanf/printf 输入输出流
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int s;
cin >> s;
double ns = s * 1.5 * 0.5;
cout << std::fixed << std::setprecision(6) << ns << endl;
return 0;
}
B. 吃鸡梦之队
思路: 二分 + 分类讨论
- 二分d
- check为贪心构造
这个check还是挺难写的,我这边的思路是分类讨论
假定X1,X2(X1<=X2), X3,X4(X3<=X4)
可以观察发现
其实 X 1 / X 2 , X 3 / X 4 在数值上一定是挨着的 其实X1/X2, X3/X4在数值上一定是挨着的 其实X1/X2,X3/X4在数值上一定是挨着的
那确定X1/X2,如何寻找X3/X4呢?
- 二分是种策略,这样时间复杂度为 O ( l o g V ∗ n ∗ l o g n ) O(logV * n*logn) O(logV∗n∗logn)
- 双指针优化,可以把整体的时间复杂度降为 O ( l o g V ∗ n ) O(logV * n) O(logV∗n)
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
bool solve(vector<int>& a, vector<int> &b, vector<int> &c, vector<int> &d, int m) {
int res = inf;
int n1 = a.size(), n2 = b.size(), n3 = c.size(), n4 = d.size();
int i2 = 0, i3 = 0, i4 = 0;
for (int i1 = 0; i1 < n1; i1++) {
// 保证b[i2] 比 a[i1] 大(包含等于)
while (i2 < n2 && b[i2] < a[i1]) {
i2++;
}
if (i2 == n2) return false;
while (i3 < n3 && b[i2] - c[i3] > m) {
i3++;
}
if (i3 == n3) return false;
while (i4 < n4 && d[i4] < c[i3]) {
i4++;
}
if (i4 == n4) return false;
if (d[i4] - a[i1] <= m) return true;
}
return false;
}
bool process(vector<vector<int>> &arr, int m) {
return solve(arr[0], arr[1], arr[2], arr[3], m)
|| solve(arr[0], arr[1], arr[3], arr[2], m)
|| solve(arr[1], arr[0], arr[2], arr[3], m)
|| solve(arr[1], arr[0], arr[3], arr[2], m);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t-- > 0) {
int n;
cin >> n;
vector<int> arr(n);
vector<int> val(n);
for (int &x: arr) cin >> x;
for (int &x: val) cin >> x;
vector<vector<int>> grps(4);
for (int i = 0; i < n; i++) {
grps[arr[i] - 1].push_back(val[i]);
}
for (int i = 0; i < 4; i++) {
sort(grps[i].begin(), grps[i].end());
}
// 分类讨论
int l = 0, r = (int)1e9;
while (l <= r) {
int m = l + (r - l) / 2;
if (process(grps, m)) {
r = m - 1;
} else {
l = m + 1;
}
}
cout << l << '\n';
}
return 0;
}
C. 洞穴探险
题目描述:
简单来说,就是 在一个无向图中,两个点之间关系 (存在多条简单路径,一条简单路径,不联通), 请判断两点之间的关系。
思路: 并查集 + tarjan割边
对于通联和非联通,其实很简单,只要简单的并查集即可。
但是仅有一条简单路径,多条简单路径的情况,就感觉很头痛。
所以呢,可以从删边的角度出发.
如果 A 到 B 存在一条简单路径,其任意一条边删去,都会导致 A B 不联通,那就是 O N E 关系,否则 M O R E 关系 如果A到B存在一条简单路径,其任意一条边删去,都会导致AB不联通,那就是ONE关系,否则MORE关系 如果A到B存在一条简单路径,其任意一条边删去,都会导致AB不联通,那就是ONE关系,否则MORE关系
而这样的删边,不就是割边吗?
因此引入2个并查集
- 用于维护图的联通性判定 S1
- 由割边图主导的联通性判定 S2
那么如果节点A,B属于S1
- A,B属于S2的同组,则A,B为ONE关系
- A,B不属于S2的同组,那么A,B存在多条简单路径,即为More
特别要注意:
该图是森林 该图是森林 该图是森林
#include <bits/stdc++.h>
using namespace std;
struct Dsu {
Dsu(int n) : n(n), arr(n, -1) {}
int find(int u) {
if (arr[u] == -1) {
return u;
}
return arr[u] = find(arr[u]);
}
void merge(int u, int v) {
int a = find(u), b = find(v);
if (a != b) {
arr[a] = b;
}
}
int n;
vector<int> arr;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t-- > 0) {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
Dsu dsu1(n);
Dsu dsu2(n);
int seqno = 0;
vector<bool> vis(n, false);
vector<int> dfn(n, 0), low(n, 0);
function<void(int, int)> tarjan;
tarjan = [&](int u, int fa) {
vis[u] = true;
dfn[u] = low[u] = ++seqno;
for (int v: g[u]) {
if (!vis[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
dsu2.merge(u, v);
}
} else if (v != fa) {
low[u] = min(low[u], dfn[v]);
}
dsu1.merge(u, v);
}
};
for (int i = 0; i < n; i++) {
if (!vis[i]) {
tarjan(i, -1);
}
}
while (q-- > 0) {
int u, v;
cin >> u >> v;
u--; v--;
if (dsu1.find(u) == dsu1.find(v) && dsu2.find(u) != dsu2.find(v)) {
cout << "MORE THAN ONE" << '\n';
} else if (dsu1.find(u) == dsu1.find(v)) {
cout << "ONE" << '\n';
} else {
cout << "NONE" << '\n';
}
}
}
return 0;
}
D. 新冠病毒
签到题
自然数累加和,然后求平均数(向下取整)
S = ∑ i = 1 i = n i = n ∗ ( n + 1 ) / 2 S = \sum_{i=1}^{i=n} i = n * (n+1) / 2 S=i=1∑i=ni=n∗(n+1)/2
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int64_t s = (int64_t)n * (n + 1) / 2;
int64_t avg = s / n;
cout << s << endl;
cout << avg << endl;
return 0;
}