解题报告（ABDEGH/10）
链接：https://ac.nowcoder.com/acm/contest/3002
题目链接：https://ac.nowcoder.com/acm/contest/3002/A
分析：$S=1=\frac{1}{2}\times2\times1$。分形状看一下，每种形状的种数，注意不要算重复了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main() {
LL n, m;
cin >> n >> m;
LL sum = (n - 1) * (m - 2) % mod * (m - 2) % mod + (n - 2) * (m - 1) % mod * n % mod;
sum += (n - 1) * (m - 2) % mod * n % mod + (n - 2) * (m - 1) % mod * (m - 2) % mod;
cout << sum * 2 % mod << endl;
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/B
分析：签到题
1
2
3
4
5
6
7
8
9
10
11
|
#include <bits/stdc++.h>
using namespace std;
int n, x, a, b;
int main() {
cin >> n >> x >> a >> b;
printf("%.2f\n", n * (x * 1.0 / 100 * a + (100 - x) * 1.0 / 100 * b));
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/C
分析：分别将umi和靶子连线与坐标轴的交点存下来，注意不要统计同一象限内的靶子。然后分 $x,y$ 轴，用木板覆盖住 $n-k$ 个交点即可。
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
|
#include <bits/stdc++.h>
using namespace std;
double sx, sy;
int n, k;
vector<double> vx, vy;
int main() {
cin >> sx >> sy >> n >> k;
for (int i = 0; i < n; i++) {
double a, b; cin >> a >> b;
if (sy * b < 0) vx.push_back((a * sy - b * sx) / (sy - b));
if (sx * a < 0) vy.push_back((b * sx - a * sy) / (sx - a));
}
sort(vx.begin(), vx.end());
sort(vy.begin(), vy.end());
// 需要挡住 n - k 个
double ans = 1e18;
int len = n - k;
for (int l = 0; l + len - 1 < vx.size(); l++) {
int r = l + len - 1;
ans = min(ans, vx[r] - vx[l]);
}
for (int l = 0; l + len - 1 < vy.size(); l++) {
int r = l + len - 1;
ans = min(ans, vy[r] - vy[l]);
}
if (ans == 1e18) puts("-1");
else printf("%f\n", ans);
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/D
分析：签到题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <bits/stdc++.h>
using namespace std;
int n;
unordered_set<int> uset;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
uset.insert(x);
}
for (int i = 1; i <= n; i++) {
if (!uset.count(i)) {
printf("%d\n", i);
break;
}
}
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/E
分析：按要求模拟即可，一度怀疑是不是只需要这么做就行了，$AC$ 了就放心了。话说这里不能一个递归写到底啊，MLE 了，用循环来写才行。算因子个数的时候用到了一个定理。
若质因数分解：
$$
N=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}
$$
则 $N$ 约数之和：
$$
(\alpha_1+1)(\alpha_2+1)…(\alpha_k+1)
$$
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int res;
LL f(LL n) {
if (n == 3) return 2;
unordered_map<int, int> primes;
for (LL i = 2; i <= n / i; i++) {
while (n % i == 0) {
n /= i;
primes[i]++;
}
}
if (n > 1) primes[n]++;
LL sum = 1;
for (auto item : primes) sum = sum * (item.second + 1);
return sum;
}
int main() {
LL n;
cin >> n;
while (n != 2) {
n = f(n);
res++;
};
cout << res << endl;
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/F
分析：这题好可惜，比赛时没开long long，赛后一看过了 88.89% 的数据，顿悟。
路径取法有 $2$ 种：
做法：对于第 $1$ 种取法，只要统计与每个黑色结点直接相连的白色点个数，求和；对于第 $2$ 种取法，需要统计每个黑色结点直接相连的子树中，以白色结点为根的白色连通块大小，都存到vector<int> temp中，然后任两个连通块之间都可组合。体现在代码 49 ~ 50 行。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2 * N;
int n;
int h[N], e[M], ne[M], idx;
char str[N];
int tag[N]; // 0表示白
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 返回以u为根的子树中，白色点的个数
int dfs(int u, int fa) {
int sum = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || tag[j]) continue;
int s = dfs(j, u);
sum += s;
}
return sum;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
scanf("%s", str + 1);
for (int i = 1; str[i]; i++) tag[i] = str[i] == 'W' ? 0 : 1;
for (int i = 0; i < n - 1; i++) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
// 从所有黑色点开始搜，白色的子树
long long res = 0;
for (int i = 1; i <= n; i++) {
if (tag[i]) { // 黑色
vector<int> temp;
for (int j = h[i]; ~j; j = ne[j]) {
int k = e[j];
if (!tag[k]) { // 搜白色连通块
temp.push_back(dfs(k, i));
}
}
for (int j = 0; j < temp.size(); j++) res += temp[j];
for (int j = 0; j < temp.size(); j++) {
for (int k = j + 1; k < temp.size(); k++) {
res += 1ll * temp[j] * temp[k];
}
}
}
}
cout << res << endl;
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/G
分析：二分答案区间 $[k,n]$，$check$ 一下 $mid$ 是否有解即可。统计字母出现次数时可以进行优化，对于长度为 $mid$ 的一段子串来说，首先从 $0$ 枚举左端点 $l$，检验 $[0, mid-1]$ 是否有解，如果无解，那么左端点右移一位，这时候我们发现，整个串右移只会影响 $2$ 个字母，也就是上一轮的左端点，和这一轮的右端点，因此只需要cnt[str[l - 1] - 'a']--; cnt[str[r] - 'a']++; 即可。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, k;
char str[N];
int cnt[26];
// 如果长度为mid有解就返回true
bool check(int mid) {
int len = strlen(str);
for (int l = 0; l + mid - 1 < len; l++) {
int r = l + mid - 1;
if (l == 0) {
for (int j = l; j <= r; j++) {
cnt[str[j] - 'a']++;
if (cnt[str[j] - 'a'] >= k) return true;
}
} else {
cnt[str[l - 1] - 'a']--; // 去掉开头
cnt[str[r] - 'a']++; // 加上结尾
if (cnt[str[r] - 'a'] >= k) return true;
}
}
return false;
}
int main() {
cin >> n >> k;
scanf("%s", str);
bool has_ans = false;
for (int i = 0; str[i]; i++) {
cnt[str[i] - 'a']++;
if (cnt[str[i] - 'a'] >= k) has_ans = true;
}
if (!has_ans) {
puts("-1");
return 0;
}
int l = k, r = n;
while (l < r) {
int mid = l + r >> 1;
memset(cnt, 0, sizeof cnt);
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/H
分析：这题和上题不是一样的嘛 = =，$26$ 个字母变成只有 $0,1$，还是二分答案区间 $[k,n]$，改改上题代码就AC了。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, k;
char str[N];
int cnt[2];
// 如果长度为mid有解就返回true
bool check(int mid) {
int len = strlen(str);
for (int l = 0; l + mid - 1 < len; l++) {
int r = l + mid - 1;
if (l == 0) {
for (int j = l; j <= r; j++) cnt[str[j] - '0']++;
if (cnt[0] <= k || cnt[1] <= k) return true;
} else {
cnt[str[l - 1] - '0']--; // 去掉开头
cnt[str[r] - '0']++; // 加上结尾
if (cnt[0] <= k || cnt[1] <= k) return true;
}
}
return false;
}
int main() {
cin >> n >> k;
scanf("%s", str);
for (int i = 0; str[i]; i++) cnt[str[i] - '0']++;
int l = k, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
memset(cnt, 0, sizeof cnt);
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/I
分析：这DP我居然没做！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300010;
LL n, a, b, c;
LL f[N];
string str;
int main() {
cin >> n >> a >> b >> c >> str;
str = " " + str;
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1];
if (i >= 4 && str.substr(i - 3, 4) == "nico") f[i] = max(f[i], f[i - 4] + a);
if (i >= 6 && str.substr(i - 5, 6) == "niconi") f[i] = max(f[i], f[i - 6] + b);
if (i >= 10 && str.substr(i - 9, 10) == "niconiconi") f[i] = max(f[i], f[i - 10] + c);
}
cout << f[n] << endl;
return 0;
}
|
题目链接：https://ac.nowcoder.com/acm/contest/3002/I
分析：当时 F 题 WA 了一次之后就直接来做 J 了，因为 J 提交次数相当多，但是通过率极低（没注意），推了一下，总结出一个公式：
$$
f(n)=x^{fi_{n-2}} \cdot y^{fi_{n-1}} \cdot a^{(fi_n-1)\cdot b} \text{ % mod}
$$
其中 $fi(i)$ 表示斐波那契数列第 $i$ 项。看了数据范围，于是我直接套上矩阵快速幂求斐波那契的板子，然后中间各种模，从此走上一条疯狂调试的不归路。赛后再测，发现通过 80% 了，所以应该是优化不够啊 = =，果然这不是我能做的题啊。有空补题。
感觉有提升余地，DP 还是硬伤，二分最近遇到比较多比较敏感，矩阵快速幂还是昨晚临时学的，虽然今天就是复制粘贴板子。两道字符串标程都不是二分，但都被我二分过了emm。不过感觉自己比半年前刚开始学算法，有点进步啊。
第一场官方说明考点：字符串，贪心，矩阵快速幂，概率论，计算几何，并查集，数论。