Codeforces Round 1013 (Div.3) 题解

发表于 更新于 分类于 阅读次数： 本文字数： 9k
呜呜呜感觉要加强英语阅读能力了。

A

题意

给定一个数组，从第一个数开始取，求取到第几个数才能凑成日期 “2025 03 01”。

题解

开个数组记录一下取的数量即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), cnt(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    if (n < 8) {
        cout << 0 << "\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++;
        if (cnt[0] >= 3 && cnt[1] >= 1 && cnt[2] >= 2 && cnt[3] >= 1 &&
            cnt[5] >= 1) {
            cout << i << "\n";
            return;
        }
    }
    cout << 0 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

每个人有权值，选人组队，每一队里要求最小值乘以人数大于等于 \(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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0, cnt = 0;
    for (int i = n; i >= 1; i--) {
        cnt++;
        if (cnt * a[i] >= x) {
            ans++;
            cnt = 0;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

生成一个排列 \(p\) ，要求对于 \(p\) 的所有循环左移中，都有恰好一个位置 \(i\) 满足 \(p_i = i\)。

题解

对于偶数经过小范围数据的枚举后可以发现不可能，奇数可以结合样例构造。

严格的证明不妨把排列的范围换成 \([0,...,n-1]\)，那么要求对于每个 \(k\in[0,n-1]\)，\(p_i\) 位移 \(k\) 次后，有 \((i + k) \pmod n \equiv p_i\)，则 \(k\equiv (p_i - i)\pmod n\)，要求对于每个 \(k\) 都存在这样的 \(i\)，那么两边求和有：\(\frac{n(n-1)}{2}\equiv \sum_{i=0}^{n-1}p_i - \sum_{i=0}^{n-1}i \equiv \frac{n(n-1)}{2} - \frac{n(n-1)}{2} \equiv 0 \pmod n\)，即 \(\frac{n(n-1)}{2} \equiv 0\pmod n\)，那么对于 \(n\) 为偶数是不可能的（设 \(n = 2m\) 验证）。对于奇数，按照样例即可构造。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    if (n % 2 == 0) {
        cout << -1 << "\n";
        return;
    }
    int p = 1;
    for (int i = 1; i <= n; i += 2) {
        cout << i << " ";
        p++;
    }
    int v = 2;
    for (int i = p; i <= n; i++) {
        cout << v << " \n"[i == n];
        v += 2;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

\(n\) 行，每行 \(m\) 个桌子，要把每行的桌子拼成长桌，求最长的长桌长度，满足选取的桌子大于等于 \(k\)。

题解

由于求出一个答案后，比它长的都能满足，考虑二分答案。最优的方案一定就是每一行构造类似，设长度为 \(x\)，那么就从开头选择 \(x\) 个桌子，然后空一格，继续选择，每一行能选的数量就是 \(\lfloor\frac{m}{x+1}\rfloor \times x + m \pmod {x+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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int lo = 1, hi = m;
    i64 ans = m;
    while (lo <= hi) {
        i64 mid = lo + (hi - lo) / 2;
        if (1ll * n * (m / (mid + 1) * mid + m % (mid + 1)) >= k) {
            ans = min(ans, mid);
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定范围 \([1,n]\)，寻找满足 \(\frac{\text{lcm}(a,b)}{\text{gcd(a,b)}}\) 为素数的对数 \((a,b)\)。

题解

由于 \(\text{lcm}(a,b) = \frac{ab}{\text{gcd}(a,b)}\)，那么也就是找满足 \(\frac{ab}{\text{gcd}^2(a,b)}\) 的素数，设 \(a = x\gcd(a,b), b = y\gcd(a,b)\)，那么 \(\frac{ab}{\text{gcd}^2(a,b)} = xy\)，也就是需要 \(xy\) 为素数，那么 \(x,y\) 其中一个一定是 \(1\)，另一个一定是素数。

我们枚举范围内每一个素数 \(y\)，那么它的倍数都是满足条件的（\(ky\) 其中的 \(k\) 看作 \(\text{gcd}\)）。这样的 \(k\) 的个数就是 \(\lfloor\frac{n}{y}\rfloor\)。

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;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

// minp(x) 可以找到 x 大于 1 的最小质因子
vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    sieve(n);
    i64 ans = 0;
    for (int i = 0; i < primes.size(); i++) {
        ans += n / primes[i];
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定一个地图，相邻格子长度为 1 ，不能走到障碍上，从最后一排走到第一排，每一排最多经过两个点，能行走的距离为臂长 \(d\)，初始可任意选择最后一排不为障碍的位置，求到达最后一排的方案数对 \(10^9 + 7\) 取模的结果。

题解

每一排最多走两个点，那么不妨设 \(dp_{i,j,0/1}\) 表示第 \(1/2\) 次到达 \((i,j)\) 的方案数，考虑状态转移。

\(dp_{i,j,0}\) 只能通过 \(dp_{i+1,y,0/1}\) 转移，要求 \(\sqrt{(j-y)^2 + 1} \le d\)，即 \(j - \sqrt{d^2-1} \le y \le j + \sqrt{d^2-1}\)，且 \(\sqrt{d^2-1} = d - 1\)。

即 \(dp_{i,j,0} = \sum_{y=j-d+1}^{j+d-1}dp_{i+1,j,0/1}\)，而 \(dp_{i,j,1} = \sum_{y=j-d}^{j+d}dp_{i,y,0}\)​， 不难想到维护每一行的前缀和帮助转移。

最后的答案就是第一行的 \(\sum_{j=1}^mdp_{1,j,0/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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) { Mod = Mod_; }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;  // 静态模数，题目给定模数
using D = MInt<0>;  // 动态模数，可以 D::setMod(x) 改变

void solve() {
    int n, m, d;
    cin >> n >> m >> d;
    int sqd = d - 1;
    vector<string> a(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = " " + a[i];
    }
    vector<vector<array<D, 2>>> dp(n + 2, vector<array<D, 2>>(m + 1));
    vector<D> sum0(m + 1), sum1(m + 1);
    for (int j = 1; j <= m; j++) {
        dp[n][j][0] = (a[n][j] == 'X');
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '#') {
                continue;
            }
            dp[i][j][0] =
                dp[i][j][0] - sum1[max(j - sqd - 1, 0)] + sum1[min(j + sqd, m)];

            dp[i][j][0] =
                dp[i][j][0] - sum0[max(j - sqd - 1, 0)] + sum0[min(j + sqd, m)];
        }
        sum0.assign(m + 1, 0);
        for (int j = 1; j <= m; j++) {
            sum0[j] = sum0[j - 1] + dp[i][j][0];
        }
        sum1.assign(m + 1, 0);
        for (int j = 1; j <= m; j++) {
            sum1[j] = sum1[j - 1];
            if (a[i][j] == '#') {
                continue;
            }
            dp[i][j][1] = dp[i][j][1] - sum0[max(0, j - d - 1)] +
                          sum0[min(m, j + d)] - dp[i][j][0];

            sum1[j] = sum1[j - 1] + dp[i][j][1];
        }
    }
    cout << sum0[m] + sum1[m] << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}