[Nowcoder]2020牛客寒假算法基础集训营6

20200213 第五场

进度（5 / 10）未完成：B / C / E / H / I

A、配对

1、链接

https://ac.nowcoder.com/acm/contest/3007/A

2、题面

现在有正整数集合 A 和 B，每个集合里有 N 个数，你要建立他们间的一一映射

将每对配对的数字相加可以得到 N 个和，你要做的就是最大化第 K 大的和

1≤K≤N≤100,000 输入的所有数字不超过 10⁸

3、思路

贪心。首先可以知道一点——前k大的和必然由集合a的前k大数和集合b的前k大数组成。后面 n - k + 1个数都可以删了。

为了使第k大最大，即让当前的2 * k个数组成的最小的一对最大，通过归纳，倒序配对为最优解（我也不知道怎么归纳，反正就这么想了）。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define INF 1 << 30
 5 #define MAXN 100005
 6 
 7 int n, k, a[MAXN], b[MAXN], ans = INF;
 8 
 9 struct cmp {
10     bool operator () (int a, int b) {
11         return a > b;
12     }
13 } x;
14 
15 int main() {
16     cin >> n >> k;
17     for (int i = 1; i <= n; i++) cin >> a[i];
18     for (int i = 1; i <= n; i++) cin >> b[i];
19     sort(a + 1, a + n + 1, x), sort(b + 1, b + n + 1, x);
20     for (int i = 1; i <= k; i++)
21         ans = min(ans, a[i] + b[k - i + 1]);
22     cout << ans;
23     return 0;
24 }

D、重排列

1、链接

https://ac.nowcoder.com/acm/contest/3007/D

2、题面

一个序列的重排列是指对这个序列中的元素进行若干次（包括0次）交换操作后得到的新序列

在本题中，序列中可能出现重复的数字，他们被视作不同的元素

例如，序列1 1的重排列有两种

现在有两个长度为 N 的非负整数序列 A 和 B，问有多少种 A 的重排列满足对于所有的 1≤i≤N，有A_i≤B_i

由于答案可能很大，你只需要输出答案对1e9+7取模的结果

3、思路

由于每个位置相对独立，序列顺序就无所谓了，于是我们先将A, B分别从小到大排序，假设A序列前 i 个数字均 <= B序列第 j 位，必存在 k >= i，满足前 k 个数字均 <= B序列第 j + 1位。由于已经在前 i 个数字中选择了一个排在第 j 位，而对于第 j + 1位要选择哪一个数字，其实与第 j 位选择的是哪一个并没任何关联，也就是说，如果第 j 位有 i 种选择，则第 j + 1位有 k - 1种选择，直接相乘即可。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 #define MAXN 1000005
 7 #define MOD 1000000007
 8 
 9 ll n, a[MAXN], b[MAXN], o = 1, ans = 1;
10 
11 int main() {
12     cin >> n;
13     for (int i = 1; i <= n; i++) cin >> a[i];
14     for (int i = 1; i <= n; i++) cin >> b[i];
15     sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
16     for (int i = 1; i <= n; i++) {
17         while (a[o] <= b[i] && o <= n) o++;
18         (ans *= (o - i)) %= MOD;
19     }
20     cout << ans; 
21     return 0;
22 }

F、十字阵列

1、链接

https://ac.nowcoder.com/acm/contest/3007/F

2、题面

小 Q 新学会了一种魔法，可以对一个 N行M列的网格上的敌人造成伤害

第 i 次使用魔法可以对网格上的一个十字形区域（即第 xi 行和第 yi 列的并）中的每个格子上的敌人造成 zi 点伤害

现在小 Q 一共使用了 H 次魔法，你需要在所有的施法完成之后统计造成伤害的情况，详见输出描述

提醒：本题输入规模较大，请使用高效的输入方式

1≤H≤500,000 1≤xi,yi,zi,N,M≤2000 1≤xi≤N,1≤yi≤M

3、思路

这题面和输入输出样例的描述我要吐槽了，这不是我一个个去算了下才知道这是个什么计算方式，不然根本不知所云。

知道怎么算后就没什么难度了，唯一注意的是题目要求要加输入优化了。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAXN 100005
 5 #define MOD 1000000007
 6 
 7 typedef long long ll;
 8 
 9 ll n, m, h, x, y, z, ans;
10 
11 ll getint() {
12     ll res = 0;
13     char ch = getchar();
14     while (ch < '0' || ch > '9') ch = getchar();
15     while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
16     return res;
17 }
18 
19 int main() {
20     cin >> n >> m >> h;
21     for (int i = 1; i <= h; i++) {
22         x = getint(), y = getint(), z = getint();
23         (ans += z * (((2 * x + 1 + m) * m + (2 * y + 1 + n) * n) / 2 - x - y)) %= MOD;
24     }
25     cout << ans;
26     return 0;
27 }

G、括号序列

1、链接

https://ac.nowcoder.com/acm/contest/3007/G

2、题面

合法括号序列的定义是：

1.空序列是合法括号序列

2.如果 S 是一个合法括号序列,那么(S)是合法括号序列

3.如果 A 和 B 都是合法括号序列,那么 AB 是一个合法括号序列

现在给定一个括号序列，求最少删去几个括号能得到一个合法的括号序列

输入包含 T 组数据，每组数据中，设括号序列的长度为 N

1≤T,ΣN≤1,000,000

（由于空串是合法的括号序列，所以答案可以是N）

3、思路

很熟悉的一道题，这就是更裸的栈问题了。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAXN 1000005
 5 
 6 stack <int> s;
 7 char ch[MAXN];
 8 int l, t;
 9 
10 int main() {
11     cin >> t;
12     for (int j = 1; j <= t; j++) {
13         int ans = 0;
14         cin >> l >> ch + 1;
15         for (int i = 1; i <= l; i++) {
16             if (ch[i] == '(') s.push(ch[i]);
17             else if (s.empty()) ans++;
18             else s.pop();
19         }
20         while (!s.empty()) s.pop(), ans++;
21         cout << ans << endl;
22     }
23     return 0;
24 }

J、签到题

1、链接

https://ac.nowcoder.com/acm/contest/3007/G

2、题面

现有一个边长为正整数的三角形，问能否以其三个顶点为圆心画三个圆，使三个圆两两外切

三边长均不超过10⁸

3、思路

签到题反倒没那么签到，我还要在纸上画画（

半径和边长的关系求出来后就简单了。题目弄了个什么画不出输出No，却压根没这个情况，2020了咋还有这种玩法。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 double a[3];
 5 
 6 int main() {
 7     cin >> a[0] >> a[1] >> a[2];
 8     sort(a, a + 3);
 9     if (a[0] + a[1] <= a[2]) cout << "wtnl";
10     else {
11         double o = 0.5 * (a[0] + a[1] + a[2]);
12         printf("Yes
%.2lf %.2lf %.2lf", o - a[2], o - a[1], o - a[0]);
13     }
14     return 0;
15 }