Codeforces Round #775 (Div. 2) ABCDE题解

A-Game

题目大意：
一条直线上有若干个点，每个点有两种情况：

• land 可以经过
• water 不能经过

每次只能移动一个距离，如果下一个是land，就可以到下一个land上，花费为0。
最多可以使用一次跳跃，从一个land_i跳到另一个land_j，花费为j-i+1。
起点为1，输入保证起点和终点都是land，问最小的花费为多少。

思路：
因为只能使用一个跳跃，因此找出左侧和右侧连续land的边界，然后从边界进行跳跃的花费是最小的。

AC代码：

#include 
const int N = 1e2 + 5;
using namespace std;

int loc[N];

void solve()
{
    int n, l, r;
    cin >> n;
    l = 1, r = n;
    for (int i = 1; i <= n; i++)
        cin >> loc[i];
    while (r >= 2)
    {
        if (loc[r - 1] == 1)
            r--;
        else
            break;
    }
    while (l < r)
    {
        if (loc[l + 1] == 1)
            l++;
        else
            break;
    }
    cout << r - l << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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

B-Game of Ball Passing

题目大意：
有若干个进行传球，每个人可以把球传给任何人，如果某个人不传球了，那么这一轮结束。
现在给出每个人传球的次数，求出轮次。

思路：
考虑人数只有两个的情况，如果两个人的传球次数相差为1且都不为0，那么就只需要一轮，传球方式为次数多的人先将球传给另一个人。
否则轮次为大-小。

有一个显然的结论： 如果将一个人分成传球次数之和相等的两个人，那么传球的轮次是不会增加的。

所以对于三个人的情况，假设三个人按照传球次数从小到大分别为x，y，z，如果|z-x-y| <=1，那么也只要一轮就能完成
否则分为两种情况：

• z>x+y，那么和两个人传球一样，轮次为z-x-y
• zy，所以总能找到一种传球方式，使得当z为0的时候，|y-x|<=1，那么还是只用1轮。

很容易就能将上述情况推广到n轮，假设最大的人为x，剩余的人之和为sum，结果为：

• sum+1>=x，只要1轮
• sum+1

AC代码：

#include 
const int N = 1e5 + 5;
using namespace std;

long long pass[N];

void solve()
{
    int n;
    long long sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> pass[i];
        sum += pass[i];
    }
    sort(pass + 1, pass + 1 + n);
    if (pass[n] == 0)
        cout << "0\n";
    else
    {
        sum -= pass[n];
        if (sum + 1 >= pass[n])
            cout << "1\n";
        else
            cout << pass[n] - sum << "\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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

C-Weird Sum

题目大意：
有一个矩阵，每个格子的坐标为其行和列，每个格子有一个颜色，颜色的编号最大为10⁵，对于相同颜色的格子，求出每一对格子的曼哈顿距离之和，最后输出所有颜色的总和。

思路：
因为是求曼哈顿距离，将同一个颜色的格子之间的行和行或列和列之间的坐标交换后是不影响结果的，所以可以直接分别求行和列的距离，用后缀和处理一下即可。

AC代码：

#include 
const int N = 1e5 + 5;
using namespace std;

vector<long long> vx[N], vy[N];
long long sum[N];

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m, c;
    long long ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> c;
            vx[c].push_back(i);
            vy[c].push_back(j);
        }
    }
    for (int i = 1; i < N; i++)
    {
        if (vx[i].size() == 0) continue;

        sort(vx[i].begin(), vx[i].end());
        sum[vx[i].size() - 1] = vx[i].back();
        for (int j = vx[i].size() - 2; j >= 1; j--)
            sum[j] = sum[j + 1] + vx[i][j];
        for (int j = 0; j < vx[i].size() - 1; j++)
            ans += sum[j + 1] - ((long long)vx[i].size() - j - 1) * vx[i][j];

        sort(vy[i].begin(), vy[i].end());
        sum[vy[i].size() - 1] = vy[i].back();
        for (int j = vy[i].size() - 2; j >= 1; j--)
            sum[j] = sum[j + 1] + vy[i][j];
        for (int j = 0; j < vy[i].size() - 1; j++)
            ans += sum[j + 1] - ((long long)vy[i].size() - j - 1) * vy[i][j];
    }
    cout << ans;
    return 0;
}
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

D-Integral Array

题目大意：
给定一个数列，数列中的每个数字都不大于c，c<=10⁶，问这个数列是否满足下列性质：对于数列中的任意两个数（也可以是同一个数）x和y，使得x/y下取整也在这个数列中。

思路：
复杂度分析，前缀和思想。
因为输入的数字范围不大，可以用vis数组直接记录每个数字是否出现，再对vis数组做一个前缀和，就可以知道一个区间内是否有数字出现。
首先1是肯定要有的，因为两个数字可以取相同。
之后就是枚举每个数字x的倍数ax，判断[a*x,(a+1)*x-1]区间内是否有数字出现过，如果有数字出现，那么这个数字除以x就会得到a，然后判断a是否出现过即可。
解法看似比较暴力，实际上复杂度是c/2+c/3+...+1，当c为10⁶时，也才四百多万而已，所以是完全可以接受的。

AC代码：

#include 
const int N = 1e6 + 5;
using namespace std;

int vis[N];

void solve()
{
    int n, c, cnt = 1;
    cin >> n >> c;
    for (int i = 0; i <= c; i++)
        vis[i] = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        vis[x] = 1;
    }
    for (int i = 1; i <= c; i++)
        vis[i] += vis[i - 1];
    if (!vis[1])
    {
        cout << "No\n";
        return;
    }
    for (int i = 2; i <= c; i++)
    {
        if (vis[i] - vis[i - 1] == 0) continue;
        int x = i + i;
        for (int j = 2; x <= c; j++, x += i)
        {
            if (vis[min(c + 1, x + i) - 1] - vis[x - 1])
            {
                if (vis[j] - vis[j - 1] == 0)
                {
                    cout << "No\n";
                    return;
                }
            }
        }
    }
    cout << "Yes\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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

E-Tyler and Strings

题目大意：
给定一个序列s和序列t，长度分别为n和m，问s经过重排后字典序小于t的方案数。

思路：
为了避免重复，可以根据两个序列左侧公共部分长度进行情况的划分。
假设当前的位置是i，[1,i-1]这一段中s和t相同，如果可以令s[i] < t[i]，那么当前的方案数就是：[i, n]进行排列组合的数量 * s[i]能放的数字个数 / (n-i+1)。
当统计完位置i之后，令s[i] = t[i]，然后继续统计下一个位置，这样可以保证不会重复，如果s[i] = t[i]的条件无法满足，那么就结束统计。
用树状数组来维护s序列数字出现的次数即可快速得到s[i]能放的数字个数。
进行下一个区间统计时，因为s[i]的数字确定了，可以根据当前的组合数O(1)更新得到下一个区间的组合数。

AC代码：

#include 
const int N = 2e5;
const int mod = 998244353;
using namespace std;

long long ksm(long long base, long long power, long long mod)
{
    long long result = 1;
    base %= mod;
    while (power)
    {
        if (power & 1)
            result = (result * base) % mod;
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int A[N + 1], C[N + 1]; // A[i]统计i出现的次数

inline int lowbit(int x) { return x & (-x); }

void update(int x, int val)
{
    A[x] += val;
    while (x <= N)
    {
        C[x] += val;
        x += lowbit(x);
    }
}
int query(int x) //查询小于等于x的个数
{
    int res = 0;
    while (x > 0)
    {
        res += C[x];
        x -= lowbit(x);
    }
    return res;
}

long long fac[N + 1], facinv[N + 1], inv[N];
void getinv(int n) // O(n)算逆元
{
    fac[0] = facinv[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod;
    facinv[n] = ksm(fac[n], mod - 2, mod);
    for (int i = n - 1; i >= 1; i--)
        facinv[i] = facinv[i + 1] * (i + 1) % mod;
    inv[1] = 1;
    for (long long i = 2; i <= N; i++)
    {
        inv[i] = -(mod / i) * inv[mod % i];
        inv[i] = (inv[i] % mod + mod) % mod;
    }
}

int n, m, s[N + 1], t[N + 1];

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    getinv(N);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        update(s[i], 1);
    }
    for (int i = 1; i <= m; i++)
        cin >> t[i];
    long long ans = 0, x = fac[n];
    for (int i = 1; i <= N; i++)
        if (A[i] > 1) x = x * facinv[A[i]] % mod;
    for (int i = 1; i <= min(n, m); i++)
    {
        long long fz = query(t[i] - 1), fm = n - i + 1; // fz:可以放在s[i]的数字个数,fm:当前区间总共的数字个数
        ans += x * fz % mod * inv[fm] % mod;
        if (A[t[i]] == 0) break; //无法满足条件，结束统计
        //因为s[i]的数字确定了，可以O(1)更新得到下一个区间的组合数
        x = x * inv[fm] % mod * A[t[i]] % mod;
        update(t[i], -1);
    }
    if (n < m && query(N) == 0) ans++;
    cout << ans % mod;
    return 0;
}
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
90