—— Summon, Light!
0%

牛客周赛 Round 119 题解

发表于 Valine：

老年选手终于AK了一次，真不容易啊

A.ICPC Rank

按题意判断一下

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;

using ll = long long;

int main()
{
    int T = 1;
    while (T--) {
        int x, y, p, q;
        scanf("%d%d%d%d", &x, &y, &p, &q);
        if (x > y) {
            puts("A");
        } else if (x < y) {
            puts("B");
        } else {
            if (p < q) {
                puts("A");
            } else if (p > q) {
                puts("B");
            } else {
                puts("C");
            }
        }
    }
    return 0;
}

B.小苯的序列极值

$i, j$ 取遍任意两数的组合，答案显然为数列极差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int inf = 2e9;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        int dd = inf, hh = -inf;
        for (int i = 1, x; i <= n; i++) {
            scanf("%d", &x);
            dd = min(dd, x);
            hh = max(hh, x);
        }
        printf("%d\n", hh - dd);
    }
    return 0;
}

C.小苯的平方数

表述实在太怪了，先枚举看一下

1
2
3
4
5
6
for i in range(10000):
    j = i**2
    k = sum(int(c) for c in str(j))
    # print(i,j,k)
    if i==k:
        print('[+]', i)

可以发现10000的范围内只有1和9。

简单推导可得再往后更不可能：$k$ 位数的平方数约为 $2k$ 位，这 $2k$ 位就算全都是9也不可能跟原数相等。

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;

using ll = long long;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int ans = 0;
        if (l <= 1 && 1 <= r) ++ans;
        if (l <= 9 && 9 <= r) ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

D.小苯的左右移动

考虑到 $a_i$ 范围可以到 $10^9$，显然要在模意义下做左移操作，但是右移（整除2）无法完全转换到模意义下

所以这题思路是比较显然的，肯定是要把每一步操作叠加起来，最后再处理

比如设置一个 $cnt$ 变量，奇数的时候加，偶数的时候减，直接按 $cnt$ 的最终值计算

然后就发现，这样连样例都过不了。这是为什么？

因为右移操作可能会使 $k$ 的低位丢失，再左移时是不一定能还原为 $k$ 的

因此，我们还需要记录每一步操作后，相对于原先的 $k$ 最多右移了几位，也就是最小值 $mn$

当 $mn<0$ 时，优先处理使 $k$ 的低位丢失的右移操作，也就是 $ k >> |mn| $

但这里又有个坑，当右移操作数过大时，在C++中属于UB（未定义行为），还需要再特判一次，详见代码

老年选手避坑实在太难了，贴个图纪念一下最后十几秒抢救成功了（

提交记录

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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int mod = 998244353;

ll fpow(ll x, ll n)
{
    ll res = 1;
    while (n) {
        if (n & 1) res = res * x % mod;
        n >>= 1;
        x = x * x % mod;
    }
    return res;
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        ll k, cnt = 0, mn = 0, res;
        scanf("%d%lld", &n, &k);
        for (int i = 1, d = 1, x; i <= n; i++, d = -d) {
            scanf("%d", &x);
            cnt += d * x;
            mn = min(mn, cnt);
        }
        if (mn < 0) {
            mn = -mn;
            if (mn >= 50) k = 0;
            else k >>= mn;
            cnt += mn;
        }
        if (cnt <= 0) {
            cnt = -cnt;
            res = (k >> cnt) % mod;
        } else {
            res = k % mod * fpow(2, cnt) % mod;
        }
        printf("%lld\n", res);
    }
    return 0;
}

E.小苯的三角计数

题面已经给出关键点：任意两边长之和大于第三边

先排序，然后枚举最短边，再枚举次短边，用lower_bound取一下最长边的范围就行了

在此基础上，通过判断条数把等边和等腰补进去就行

太模板了，感觉还没C题D题出得好

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;

using ll = long long;
using PII = pair<int, int>;
const int N = 3000;
PII p[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &p[i].first, &p[i].second);
        }
        sort(p + 1, p + n + 1);
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            if (p[i].second > 1) {
                int pos = lower_bound(p + 1, p + n + 1, PII(p[i].first * 2, 0)) - p;
                ans += pos - i - 1;
                if (p[i].second > 2)
                    ans += 1;
            }
            for (int j = i + 1; j <= n; j++) {
                int pos = lower_bound(p + 1, p + n + 1, PII(p[i].first + p[j].first, 0)) - p;
                ans += pos - j - 1;
                if (p[j].second > 1)
                    ans += 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

F.小苯的极大支配

本题的“极大匹配”跟数值大小和出现次数都有关系

首先注意到 $a_i$ 的范围为 $n$，显然可以转化到值域+个数

然后枚举每个数值 $x$，要使 $x$ 成为“极大匹配”的支配数，则必须满足：

  1. 所有大于 $x$ 的数的均被删除
  2. 记 $x$ 出现次数为 $cnt_x$，则对任意 $y \neq x$ 都有 $cnt_y \lt cnt_x$，也即 $cnt_y \leq cnt_x -1$

显然对于每个数值 $x$ 都能计算出答案。

可以从小往大遍历 $x$，但是得维护查询小于特定数的数据结构

我这里直接按 $cnt_x$ 从大到小遍历，用简单后缀和简单前缀就能计算，详见代码

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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e6 + 5;
int cnt[N], p[N], sufs[N];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            cnt[i] = 0;
            p[i] = i;
        }
        for (int i = 1, x; i <= n; i++) {
            scanf("%d", &x);
            cnt[x]++;
        }
        sufs[n + 1] = 0;
        for (int i = n; i >= 1; i--) {
            sufs[i] = sufs[i + 1] + cnt[i];
        }
        sort(p + 1, p + n + 1, [](int x, int y) {
            return cnt[x] > cnt[y];
        });
        int ans = n - 1, pres = 0;
        for (int i = 1, j = i; i <= n; i = j) {
            if (cnt[p[i]] == 0)
                break;
            while (j <= n && cnt[p[j]] == cnt[p[i]])
                ++j;
            pres += (cnt[p[i]]) * (j - i - 1);
            for (int x = i; x < j; x++) {
                int k = p[x];
                int now = pres - (cnt[k] - 1) * (j - 2) + sufs[k + 1];
                ans = min(ans, now);
            }
            pres += cnt[p[i]];
        }
        printf("%d\n", ans);
    }
    return 0;
}
咖啡，亦我所需也