2020 牛客寒假算法基础集训营 1

解题报告(ABDEGH/10)

链接:https://ac.nowcoder.com/acm/contest/3002

A. honoka和格点三角形

题目链接: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;
}

B. kotori和bangdream

题目链接: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;
}

C. umi和弓道(已补)

题目链接: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;
}

D. hanayo和米饭

题目链接: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;
}

E. rin和快速迭代

题目链接: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;
}

F. maki和tree(已补)

题目链接: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;
}

G. eli和字符串

题目链接: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;
}

H. nozomi和字符串

题目链接: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;
}

I.nico和niconiconi(已补)

题目链接: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;
}

J. u's的影响力(待补)

题目链接: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% 了,所以应该是优化不够啊 = =,果然这不是我能做的题啊。有空补题。

1

总结

感觉有提升余地,DP​ 还是硬伤,二分最近遇到比较多比较敏感,矩阵快速幂还是昨晚临时学的,虽然今天就是复制粘贴板子。两道字符串标程都不是二分,但都被我二分过了emm。不过感觉自己比半年前刚开始学算法,有点进步啊。

第一场官方说明考点:字符串,贪心,矩阵快速幂,概率论,计算几何,并查集,数论。

updatedupdated2020-07-022020-07-02
加载评论
点击刷新