Blog of RuSun

OneProblemIsDifficultBecauseYouDon′tKnowWhyItIsDiffucult

CF1649

发表于 分类于
本文字数： 7.5k 阅读时长 ≈ 7 分钟
标签：        

Codeforces Round #775 (Div. 2)

A. Game

如果是 1 就直接跳，可以使用一次魔法向后跳。显然只能在前后跳。

查看代码 
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;
const int N = 110;
int n, w[N];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> w[i];
        int p = 1, q = n;
        while (p + 1 <= n && w[p + 1] == 1)
            p++;
        while (q > 1 && w[q - 1] == 1)
            q--;
        cout << (p >= q ? 0 : q - p) << endl;
    }
    return 0;
}

B. Game of Ball Passing

给定每个人传出球次数，问至少有多少个球。

贪心，一个球，将所有人都和次数最多的人来回传球即可，如果次数最多的人还需要传球，就需要加球；否则一定可以一个球完成。

查看代码 
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 = 1e5 + 10;
int n, w[N];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        int mx = 0;
        long long sum = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> w[i];
            w[i] > mx && (mx = w[i]);
            sum += w[i];
        }
        if (sum == 0)
            puts("0");
        else if (mx > sum - mx)
            printf("%lld\n", mx - (sum - mx));
        else
            puts("1");
    }
    return 0;
}

C. Weird Sum

给定一个矩阵，对于其中任意两个相同的数 wx1,y1,wx2,y2 ，贡献代价 |x1−x2||y1−y2| 。求总代价。

将所有的数相同的数放在一起，将行和列分开计算。现在问题转化为一个序列，两两求绝对值差的和。可以将所有的排序了求，也可以树状数组求。

查看代码 
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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
int n, m, w[N];
vector<int> c[N], r[N];
LL calc(vector<int> &x)
{
    sort(x.begin(), x.end());
    LL d = 0, res = 0;
    for (int i = 0; i < x.size(); i++)
    {
        res += (LL)i * x[i] - d;
        d += x[i];
    }
    return res;
}
int main()
{
    read(n), read(m);
    vector<int> ws;
    for (int i = 0; i < n * m; i++)
    {
        read(w[i]);
        ws.push_back(w[i]);
    }
    sort(ws.begin(), ws.end());
    int len = ws.erase(unique(ws.begin(), ws.end()), ws.end()) - ws.begin();
    for (int i = 0; i < n * m; i++)
    {
        w[i] = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin();
        c[w[i]].push_back(i / m);
        r[w[i]].push_back(i % m);
    }
    LL res = 0;
    for (int i = 0; i < len; i++)
        res += calc(c[i]) + calc(r[i]);
    write(res);
    return 0;
}

D. Integral Array

一个序列合法当且仅当对于任意序列中的两个数 x≥y ，⌊xy⌋ 也在序列中。考虑一个在序列中的数 y ，对 x∈[ky,ky+y) ，⌊xy⌋=k ，即如果 [ky,ky+y) 有序列中的数，一定必须存在 k 。这样对于每个数枚举 k ，时间复杂度为 O(n)+O(n2)+…+O(nn)=O(nln⁡n) 。可以通过。判断一段区间是否有一个数，可以在值域上做前缀和。

查看代码 
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, c, w[N], s[N];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> c;
        for (int i = 1; i <= n; i++)
            cin >> w[i], s[w[i]]++;
        for (int i = 1; i <= c; i++)
            s[i] += s[i - 1];
        bool flag = s[1] > 0;
        for (int i = 1; i <= c && flag; i++)
            for (int j = 1; s[i] > s[i - 1] && j * i <= c && flag; j++)
                (s[min(j * i + i - 1, c)] - s[j * i - 1]) && !(s[j] - s[j - 1]) && (flag = false);
        puts(flag ? "Yes" : "No");
        for (int i = 1; i <= c; i++)
            s[i] = 0;
    }
    return 0;
}

E. Tyler and Strings

类似数位 DP 的方式，对于每一位，考察选择小于当前的数和等于当前的数。

如果当前的位置选择小的数，那么后面的随便选。

在没有限制 i 为前，可能的答案有：
(n−i+1)!cnt1!cnt2!…cntm!
限制之后：
(n−i)!cnt1!cnt2!…(cntm−1)!
乘上了 cntmn−i+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
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, mod = 998244353;
int inv[N], fact[N], ifact[N];
int n, m, L, A[N], B[N], cnt[N << 1], tr[N << 1];
void add(int x, int k)
{
    for (; x <= L; x += x & -x)
        tr[x] += k;
}
int query(int x)
{
    int res = 0;
    for (; x; x -= x & -x)
        res += tr[x];
    return res;
}
void init()
{
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = -(LL)(mod / i) * inv[mod % i] % mod;
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        ifact[i] = (LL)ifact[i - 1] * inv[i] % mod;
    }
}
int main()
{
    read(n), read(m);
    init();
    vector<int> ws;
    for (int i = 1; i <= n; i++)
        read(A[i]), ws.push_back(A[i]);
    for (int i = 1; i <= m; i++)
        read(B[i]), ws.push_back(B[i]);
    sort(ws.begin(), ws.end());
    L = ws.erase(unique(ws.begin(), ws.end()), ws.end()) - ws.begin();
    for (int i = 1; i <= n; i++)
        A[i] = lower_bound(ws.begin(), ws.end(), A[i]) - ws.begin() + 1;
    for (int i = 1; i <= m; i++)
        B[i] = lower_bound(ws.begin(), ws.end(), B[i]) - ws.begin() + 1;
    int res = 0, cur = fact[n];
    for (int i = 1; i <= n; i++)
        cnt[A[i]]++;
    for (int i = 1; i <= L; i++)
        cur = (LL)cur * ifact[cnt[i]] % mod;
    for (int i = 1; i <= L; i++)
        add(i, cnt[i]);
    bool flag = true;
    for (int i = 1; i <= min(n, m); i++)
    {
        cur = (LL)cur * inv[n - i + 1] % mod;
        (res += (LL)query(B[i] - 1) * cur % mod) %= mod;
        if (!cnt[B[i]])
        {
            flag = false;
            break;
        }
        add(B[i], -1);
        cur = (LL)cur * (cnt[B[i]]--) % mod;
    }
    printf("%d", (res + (n < m && flag) + mod) % mod);
    return 0;
}
相关文章

Gitalk 加载中 ...