Codeforces Round 919 (Div. 2)题解（A-E）

https://codeforces.com/contest/1920

A Satisfying Constraints

链接：A - Satisfying Constraints

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--){
        int n;
        scanf("%d", &n);
        vector<int> eq;
        int a1 = 1, a2 = 1e9 + 2;
        for(int i = 1; i <= n; i++){
            int x, y;
            scanf("%d%d", &x, &y);
            
            if(x == 1){
                a1 = max(a1, y);
            }
            else if(x == 2){
                a2 = min(a2, y);
            }
            else{
                eq.push_back(y);
            }
        }
        if(a2 < a1) puts("0");
        else{
            int sub = 0;
            for(int x : eq){
                if(x >= a1 && x <= a2){
                    sub++;
                }
            }
            printf("%d\n", a2 - a1 + 1 - sub);
        }
    }

    return 0;
}

B Summation Game

链接：B - Summation Game

代码

#include <bits/stdc++.h>
using namespace std;
int n, k, x;
const int N = 3e5 + 2;
int a[N], s[N];
int main()
{   
    int T;
    cin >> T;
    while (T--)
    {
        int ans = -0x3f3f3f3f;
        scanf("%d%d%d", &n, &k, &x);
        for(int i = 1; i <= n; i++){
            scanf("%d", a + i);
        }
        sort(a + 1, a + 1 + n);
        s[0] = 0;
        for(int i = 1; i <= n; i++){
            s[i] = s[i - 1] + a[i];
        }
        for(int i = 0; i <= min(n, k); i++){
            int r = n - i;
            if(r <= 0) {
                ans = max(ans, 0);
            }
            else{
                int m = r - x;
                m = max(0, m);
                int tmp = s[m] - (s[r] - s[m]);
                ans = max(ans, tmp);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C Partitioning the Array

链接：C - Partitioning the Array

题意

艾伦有一个数组 a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 。对于每个是 n𝑛 除数的正整数 k𝑘 ，艾伦都会做如下运算：

他将数组分割成长度为 k𝑘 的 nk𝑛𝑘 个互不相交的子数组。换句话说，他将数组划分为以下子数组：
[a1,a2,…,ak],[ak+1,ak+2,…,a2k],…,[an−k+1,an−k+2,…,an]
如果存在某个正整数 𝑚 ( 𝑚≥2 )，使得他将数组中的每个元素除以 𝑚 后的余数都替换为该元素，则所有子数组都相同，则艾伦得一分。

帮助艾伦找出他将获得的分数。

思路

对于两个数字： $x$ 和 $y$ ，设其在模m的情况下相等，那么会有 $\bmod m \equiv y \bmod m$ ，即有 $\equiv 0 \pmod m$ 。

当且仅当m为 $x - y$ 的因数的时候，在模m意义下，两个数字相等。

由于每组的对应元素在模 $m$ 意义下都相等，所以 m 应该为每一组元素两两之间的gcd

补充：当一个参数为零时，最大公约数（Greatest Common Divisor，gcd）定义为另一个参数的绝对值。因此，当一个参数为零时，gcd(0, x)等于x的绝对值。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
const int N = 2e5 + 30;
int a[N];
int solve(int d)
{
    int g = 0;
    for(int i = 1; i <= n - d; i++){
        g = __gcd(g, abs(a[i] - a[i + d]));
    }
    //如果为0，那么表示d为n的情况
    return g != 1;
}
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int ans = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", a + i);
        for(int i = 1; (ll)i*(ll)i <= (ll)n; i++){
            if(n % i == 0){
                if(i * i == n){
                    ans += solve(i);
                }
                else{
                    ans += solve(i);
                    ans += solve(n / i);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D Array Repetition

链接：D - Array Repetition

思路

依次记录每一次操作之后的数组总长度。

在给定需要求得的位置时，确定其是在那一次操作引入的：

若为add操作，那么直接得出值
若为复制操作，那么递归求取该位置在复制前位置上的值

由于复制操作会使得位置坐标至少减少一半，所以在时间复杂度足够优秀。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5;
int n, q;
vector<__int128> qu;
int val[N];
int mul[N];
int solve(int x){
    while(x >= 0){
        int idx = lower_bound(qu.begin(), qu.end(), x) - qu.begin();
        if(val[idx] != -1){
            return val[idx];
        }
        else{
            x = (x - 1) % (qu[idx] / mul[idx]) + 1;
        }
    }
}


signed main()
{
    int T;
    cin >> T;
    while(T--){
        qu.clear();
        __int128 len = 0;
        bool valid = true;
        scanf("%lld%lld", &n, &q);
        for(int i = 0; i < n; i++){
            int x, y;
            scanf("%lld%lld", &x, &y);
            if(x == 1){
                len++;
                val[i] = y;
            }
            else{
                len *= (y + 1);
                val[i] = -1;
                mul[i] = (y+1);
            }
            if(valid)//!!!!!!!!!!!
                qu.push_back(len);
            if(len > (__int128)1e18){
                valid = false;
            }
        }
        for(int _ = 1; _ <= q; _++){
            int x;
            scanf("%lld", &x);
            printf("%lld ", solve(x));
        }
        puts("");
    }

    return 0;
}

E Counting Binary Strings

链接：E- Counting Binary Strings

题意

如果二进制字符串 $^\ddagger$ 的子串 $^\dagger$ 恰好包含一个 1，Patrick 就称该子串为好字符串。

帮助帕特里克计算二进制字符串 $s$ 的个数，使得 $s$ 包含恰好 $n$ 个好子串，并且没有长度严格大于 $k$ 的好子串。注意，子串是根据它们在字符串中的位置来区分的，因此如果 $s =$ 1010 时，应同时计算 10 的出现次数。

$^\dagger$ 如果从 $b$ 中删除开头的几个(可能是零个或全部)字符和结尾的几个(可能是零个或全部)字符就可以得到 $a$ ，那么字符串 $a$ 就是字符串 $b$ 的子串。

$^\ddagger$ 二进制字符串是指只包含 0 和 1 字符的字符串。

思路

模型转化

进行演算：
$\underbrace{00001}_{a_1} \! \! \! \, \underbrace{ \; \, \! 0001}_{a_2} \! \! \! \, \underbrace{ \; \, \! 00000001}_{a_3} \! \! \! \, \underbrace{ \; \, \! 0001}_{a_4} \! \! \! \, \underbrace{ \; \, \! 000}_{a_5}$

在这个例子中，好子串的数目是 $a_1 a_2 + a_2 a_3 + a_3 a_4 + a_4 a_5$ 。我们可以为任何字符串 $s$ 创建这样的数组，而 $s$ 的好子串数就是数组中相邻元素的乘积之和。

我的理解：

对于每一个1，我们要计算其的贡献。

不妨假设左边有n个连续的零，右边有m个连续的零，其所产生的好串的数目为 $\cdot(m + 1)$ 。

对于第一个1，其 m+1 与第二个1的 n+1 是相同的，均为4。所以，可以进行转化为一个数组的相邻项的乘积相加。

进行DP

状态为 $dp_{i,j} = \text{number of arrays with sum i and last element j}$

得到初步的转移等式： $dp_{i, j} = \sum_{p=1}^{k-j+1}{dp_{i - j \cdot p,p}}$

k-j+1是为了限制并且没有长度严格大于 $k$ 的好子串

但是其时间复杂度不够优秀。可以进行一个优化，即求和的过程中，p最多到达 $\lfloor \frac{i（总和）}{j（数组中当前的最后一个元素）} \rfloor$ ，若超过这个值，仅仅 $\cdot j$ 便超过了i，显然没有意义。

如此优化之后，结合常识：
$\frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} = O(n\log n)$
便可以使得时间复杂度合格, $O(n^2 \log_2n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3000;
int dp[N][N];
const int mod = 998244353;
int n, k;
void cleanse(){
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            dp[i][j] = 0;
        }
    }
    for(int i = 0; i <= n; i++){// 更确切为 1 到 k
        dp[0][i] = 1;
    }
}
int main()
{
    int T;
    cin >> T;
    while(T --){
        scanf("%d%d", &n, &k);
        cleanse();
        for(int sum = 1; sum <= n; sum++){
            for(int cur = 1; cur <= k; cur++){
                for(int j = 1; j <= (sum / cur) && j + cur - 1 <= k; j++){
                    dp[sum][cur] = ((long long)dp[sum][cur] + dp[sum - j * cur][j])%mod;
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= k; i++){
            ans = (ans + dp[n][i]) % mod;
        }
        printf("%d\n", ans);
    }
    return 0;
}