跳转至

CF1383 题解

CF1383A String Transformation 1

给你两个长度为 \(n\) 的字符串 \(a,b\)（小写字母），你需要尽可能少的执行以下操作，使得 \(a\) 变成 \(b\)：

  • 选择一些下标 \(p_1,p_2,\cdots p_k\) 满足 \(p_1<p_2<\cdots<p_k\) 且 \(a_{p_1}=a_{p_2}=\cdots=a_{p_k}\)，然后将 \(a\) 的这些位置替换为另一字母 \(y\)，同时满足 \(y>a_{p_i}\)；

\(n\le 10^5\)

考虑 \(n\) 个字符二元组 \((a_i,b_i)\)，表示需要把字符 \(a_i\) 变成 \(b_i\)。然后从 \(a_i\) 向 \(b_i\) 连一条有向边，这样可以建出一个 DAG。

依次考虑 DAG 的每一个连通块，我们只需要按照拓扑序扫一遍所有字母就可以了，因此一个连通块的代价为 \(sz-1\)。如果用少于 \(sz-1\) 次操作，则连通块无法被操作连通，因此必定存在要求没有被满足。

CF1383B GameGame

有一个可重集，Alice 和 Bob 进行博弈，Alice 先手。每回合：

  • 当前玩家从集合中拿走一个数；

集合为空之后，游戏结束。拿走数异或和更大的人获胜。假设二人都非常聪明，问最终谁会获胜，或者平局。

取集合的异或和 \(s\)，显然只有 \(s\) 的最高位有用。若 \(s=0\) 则平局。现在问题转化为：数字只有 \(0\) 和 \(1\)，\(1\) 有奇数个，最终拿走奇数个 \(1\) 的人获胜。

分讨 \(0\) 的奇偶性，若有偶数个 \(0\)，那么显然等价于没有（选 \(0\) 后，另一个人都可以立即再选一个 \(0\)），答案取决于 \(1\) 的数量模 \(4\) 的余数。若有奇数个 \(0\)，那么等价于只有一个 \(0\)。此时如果只靠前面的 \(1\)，Alice 无法获胜，那么它可以取 \(0\) 将局势反转。其余情况，Alice 只要不取 \(0\) 就会获胜。因此 Alice 必胜。

CF1383D Rearrange

给你一个 \(n\times m\) 的矩阵，矩阵中 \([1,mn]\) 的每个数字各出现一次。请你再构造一个矩阵，满足每行最大值组成的集合，以及每列最大值组成的集合与给定的矩阵相等。

你还要满足你构造出的矩阵的每一行、每一列都是单峰的。

\(n,m\le 250\)

可以先填行列最大值集合中的数字，然后再填其它数字。不难想到将所有最大值降序排序然后依次填入。填的过程中，你需要保证：行最大值所在的行不存在已经填入的数字；列最大值和行&列最大值同理。

这个条件比较容易实现，我们甚至没有限制行最大值应该填在哪一列之类的。现在应该考虑那些非最大值数字。也将它们从大到小排好序。

这里直接提供一种构造：从 \((0,0)\) 出发，如果遇到行最大值就往下走一格，如果遇到列最大值就往右走一格，如果遇到行&列最大值就往右下走一格。如果往下走了一格走到 \((x,y)\)，就把 \((x,y)\) 左边的格子从右到左填上非最大值；如果往右走了一格走到 \((x,y)\)，就把 \((x,y)\) 上面的格子从下到上填上非最大值。

这种构造有一个好的性质就是：矩阵空白的位置都唯一对应一个行最大值和列最大值的二元组。

不难发现这样满足单峰的条件，并且填入的非最大值也一定不会超过同行同列的最大值（因为原先的矩阵就是满足这个条件的一个构造，发现排序后大的数字找到了更宽松的限制，小的数字找到了更严格的限制，这样更优，因此也合法）。

代码 
 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<iostream>
using namespace std;
const int N = 300;

int n, m;
int a[N][N];
int ans[N][N];

int f[N * N];
int sx[N * N], sy[N * N], top;

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    for(int i = 1; i <= n; i++) {
        int mx = 0;
        for(int j = 1; j <= m; j++) mx = max(mx, a[i][j]);
        f[mx] |= 1;
    }
    for(int j = 1; j <= m; j++) {
        int mx = 0;
        for(int i = 1; i <= n; i++) mx = max(mx, a[i][j]);
        f[mx] |= 2;
    }

    int x = 0, y = 0;
    for(int i = n * m; i >= 1; i--) {
        if(f[i] == 0) continue;
        else if(f[i] == 1) {
            ans[++x][y] = i;
            for(int j = y - 1; j >= 1; j--) { sx[++top] = x; sy[top] = j; }
        } else if(f[i] == 2) {
            ans[x][++y] = i;
            for(int j = x - 1; j >= 1; j--) { sx[++top] = j; sy[top] = y; }
        } else {
            ans[++x][++y] = i;
            for(int j = y - 1; j >= 1; j--) { sx[++top] = x; sy[top] = j; }
            for(int j = x - 1; j >= 1; j--) { sx[++top] = j; sy[top] = y; }
        }
    }

    for(int i = n * m, j = 1; i >= 1; i--) {
        if(f[i] == 0) {
            ans[sx[j]][sy[j]] = i;
            ++j;
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

CF1383E Strange Operation

给你一个 01 串 \(a\)，长度为 \(n\)。你可以进行至多 \(n-1\) 次操作（可以不做）：

  • 选择 \(1\le i<n'\)，执行 \(a_i\gets \max(a_i,a_{i+1})\)，然后删掉 \(a_{i+1}\)；

问你可以得到多少种本质不同的 01 串。答案对 \(10^9+7\) 取模。

\(n\le 10^6\)

发现可能会出现重复的串，而且不易去重，因此先考虑判定问题。

发现操作可以分成本质不同的两种效果：

  • 将两个 \(1\) 变成一个 \(1\)；
  • 将一个 \(0\) 连续段长度减少了 \(1\)；

设 \(a\) 的 \(0\) 连续段长度组成的序列为 \(b_{1\sim m}\)，例如

a = 0010110
b = 2,1,0,1

发现这样的 \(a\) 和 \(b\) 是一一对应的关系，所以我们直接对 \(b\) 计数也不会算重。

那么一次操作，要么是删掉一个不在开头结尾的 \(0\)，要么将一个数字减 \(1\)。因此我们容易判定一个 \(b'\) 能否被 \(b\) 生成：枚举 \(b'\) 的每一个元素，然后找到 \(b\) 中第一个大于等于这个元素的数字进行匹配。

由于 \(b\) 的第一项和最后一项不能删除只能减小，因此 \(b'\) 的第一项和最后一项其实只有 \((b[0]+1)(b[m]+1)\) 种取值。然后我们就可以不管开头结尾了。这里记得特判 \(m=1\) 的情况。

考虑 dp，仿照“本质不同子序列计数”进行设计即可。由于我们不关心子序列的长度，因此设 \(f_i\) 表示匹配到了 \(b\) 的第 \(i\) 位，\(b'\) 前面的部分有多少种取值。转移即枚举 \(b'\) 的下一位是多少，然后转移到匹配位置。

但是这样做太劣了，因此直接考虑 \(f_j\) 对 \(f_i\) 的转移系数。

\[ f_j\times \max(0,a_i-\max_{k\in(j,i)}a_k)\to f_i \]

因此这要求 \(j\) 位于 \(gel[i]\)（\(i\) 左边第一个更大的数字）之后（可以取等）。考虑单调栈，发现只有弹栈的时候可以进行转移，用前缀和优化即可。时间复杂度 \(O(n)\)。

代码 
 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
#include<iostream>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;

int n, m, ans;
int a[N];
string str;

int f[N], s[N];
int sta[N], top;

signed main() {

    cin >> str;
    n = str.size();

    str.push_back('1');
    for(int i = 0, j = 0; i <= n; i++) {
        if(str[i] == '1') a[++m] = j, j = 0;
        else ++j;
    }

    if(m == 1) { cout << a[1] << '\n'; return 0; }
    else ans = (a[1] + 1) * (a[m] + 1) % MOD;

    sta[++top] = 1;
    a[1] = N;
    f[1] = s[1] = 1;
    for(int i = 2; i <= m - 1; i++) {
        int mx = -1, pre = i;
        while(top && mx < a[i]) {
            f[i] = (f[i] + (s[pre - 1] - s[sta[top] - 1] + MOD) * (a[i] - mx) % MOD) % MOD;
            mx = a[sta[top]];
            if(mx < a[i]) pre = sta[top--];
        }
        s[i] = (s[i - 1] + f[i]) % MOD;
        sta[++top] = i;
    }

    cout << s[m - 1] * ans % MOD << '\n';

    return 0;
}