Codeforces Round 717 Div2

发表于2021-04-30更新于2023-09-15字数统计2.3k阅读时长22分

比赛链接

A - Tit for Tat

Description

题目链接

Solution

显然只需要尽可能把前面的数减小，把多出来的部分移到最后。

Code

Tit for Tat
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 105;
const int MOD = 1E9 + 7;
int n, k, a[MAXN];

void solve(int caseNum) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (k == 0) break;
        if (a[i] > 0) {
            int tmp = min(k, a[i]);
            a[i] -= tmp;
            k -= tmp;
            a[n] += tmp;
        }
    }
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    cout << endl;
}

signed main() {
    int testCase = 1;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> testCase;
    for (int i = 1; i <= testCase; i++) solve(i);
    return 0;
}

B - AGAGA XOOORRR

Description

题目链接

Solution

如果能通过操作使剩下的数相同，记为 xx，那么原来所有数异或起来要么为 00，要么为 xx。如果异或起来为 0，那么直接输出 YES；否则，由于题目中的操作是对相邻的数进行的，所以从左到右按异或和为 xx 分段，最后判断分出的段数是不是奇数即可。

Code

AGAGA XOOORRR
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>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E3 + 5;
const int MOD = 1E9 + 7;
int n, k, a[MAXN], pre[MAXN];

void solve(int caseNum) {
    cin >> n;
    int tmp = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], tmp ^= a[i];
    bool tag = 1;
    if (tmp == 0) {
        cout << "YES" << endl;
    } else {
        int tot = 0, q = 0;
        for (int i = 1; i <= n; i++) {
            q ^= a[i];
            if (q == tmp) tot++, q = 0;
        }
        if (tot > 1 && tot % 2)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

signed main() {
    int testCase = 1;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> testCase;
    for (int i = 1; i <= testCase; i++) solve(i);
    return 0;
}

C - Baby Ehab Partitions Again

Description

题目链接

Solution

首先用背包判断能否选择一些数，使它们的和恰好是总和的一半。如果不能的话，答案为 0；否则只需要删除一个数就能满足题目条件，具体如下：

由于此时数列的和一定为偶数，若存在一个数是奇数，删掉这个数即可；否则，该数列每一个数都是偶数，那么对原数列的划分等价于将原数列每一个数都除 2 后的划分。我们只需要不断将每个元素除以 2，直到第一次出现奇数为止，之后随便删掉一个奇数即可。

Code

Baby Ehab Partitions Again
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, a[101], sum;
bool dp[101][MAXN];

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= sum; j++) {
            dp[i][j] |= dp[i - 1][j];
            if (j >= a[i]) dp[i][j] |= dp[i - 1][j - a[i]];
        }
    if (sum % 2 || !dp[n][sum / 2])
        return cout << 0, 0;
    else {
        cout << 1 << endl;
        for (int k = 0; k <= 11; k++)
            for (int i = 1; i <= n; i++)
                if ((a[i] >> k) & 1) return cout << i, 0;
    }
    return 0;
}

D - Cut

Description

题目链接

Solution

nn 个数乘积为它们的 LCM 当且仅当它们两两互质(即每个质因子最多在所有数中出现一次)。一种分段的方法是，从 i=1i=1 开始向右扩展，沿途记录各个质因子出现的次数。如果对于第 ii 个数，它的某个质因子在前面出现至少一次，那么必须以 ii 为起始扩展新的一段。可以证明该策略是最优的。

首先考虑求以 ii 为起始向右扩展后下一段的起始位置，记为 nxtinxt_i。我们从 nn 到 11 依次求 nxtinxt_{i}。假设 nxti+1nxt_{i+1} 已求出，显然有 nxti≤nxti+1nxt_{i} \le nxt_{i+1}。遍历 aia_i 的每一个质因子，将 nxtinxt_{i} 对所有质因子最后出现位置的最小值取 minmin 即可。

接下来考虑如何处理区间查询。对于区间 [l,r][l,r], 我们从 i=li=l 开始按 nxtinxt_i 向后跳，直到越过右端点为止，此时跳的次数即为答案。直接一次一次往后跳比较低效，我们可以用倍增优化。

Code

Cut
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

template <class T>
void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

const int MAXN = 1E5 + 5;
const int MOD = 1E9 + 7;
int n, m, a[MAXN], last[MAXN], nxt[MAXN];
int to[MAXN][20];

signed main() {
    read(n, m);
    for (int i = 1; i <= n; i++) read(a[i]);

    for (int i = 1; i <= n + 1; i++) nxt[i] = n + 1;
    for (int i = 1; i <= 1E5; i++) last[i] = n + 1;
    for (int i = n; i >= 1; i--) {
        nxt[i] = min(nxt[i], nxt[i + 1]);
        int tmp = a[i];
        for (int j = 2; j <= sqrt(tmp); j++) {
            if (tmp % j == 0) nxt[i] = min(nxt[i], last[j]), last[j] = i;
            while (tmp % j == 0) tmp /= j;
        }
        if (tmp != 1) nxt[i] = min(nxt[i], last[tmp]), last[tmp] = i;
    }

    for (int i = 1; i <= n + 1; i++) to[i][0] = nxt[i];
    for (int j = 1; j <= 19; j++)
        for (int i = 1; i <= n + 1; i++) to[i][j] = to[to[i][j - 1]][j - 1];

    for (int i = 1; i <= m; i++) {
        int l, r;
        read(l, r);
        int cnt = 0;
        for (int j = 19; ~j; j--) {
            if (to[l][j] <= r) {
                l = to[l][j];
                cnt += (1 << j);
            }
        }
        printf("%d\n", cnt + 1);
    }
    return 0;
}

E - Baby Ehab Plays with Permutations

Description

题目链接

Solution

设 dp[i][j]dp[i][j] 表示长度为 ii，最少需要 jj 次交换能变为 11 ~ ii 的全排列的序列数。对于第 ii 个数，如果它等于 ii，那么不需要对这个数进行交换操作，于是 dp[i][j]←dp[i−1][j]dp[i][j] \leftarrow dp[i-1][j]；否则，这个数原本的位置可能在 11 ~ i−1{i-1}，此时有 dp[i][j]←dp[i−1][j−1]∗(i−1)dp[i][j] \leftarrow dp[i-1][j-1]*(i-1)。设 f[i][j]f[i][j] 表示长度为 ii，需要恰好 jj 次交换能变为 11 ~ ii 的全排列的序列数，那么 f[i][j]=dp[i][j]+dp[i][j−2]+dp[i][j−4]+...f[i][j] = dp[i][j]+dp[i][j-2]+dp[i][j-4]+...。

由于题目中交换次数最多 kk 次，因此最多有 2k2k 个数位置发生变化。设位置变化的数的个数为 ii，简单想一想答案应该为 ∑i=0min(n,2k)(ni)f[i][k]\sum \limits_{i=0}^{min(n,2k)} \binom{n}{i}f[i][k]。实际上，这样计算会有重复，因为根据前面的定义， g[i][j]g[i][j] 没有保证交换后每个数不在它原来的位置。解决方法很简单，我们只需要对每个 g[i][j]g[i][j] 容斥一下，再用容斥后的结果重新计算即可。

时间复杂度 O(n3)O(n^3)。（代码中的做法是 O(n4)O(n^4)的，把 Comb2 预处理下就是 O(n3)O(n^3) 的了)

Code

Baby Ehab Plays with Permutations
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long
using namespace std;

const int MAXN = 205;
const int MOD = 1E9 + 7;
int n, k;
int dp[MAXN * 2][MAXN];  
int g[MAXN * 2][MAXN];  
int fac[MAXN * 2], inv[MAXN * 2];

int qpow(int a, int b, int MOD) {
    int ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

int Comb1(int n, int m) { return fac[n] * inv[m] % MOD * inv[n - m] % MOD; }

int Comb2(int n, int m) {
    int num = 1, den = 1;
    for (int i = n - m + 1; i <= n; i++) num = num * i % MOD;
    for (int i = 1; i <= m; i++) den = den * i % MOD;
    return num * qpow(den, MOD - 2, MOD) % MOD;
}

void init(int k) {
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= k; i++)
        fac[i] = fac[i - 1] * i % MOD, inv[i] = qpow(fac[i], MOD - 2, MOD);
}

signed main() {
    cin >> n >> k;
    init(2 * k);
    for (int i = 0; i <= min(n, 2 * k); i++) dp[i][0] = 1;
    for (int i = 1; i <= min(n, 2 * k); i++)
        for (int j = 1; j <= k; j++)
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * (i - 1) % MOD) % MOD;

    for (int i = 0; i <= min(n, 2 * k); i++)
        for (int j = 0; j <= k; j++)
            for (int f = 0; f <= i; f++) {
                g[i][j] += Comb1(i, f) * dp[i - f][j] * (f % 2 ? -1 : 1) % MOD;
                g[i][j] %= MOD;
            }

    for (int x = 1; x <= k; x++) {
        int ans = 0;
        for (int i = 0; i <= min(n, 2 * x); i++)
            for (int f = x; f >= 0; f -= 2) {
                ans += Comb2(n, i) * g[i][f] % MOD;
                ans %= MOD;
            }
        cout << (ans + MOD) % MOD << ' ';
    }
    return 0;
}