Codeforces Round 919 (Div. 2) A~E_summation game

A. Satisfying Constraints(模拟)

题意：

给出$n$个限制条件，问有多少个数字$k$同时满足这些限制条件。

限制条件分为以下三种：

1. $k$必须大于等于给出的一些数字$x$

2. $k$必须小于等于给出的一些数字$x$

3. $k$不能与给出的数字$x$相同

分析：

对于限制条件1, 2，可以使用两个变量维护数字$k$的取值区间。

对于限制条件3，可以采用容器(set, map等)存储这些不能取到的数字。

根据限制条件1，2得到的区间，再遍历容器检查区间内有多少数字不能被取到，剩下的数字个数就是答案。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

set<int> s;

void solve() {
    int n;
    cin >> n;
    int l = -1e9, r = 1e9;
    s.clear();
    for (int i = 0; i < n; i++) {
        int a, x;
        cin >> a >> x;
        if (a == 1) {
            l = max(l, x);
        } else if (a == 2) {
            r = min(r, x);
        } else {
            s.insert(x);
        }
    }
    int ans = r - l + 1;
    for (auto i : s) {
        if (i >= l && i <= r) ans--;
    }
    cout << max(0, ans) << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        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. Summation Game(枚举)

题意：

有一个包含$n$个数字的序列$A=a_1,a_2,...,a_n$，Alice和Bob将会执行以下操作：

• 首先，Alice将会移除序列中至多$k$个数字。

• 然后，Bob将会选择剩余的序列中至多$x$个数字并让这些数字乘上$-1$。

Alice想让剩下的数字之和尽可能大，但Bob想让剩下的数字之和尽可能小，假设两人均采取最优策略，那么剩下的数字之和会是多少？

分析：

实际上，Bob会做的事情是固定的，即选择剩余的数组中最大的$x$个数字进行操作。

既然Bob的操作固定了，那就可以思考Alice的操作了，由于Alice想要结果尽可能大，那么Alice的操作就是删除部分最大的数字，由于不知道删除多少个是最优的，因此需要对删除的数字个数进行枚举，记录最大的结果。

对删除后剩余的数字总和进行计算可以先对数组进行排序，并维护前缀和，使用前缀和来计算结果。

hint: 删除元素后剩余的数字不足$x$个时，计算区间和时需避免出现下标越界。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 5e2;
int a[N], pre[N];

void solve() {
    int n, k, x;
    cin >> n >> k >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    int ans = -1e9;
    for (int i = 0; i <= k; i++) {
        int m = n - i;
        int sum;
        /*小心下标越界*/
        if (m > x) sum = pre[m - x] - (pre[m] - pre[m - x]);
        else sum = -pre[m];
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        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. Partitioning the Array(数学)

题意：

给出一个包含$n$个数字的数组$A=a_1,a_2,...,a_n$，你可以选择一个数字$k$，并对数字进行以下操作：

• 将数组均分为$\frac{n}{k}$个子数组，子数组形如：$$[a_1,a_2,...,a_k],[a_{k+1},a_{k+2},...,a_{2k}],...,[a_{n-k+1},a_{n-k+2},...,a_n]$$

• 如果可以选择一个数字$m$，让数组中所有元素对$m$取余数，且计算后得到的各个子数组均是相同的，那么就可以获得一点积分。

问：最多可以获得多少积分（一个数字$k$最多产生一点积分）。

分析：

首先思考$k$的选择，不难发现只有$k$为$n$的因子时各个子数组的长度才是相等的，因此只需要考虑$n$的所有因子作为$k$的选择。

当只有两个数字$x,y$时，那么只要这两个数之间差的绝对值取模$m$的结果为0，那么这两个数字对于$m$取模的结果必然是相同的。

将结论推广至全部数组中的内容，为了尽可能使得到的$m$更大，令$m$即为所有子数组中对位元素的差的绝对值之间的最大公约数。

为了便于计算，每次计算只考虑相邻子数组中的元素进行对位计算，即计算：

$$m=gcd(|a_1-a_{1+k}|,|a_2-a_{2+k}|,...,|a_{n-k+1}-a_n|)$$

由于题目要求的$m\ge 2$，那么只要得到的结果不为1，那么就表示当前存在合法的$m$能获得积分。

Tips: 当数组中对位元素之差均为0时，即各子数组中相同位置的元素均相等，此时得到的最大公约数为$0$，但此时任选一个$m$均为合法的解，因此也可以获得积分。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 5e2;
int a[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int k = 1; k <= n; k++) {
        if (n % k == 0) {
            int m = 0;
            for (int j = 1; j + k <= n; j++) {
                m = __gcd(m, abs(a[j + k] - a[j]));
            }
            if (m != 1) ans++;//m>=2 || m == 0
        }
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        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

D.Array Repetition(模拟)

题意：

开始时有一个空的数组$a$，将对这个数组进行$n$次操作，每次操作为以下两种操作之一：

1. 选择一个数字$x$，将这个数字添加到数组$a$的末尾。

2. 将数组$a$的内容复制$x$遍放在数组$a$的后面。

结束操作后，会给出$q$个询问，每个询问需要你回答数组中第$k$个元素是多少。

分析：

虽然操作$2$会使数组中数字总数增加的非常快，但是由于题目的询问最多只会到$10^{18}$，因此，当数组中总数超过$10^{18}$时，就不需要再进行操作了。

可以使用结构体记录下每次操作后数组中的数字总数$sum$以及操作$1$添加进来的数字个数$cnt$。如果是操作$2$，还需要记录下操作$2$的复制次数$mul$。

对于操作$1$，还需将添加的数字记录到另一个数组$a$中。

然后对于每次查询，均可通过递归的方式从记录的操作信息回推到某一条操作$1$对应的数字：

• 如果当前查询的第$k$个元素与当前结构体记录的总数字个数$sum$相等，那么此时的答案就是数组$a$中第$cnt$个数字。

• 如果不相等，说明需将本轮的复制操作消除，继续递归查找，将复制消除后，需将$k$也修改为$kmod\frac{sum}{mul}$，而且需要注意，如果余数为$0$，需要将$k$修改为$\frac{sum}{mul}$，计算得到$k$后继续递归查询。

对于每次递归查询，遇到操作$1$就会返回结果，遇到操作$2$就会移除复制操作后递归查询，查询时间复杂度为对数级别。

坑点：

虽然我们手动设置数字上限为$10^{18}$，但如果使用long long类型存储，依然不能保证运算中不会发生溢出，因此需要使用__int128来进行存储。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 5e2;
struct Node{
    __int128 sum;//数字总数
    int cnt, mul;//操作1的次数，mul为如果当前操作为操作2，那么记录复制的次数
    bool operator < (const Node &o) const {
        if (sum != o.sum) return sum < o.sum;
        return cnt < o.cnt;
    }
};

int n, q;

vector<int> a;//数字表
vector<Node> num;//信息表

int search(ll k) {查询第k个数字
    //在信息表里查
    int id = lower_bound(num.begin(), num.end(), Node{k, 0}) - num.begin();
    //当前查询的k与信息表的数字总数相等，那么此时就是对应信息表中记录的最后一次操作1插入的数字
    if (num[id].sum == k) {
        return a[num[id].cnt - 1];
    }
    k %= num[id].sum / num[id].mul;//否则计算在当前的操作2前第k个数字对应的数字是第几个
    if (k == 0) k = num[id].sum / num[id].mul;
    return search(k);//递归查询
}

void solve() {
    a.clear();
    num.clear();
    cin >> n >> q;
    __int128 sum = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        ll b, x;
        cin >> b >> x;
        int mul = 0;
        if (sum <= 1e18) {//只有数字总数小于等于10的18次方才记录操作信息
            if (b == 1) {
                cnt++;
                sum++;
                a.push_back(x);
            } else {
                mul = x + 1;
                sum *= mul;//如果是long long类型，这里就可以发生溢出
            }
            num.push_back(Node{sum, cnt, mul});
        }
    }
    while (q--) {
        ll k;
        cin >> k;
        cout << search(k) << ' ';
    }
    cout << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

E. Counting Binary Strings（排列组合、dp）

题意：

对于一个只含有$0$和$1$的字符串$s$，如果它的子串$\hat{s}$只含有$1$个$1$，我们就称他为好子串。

现在我们希望知道，有多少个字符串$s$满足以下要求：

• $s$有且仅有$n$个好子串；
• $s$的好子串的长度均不超过$k$。

答案可能很大，需要对$998244353$取模。另外，在考虑子串时，我们需要考虑位置。比如说，1010中，我们认为有$2$个子串$10$，因为他们的位置是不同的。

思路

对于由若干个$1$和$0$组成的字符串$s$，我们可以认为：每一个$1$都可以和它之前、之后的$0$进行组合，形成好字符串。比如：0010，对于这个$1$，它可以分别向前、向后与若干个$0$进行组合（当然也可以不向前选择、或者不想后选择）。在这个例子中，若我们不考虑$k$的限制，含有中间的$1$的子串有$3\times 2=6$个。类似的，00100010中含有$3\times 4+4\times 2=20$个好子串。在这个过程中，我们重点关注的是1左右两边$0$的个数（此处在计算过程中我们进行了$+1$操作）。

对于一个给定的字符串$s$，我们可以把这些$0$的个数$+1$以后的结果记作数组$a_1,a_2,\dots ,a_n$的内容，则$s$中好子串的个数为$a_1{a}_2+a_2{a}_3+\cdots +a_{n-1}{a}_n$。此时若我们多加入一个$a_{n+1}$，就是在原来结果的基础上加上$a_n{a}_{n+1}$。换言之，假设我们用$dp[sum]$数组中的元素来表示好子串个数为$sum$的子串数，即$sum={\sum }_{i=1}^{n+1}{a}_n$，那么我们可以发现：$dp[sum]$与$dp[sum-a_n\cdot a_{n-1}]$有关。

但是，并不是只有$a_n$结尾的方案才能得到和为$sum$的结果，我们需要给$dp$数组加上一个维度作为限制。此处，我们以$dp[sum][last]$表示：和为$sum$，最后一个元素（即我们前面讨论的$a_{n+1}$）为$last$的方案数，那么我们有：

d p [ s u m ] [ l a s t ] = ∑ i d p [ s u m − i ⋅ l a s t ] [ i ]

$$\begin{aligned} dp[sum][last]=\sum_{i}dp[sum-i\cdot last][i] \end{aligned}$$ dp[sum][last]=i∑​dp[sum−i⋅last][i]​

其中，$i$的枚举范围要考虑到：

• $i\cdot last\le sum$，避免出现负数下标；
• $i+last-1\le k$，这一举动是为了保证加入以后，长度不超过$k$；
  • 如果你不理解为什么要$-1$，请你回想：我们在上面的计算过程中进行了$+1$操作，当你要对$a$数组加入元素$last$时，实际上你是多加了好几个$0$，$i$与$last$的数值如果代表长度，会包含同一个$1$，计算长度时，我们要避免重复计算这个$1$的长度，所以根据容斥原理进行$-1$操作。

初始化$dp$数组时，可以令满足$1\le last\le k$的$dp[0][last]$均为$1$，即对应全$0$字符串。

hint: 清空$dp$数组需要使用循环来清空避免超时。

代码：

#include<bits/stdc++.h>

using namespace std;
int n, k, dp[3000][3000];
const int mod = 998244353;

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) dp[i][j] = 0;
    int ans = 0;
    //对全0字符串进行初始化操作
    for (int last = 1; last <= k; last++) {
        dp[0][last] = 1;
    }
    //根据dp方程进行计算，注意i的范围，不要忘记取模
    for (int sum = 1; sum <= n; sum++) {
        for (int last = 1; last <= k; last++) {
            for (int i = 1; i * last <= sum && i + last - 1 <= k; i++) {
                dp[sum][last] = (dp[sum][last] + dp[sum - i * last][i]) % mod;
            }
        }
    }
    //统计满足要求的好子串个数，不要忘记取模
    for (int last = 1; last <= k; last++) {
        ans = (ans + dp[n][last]) % mod;
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        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

学习交流

以下为学习交流QQ群，群号： 546235402，每周题解完成后都会转发到群中，大家可以加群一起交流做题思路，分享做题技巧，欢迎大家的加入。