526互联

Codeforces Edu 154 (A-E)

发布时间 2023-12-08 07:48:23作者: Imcaigou

Codeforces Edu154 (Rated for Div2) (A-E)

A.Prime Deletion

可以发现只要存在一个两位数（两位不相同），其正着看和反着看都是质数，则原问题有解。这时我们可以把除了这两位上的数之外的其他数从 \(s\) 中剔除，就有答案。上述两位数不少，如：13,17,...

#include <bits/stdc++.h>
using namespace std;
int T, pos3, pos1;
char s[15];
int main (){
    scanf ("%d", &T);
    while (T --){
        scanf ("\n%s", s + 1);
        for (int i = 1;i <= 9;++ i)
            if (s[i] == '1')
                pos1 = i;
            else
            if (s[i] == '3')
                pos3 = i;
        if (pos1 < pos3)
            printf ("13\n");
        else
            printf ("31\n");
    }
    return 0;
}

B.Two Binary Strings

从左往右观察，我们可以尝试分类讨论。

若 \(a_i=b_i=1\)，且 \(i\) 的左边有需要赋值的，那么说明 \(a_i\) 和 \(b_i\) 帮不上忙，因为根据下面三种对策 \(i\) 的左边若有需要赋值的，则一定不能通过 \(1...1\) 的赋值完全消除不相等的数，因为根据第二种情况 \(a_j=b_j=1,j<i\) 的时候 \(j\) 前面一定有需要赋值的；

若 \(a_i=b_i=1\)，且 \(i\) 的左边无需要赋值的，那么可以直接赋值 \([i,n]\) 的所有数为 \(1\)，结束扫描；

若 \(a_i=b_i=0\)，且 \(i\) 的左边有需要赋值的，那么可以直接赋值 \([1,i]\) 的所有数为 \(0\)，此时 \(i+1\) 的左边无需要赋值的；

若 \(a_i=b_i=0\)，且 \(i\) 的左边无需要赋值的，那么 \(a_i,b_i\) 和 \(a_1,b_1\) 的效果一样，跳过。

最后判断是否全局相等。

#include <bits/stdc++.h>
using namespace std;
int T, n;
char s[5005], t[5005];
int main (){
    scanf ("%d", &T);
    while (T --){
        scanf ("\n%s\n%s", s + 1, t + 1);
        n = strlen (s + 1);
        bool tag = false;
        for (int i = 2;i < n;++ i){
            if (s[i] != t[i])
                tag = true;
            if (s[i] == t[i]){
                if (s[i] == '0')
                    tag = false;
                if (s[i] == '1' && tag == false)
                    break;
            }
        }
        if (tag)
            printf ("NO\n");
        else
            printf ("YES\n");
    }
    return 0;
}

C.Queries for the Array

每次得到前 \(i\) 个数不满足严格递增时，并不意味着前 \(i - 1\) 个数不满足。

每次得到前 \(i\) 个数满足严格递增时，意味着前 \(j\) 个数都满足，\(j<i\)。

所以可以对于 \(0\) 和 \(1\) 分别打标记，在遇到 ‘+’ 或 ‘-’ 时根据标记性质选择继承、储存和改变。

#include <bits/stdc++.h>
using namespace std;
int T, n, tag[200005], top, now_tag;
char s[200005];
bool Ans;
int main (){
    scanf ("%d", &T);
    while (T --){
        scanf ("\n%s", s + 1);
        n = strlen (s + 1);
        Ans = true;
        now_tag = 1;
        top = 0;
        tag[0] = 1;
        for (int i = 1;i <= n;++ i){
            if (s[i] == '+'){
                if (now_tag == 1)
                    now_tag = 2;
                ++ top;
                tag[top] = 2;
                if (now_tag == 0)
                    tag[top] = 0;
                if (top == 1){
                    tag[top] = 1;
                    now_tag = 1;
                }
            }
            if (s[i] == '-'){
                if (top < 1){
                    Ans = false;
                    break;
                }
                if (tag[top] == 1)
                    tag[top - 1] = 1;
                -- top;
                now_tag = tag[top];
            }
            if (s[i] == '1'){
                if (now_tag == 0){
                    Ans = false;
                    break;
                }
                tag[top] = 1;
                now_tag = 1;
            }
            if (s[i] == '0'){
                if (now_tag == 1){
                    Ans = false;
                    break;
                }
                now_tag = 0;
                tag[top] = 0;
            }
        }
        if (Ans)
            printf ("YES\n");
        else
            printf ("NO\n");
    }
    return 0;
}

D.Sorting By Multiplication

如果不考虑负数，则可以从 \(i=1\) 开始往后扫：

若 \(a_i < a_{i+1}\) 就不管；

否则将 \(a_x,x\in[i+1,n]\) 乘上一个倍数使 \(a_i< a_{i+1}\)。

考虑负数，就可以对原序列分两段。左段为负，我们可以倒着做上述操作，右段正着做。

这样是 \(O(n^2)\) 的，但是可以通过预处理变为 \(O(n)\)。

#include <bits/stdc++.h>
using namespace std;
int T, n, a[200005], Ans, f[200005], g[200005];
int main (){
    scanf ("%d", &T);
    while (T --){
        scanf ("%d", &n);
        for (int i = 1;i <= n;++ i)
            scanf ("%d", &a[i]);
        f[1] = 0;
        for (int i = 2;i <= n;++ i)
            if (a[i - 1] > a[i])
                f[i] = f[i - 1];
            else
                f[i] = f[i - 1] + 1;
        g[n] = 0;
        for (int i = n - 1;i >= 1;-- i)
            if (a[i + 1] > a[i])
                g[i] = g[i + 1];
            else
                g[i] = g[i + 1] + 1;
        Ans = n - 1;
        for (int i = 1;i <= n + 1;++ i){
            if (i == 1)
                Ans = min (Ans, g[1]);
            else
            if (i == n + 1)
                Ans = min (Ans, f[n] + 1);
            else
                Ans = min (Ans, g[i] + f[i - 1] + 1);
        }
        printf ("%d\n", Ans);
    }
    return 0;
}

E.Non-Intersecting Subpermutations

考虑 DP。

首先，很显然的一点是，对于固定的序列，每次选最左边第一个合法的连续段并删去，能够选的次数等于其价值，为了不算重，我们要求下面的所有连续段一定都尽量靠左，对于每个序列只算所有连续段都靠最左时的一次答案。

令 \(f_i\) 表示考虑前 \(i\) 个位置，最后一个连续段为 \([i-k+1,i]\) 时的的方案数。

令 \(g_i\) 表示考虑一个长度为 \(i\) 的序列，从左往右的第一个合法连续段的右端点为 \(i\) 的方案数。

\(g_i\) 是为了转移 \(f_i\) 而生的，我们可以枚举上一个连续段的右端点 \(j\) 。所以有 \(f\) 的转移式：

\[f_i=\sum_{j=k}^{i-k} f_jg_{i-j} \]

所以问题的关键在于求 \(g\)。

对于一个 \(g_i\) 我们考虑整体减局部。

\([i-k+1,i]\) 是合法连续段的方案数为 \(k!k^{i-k}\)。

考虑第一个合法连续段的右端点为 \(j\) （\(k \le j \le i - 1\)）且满足 \([i-k+1,i]\) 是合法连续段时的方案数，这时分类讨论：

  1. \(i-j<k\) ，这时因为我们还要求了“满足 \([i-k+1,i]\) 是合法连续段“的条件，而 \([i-k+1,j]\) 已经构成了一个 \(k-i+j\) 长度的不重复数列，我们在后面填数使其构成 \(k\) 长度的排列，其方案数实际上是等于在其后面插入一个 \(i-j\) 的排列，所以此时 \(g_j\) 的贡献是 \((i-j)!g_j\)。
  2. \(i-j \ge k\)，这是我们首先满足 \([i-k+1,i]\) 是合法连续段的条件，然后剩下的 \(i-j-k\) 个数可以随便填，所以此时 \(g_j\) 的贡献是 \(k!k^{i-j-k}g_j\) 。

综上，有：

\[g_i = k!k^{i-k} - \sum_{j=k}^{i-1} ([i-j<k](i-j)!g_j + [i-j \ge k]k!k^{i-j-k}g_j) \]

\([]\) 是艾佛森括号。

然后通过 \(f\) 的转移式可以算出 \(f\)。

此时对于一个 \(f_i\)，其前面的位置都已确定，而其后面的位置无论怎么填， \([i-k+1,i]\) 都会在这个序列中以一个正确的”尽量靠左“的连续段，所以必然会被计入答案。因为后面随便填，所以 \(f_i\) 的贡献为 \(k^{n-i}f_i\)

即：

\[Answer=\sum_{i=1}^n k^{n-i}f_i \]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n, k;
int f[4005], g[4005];
int jc[4005], kpow[4005];
int Ans;
signed main (){
   scanf ("%lld%lld", &n, &k);
   jc[0] = kpow[0] = 1;
   for (int i = 1;i <= n;++ i){
       jc[i] = jc[i - 1] * i % mod;
       kpow[i] = kpow[i - 1] * k % mod;
   }
   for (int i = 0;i < k;++ i)
       g[i] = 0;
   for (int i = k;i <= n;++ i){
       g[i] = jc[k] * kpow[i - k] % mod;
       for (int j = k;j < i;++ j)
           if (i - j < k)
               (g[i] += mod - jc[i - j] * g[j] % mod) %= mod;
           else
               (g[i] += mod - jc[k] * kpow[i - j - k] % mod * g[j] % mod) %= mod;
   }
   for (int i = 0;i < k;++ i)
       f[i] = 0;
   for (int i = k;i <= n;++ i){
       f[i] = g[i];
       for (int j = k;j + k <= i;++ j)
           (f[i] += f[j] * g[i - j] % mod) %= mod;
       (Ans += f[i] * kpow[n - i] % mod) %= mod;
   }
   printf ("%lld\n", Ans);
   return 0;
}