解题报告(ABFGJ/10)
链接:https://ac.nowcoder.com/acm/contest/3007
A. 配对
题目链接:https://ac.nowcoder.com/acm/contest/3007/A
分析:贪心,先把两个数组的前 $k$ 大都取出来,在这些数中来进行匹配,需要使得最小值最大,那么构造方案显然就是:最小+最大,次小+次大...。简陋证明如下:
假设存在 $a_1 > a_2,\ b_1 > b_2$,如果匹配方式为:$a_1+b_1,\ a_2 + b_2$,那么最小值为 $a_2+b_2$,而采取上面所说的构造方案:$a_1+b_2,\ a_2+b_1$,最小值一定在这两个数之间,且一定大于上一种方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k;
int a[N], b[N], c[N], cnt;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
sort(a + 1, a + n + 1, greater<int>());
sort(b + 1, b + n + 1, greater<int>());
for (int i = 1; i <= k; i++) c[cnt++] = a[i] + b[k - i + 1];
sort(c, c + cnt);
cout << c[0] << endl;
return 0;
}
|
B. 图
题目链接:https://ac.nowcoder.com/acm/contest/3007/B
闲话:比较喜欢图论问题,所以看到这么简单粗暴的标题我就直接进来了。结果没想到这题变成了我的签到题,然后在 $J$ 题(真·签到)卡了好久。
分析:题意要求一条最长链。假如这是一个有向无环图,那么问题就很简单了,只要按照拓扑序求最长路即可。但是题目特别提到了简单路径,说明图中可能存在正环。所以,自然想到 $Tarjan$ 缩点,原图转化成了 $DAG$,然后按拓扑序求一遍最长路就行了啊。(不过看完题解,发现我还是做麻烦了,板子有啥麻烦)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <bits/stdc++.h>
using namespace std;
const int N = 1000010, M = N * 2;
int n;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], tt;
bool in_stk[N];
int id[N], sz[N], scc_cnt;
int dist[N], cnt[N];
void add(int h[], int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stk[++tt] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
} else if (in_stk[j]) {
low[u] = min(low[u], dfn[j]);
}
}
if (dfn[u] == low[u]) {
++scc_cnt;
int v;
do {
v = stk[tt--];
in_stk[v] = false;
id[v] = scc_cnt;
sz[scc_cnt]++;
} while (v != u);
}
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
add(h, i, x);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= n; i++) {
for (int j = h[i]; ~j; j = ne[j]) {
int k = e[j];
int a = id[i], b = id[k];
if (a != b) add(hs, a, b);
}
}
for (int i = scc_cnt; i; i--) {
if (!dist[i]) dist[i] = sz[i];
for (int j = hs[i]; ~j; j = ne[j]) {
int k = e[j];
dist[k] = max(dist[k], dist[i] + sz[k]);
}
}
int res = 0;
for (int i = 1; i <= scc_cnt; i++) {
res = max(res, dist[i]);
}
printf("%d\n", res);
return 0;
}
|
C. 汉诺塔(待补)
题目链接:https://ac.nowcoder.com/acm/contest/3007/C
分析:
D. 重排列(已补)
题目链接:https://ac.nowcoder.com/acm/contest/3007/D
闲话:这题就白给了,WA了好几次,以为是构造 $b[\ ]$,求方案数,比赛结束,经过别人提醒,才发现看反了要求,枯。
分析:计数问题。排序不影响方案数,从小到大枚举每一个 $b[i]$,求一下 $a[\ ]$ 中 $\le b[i]$ 的数的个数 $num$,然后乘起来就行了。注意,对于 $b[1]$,在 $a[\ ]$ 中有 $num$ 种选择,对于 $b[i],i>1$,选择个数需要减去前面已经用到的 $i-1$ 个。考虑用树状数组来统计 $a[\ ]$ 中 $\le b[i]$ 的数的个数,需要离散化。(看完题解我好像又做麻烦了)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n;
int a[N], b[N];
int c[N];
vector<int> alls;
int lowbit(int x) {
return x & -x;
}
void add(int x, int y) {
for (int i = x; i <= alls.size(); i += lowbit(i)) c[i] += y;
}
int sum(int x) {
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += c[i];
return res;
}
int find(int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
alls.push_back(a[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
alls.push_back(b[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i++) {
int t = find(a[i]);
add(t, 1);
}
LL res = 1; // 从小到大枚举b[i],找到 <= b[i]的个数
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) {
int num = sum(find(b[i]));
if (i == 1) res *= num;
else res *= max(0, (num - i + 1));
res %= mod;
}
cout << res << endl;
return 0;
}
|
E. 立方数(待补)
题目链接:https://ac.nowcoder.com/acm/contest/3007/E
分析:
F. 十字阵列
题目链接:https://ac.nowcoder.com/acm/contest/3007/F
分析:简单二维差分。(一开始看不懂输出要求...)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010, mod = 1e9 + 7;
int n, m, q;
LL b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main() {
cin >> n >> m >> q;
while (q--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
insert(x, 1, x, m, z);
insert(1, y, n, y, z);
insert(x, y, x, y, -z);
}
LL res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
b[i][j] %= mod;
(res += b[i][j] * (i + j)) %= mod;
}
}
cout << res << endl;
return 0;
}
|
G. 括号序列
题目链接:https://ac.nowcoder.com/acm/contest/3007/G
分析:堆栈搞一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int T, n;
char stk[N];
char op[N];
int main() {
cin >> T;
while (T--) {
scanf("%d", &n);
int res = 0, tt = 0;
scanf("%s", op);
for (int i = 0; op[i]; i++) {
if (op[i] == '(') stk[++tt] = ')';
else {
if (!tt) res++;
else if (stk[tt--] != ')') res++;
}
}
res += tt;
printf("%d\n", res);
}
return 0;
}
|
H. 云(待补)
题目链接:https://ac.nowcoder.com/acm/contest/3007/H
分析:
I. 导航系统(待补)
题目链接:https://ac.nowcoder.com/acm/contest/3007/I
分析:
J. 签到题
题目链接:https://ac.nowcoder.com/acm/contest/3007/J
分析:列一下半径和边长的方程即可。(一开始看是个签到题,直接猜等腰,结果浪费好长时间)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
int a[3];
double res[3];
int main() {
for (int i = 0; i < 3; i++) cin >> a[i];
sort(a, a + 3);
if (a[0] + a[1] <= a[2]) puts("wtnl");
else {
double r1, r2, r3;
r1 = (a[1] + a[2] - a[0]) / 2.0;
r2 = (a[0] + a[2] - a[1]) / 2.0;
r3 = (a[0] + a[1] - a[2]) / 2.0;
if (r1 < 0 || r2 < 0 || r3 < 0) puts("No");
else {
puts("Yes");
res[0] = r1, res[1] = r2, res[2] = r3;
sort(res, res + 3);
for (int i = 0; i < 3; i++) printf("%.2f ", res[i]);
puts("");
}
}
return 0;
}
|
总结
本来开局做掉 $B$ 体验很好,结果卡 $J$,最后 $D$ 看错题目,没 $AC$ 可惜了。
第六场官方说明考点:贪心,图论,构造,二分,计数,数论,思维