1. A. Was there an Array?

门钥匙

口头表述

给你一个长度为n的整数数组a，但是这个数组a本身没有告诉你，我们只知道它中间每个位置的相等情况：对于每个位置i，其中2 ≤ i ≤ n-1，如果 a[i-1] == a[i] == a[i+1]，那么 b[i] = 1，反之b[i] = 0。现在题目给你的是数组 b2, b3, ..., b(n-1)，让你判断：是否存在某个整数数组 a，它能够产生这个给定的 b 数组。如果存在，输出YES，反之NO。

题解

思路不复杂，发现是101的就说明有错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
    int n; cin >> n;
    vector<int> b(n-2);
    for(int i = 0;i < n-2;++i) cin >> b[i];

    for(int i = 0;i < n-4;++i){
        if(b[i] == 1 && b[i+2] == 1){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    return;
}

WA2，为什么，因为这个地方只保证1 * 1，而没保证101

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
    int n; cin >> n;
    vector<int> b(n-2);
    for(int i = 0;i < n-2;++i) cin >> b[i];

    for(int i = 0;i < n-4;++i){
        if(b[i] == 1 && b[i+2] == 1 && b[i+1] == 0){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    return;
}

2. B. Set of Strangers

门钥匙

口头表述

给你一个n*m的表格，每个格子一开始有一个颜色。如果两个格子没有公共边，那么这两个格子叫陌生人。现在你可以做一些操作，每次操作，可以选择若干个格子，要求每个格子两两陌生，颜色必须相同，然后把这些格子染成另一个颜色。目标是用最少的操作次数，把整个表格染成同一个颜色，最后输出这个最少的操作次数

题解

这道题的目标是把整个矩阵染成同一种颜色。一次操作可以选择若干个颜色相同的格子，并且这些格子两两之间不能共边，然后把它们全部染成另一种颜色。

我们先不考虑最终染成什么颜色，而是单独考虑某一种颜色 x：如果最后不保留颜色 x，那么就需要把所有颜色为 x 的格子全部改掉。

对于一种颜色 x，它被全部改掉所需要的操作次数只有两种可能：1 或 2。

如果所有颜色为 x 的格子之间都没有上下左右相邻，那么这些格子本身就是一个合法的”陌生人集合”，可以在一次操作中全部染成目标颜色，所以这种颜色的代价是 1。

如果颜色 x 存在两个上下左右相邻的格子，那么这两个格子不能在同一次操作中同时被选择，所以至少需要 2 次操作。又因为整个矩阵可以按照棋盘黑白染色来划分，同一种颜色的格子可以分成黑格上的一组和白格上的一组。黑格之间不会共边，白格之间也不会共边，所以最多 2 次一定可以把这种颜色全部改掉。因此这种颜色的代价是 2。

所以我们可以定义一个数组 f：

1
2
3
f[x] = 0 表示颜色 x 没有出现过
f[x] = 1 表示颜色 x 出现过，但没有相邻同色格子
f[x] = 2 表示颜色 x 出现过，并且存在相邻同色格子

题目中颜色的范围是 1 <= a[i][j] <= n * m，所以可以直接开vector<int> f(n * m + 1, 0);，这样就可以用颜色值本身作为下标。例如颜色 x 出现时，就更新 f[x]。

接下来遍历矩阵，判断某个颜色是否存在相邻同色格子。对于每个格子 (i, j)，只需要检查它的上方 (i - 1, j) 和左方 (i, j - 1) 是否和它颜色相同即可。

因为如果某个格子和右边或下边相邻，那么在之后遍历到右边或下边那个格子时，也会通过检查左边或上边发现这对相邻关系。

遍历时，如果颜色 x 第一次出现，就令f[x] = 1，如果发现它和上方或左方格子颜色相同，就说明颜色 x 存在相邻同色格子，需要两步操作才能全部改掉，于是令f[x] = 2。统计完所有颜色的代价后，假设所有出现过的颜色代价之和为 sum。

如果最终选择颜色 tar 作为整张表的最终颜色，那么颜色 tar 不需要被修改，其他颜色都需要改成 tar。所以答案就是sum - f[tar]。

为了让操作次数最少，应该选择代价最大的颜色作为最终颜色。于是最终答案为sum - max(f[x])，也就是说，先求所有颜色的总代价，再减去其中最大的代价。

时间复杂度为 O(nm)，因为每个格子只需要遍历一次。空间复杂度为 O(nm)，用于存储矩阵和颜色状态数组。

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
void solve(){
    int n,m; cin >> n >> m;
    vector<vector<int>> g(n+1,vector<int> (m+1,0));
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            cin >> g[i][j];
        }
    }

    vector<int> f(n*m+1,0);
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            int x = g[i][j];

            if(f[x] == 0) f[x] = 1;
            
            if(i > 1 && g[i-1][j] == x) f[x] = 2;
            if(j > 1 && g[i][j-1] == x) f[x] = 2;
        }
    }

    int sum = 0,mx = 0;
    for(int i = 1;i <= n*m;++i){
        sum += f[i];
        mx = max(mx,f[i]);
    }

    cout << sum-mx << '\n';
    return;
}

3. C. Beautiful Sequence

门钥匙

口头表述

给你一个数组a，里面每个数只能是1 2 3，现在让你统计多少个子序列是美丽的。

一个子序列美丽，需要满足：

  1. 长度至少是3
  2. 除了第一个元素，每个元素左边都要有一个比它小的数
  3. 除了最后一个元素，每个元素右边都要有一个比它大的数

题解

首先我们需要想什么序列可能美丽。可以想到，第一个数必须是1，最后一个数必须是3，而中间至少有一个2。

这道题需要我们用到子序列计数dp，也就是状态机dp，我们记录三个状态：

dp1：当前已经形成的 [1] 子序列数量
dp2：当前已经形成的 [1, 2, 2, …] 子序列数量，要求至少有一个 2
res：当前已经形成的 [1, 2, …, 3] 美丽子序列数量

如果当前数是1，那么它可以作为一个新的[1]子序列，即dp1++

如果当前数是2，那么它可以接在以前的[1]后面形成[1,2]，也可以接在以前的[1,2,2,…]后面，因此dp2 = dp2*2+dp1

如果当前数是3，那就形成美丽子序列，所以res += dp2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
    int n; cin >> n;
    int dp1 = 0,dp2 = 0,res = 0;
    for(int i = 0;i < n;++i){
        int x; cin >> x;

        if(x == 1) dp1 = (dp1+1)%mod;
        else if(x == 2) dp2 = (dp2*2%mod+dp1)%mod;
        else res = (res+dp2)%mod;
    }

    cout << res << '\n';
    return;
}