题解

按照题意直接模拟即可。

从前往后枚举位置 i：

• 如果 i 是奇数，那么必须满足 a[i]=a[i+1]
• 如果 i 是偶数，那么必须满足 a[i]≠a[i+1]

只要有一个位置不满足，就不是配对序列。

用 cnt 记录不合法的位置个数，最后判断 cnt 是否为 0 即可。

时间复杂度为 O(n)。

#include<bits/stdc++.h>
using namespace std;

int a[110];

int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        int cnt = 0;
        for(int i = 1; i < n; i++){
            if(i % 2 == 1 && a[i] != a[i + 1]) cnt++;
            else if(i % 2 == 0 && a[i] == a[i + 1]) cnt++;
        }

        if(cnt == 0) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

题目思路

题目要求模拟箱子下落。

注意到每一列之间互不影响，所以我们可以按列处理。

对于某一列：

• 挡板 - 会把这一列分成若干段；
• 在同一段中，所有箱子最后都会因为重力掉到这一段的最下方；
• 这一段里剩下的位置都变成 .。

所以我们可以从下往上扫描一列：

• 用数组 c 暂时存这一段里遇到的所有箱子；
• 如果当前格子不是挡板 -，并且是箱子，就把它记下来；
• 如果当前格子是挡板，或者已经扫到了最上面，就说明这一段结束了；
• 这时把这一段重新填一遍：下面先放箱子，上面补 .。

这样处理完每一列后，整个答案就出来了。

---

代码做法说明

代码的核心是这一部分：

for(int j=1; j<=m; j++){
    int b=n, cnt=0;
    for(int i=n; i>=0; i--){
        if(a[i][j]!='-'&&i!=0){
            if(a[i][j]!='.'){
                c[++cnt]=a[i][j];
            }
        }else{
            int cnt1=1;
            for(int k=b; k>i; k--){
                if(cnt1<=cnt){
                    a[k][j]=c[cnt1++];
                }else{
                    a[k][j]='.';
                }
            }
            cnt=0;
            b=i-1;
        }
    }
}

含义如下：

• j 枚举每一列；
• b 表示当前这一段的最下边界；
• cnt 表示当前这一段里有多少个箱子；
• 从下往上扫，如果遇到箱子，就存到 c 中；
• 如果遇到挡板，说明当前这一段结束，把箱子全部填到这一段底部；
• 然后开始处理上一段。

---

为什么这样做是对的

因为重力只会让箱子竖直下落，不会左右移动，所以每一列可以单独考虑。

对于一列中的某一段（上下边界可能是挡板或边界）：

• 段中的箱子数量不会改变；
• 箱子的相对顺序不会改变；
• 最终一定全部堆到这一段的最底部。

所以我们只需要统计每一段有哪些箱子，再把它们放到底部即可。

---

复杂度分析

设网格大小为 n × m。

• 每个格子只会被扫描和重写有限次；
• 总时间复杂度为 O(nm)；
• 额外空间复杂度为 O(n)，用于暂存一列中的箱子。

在本题中 m ≤ 10，所以这样做完全可以通过。

---

参考代码（按给定代码整理，简易注释）

#include<bits/stdc++.h>
using namespace std;

char a[100010][15];
char c[100010];

int main(){
    int n, m;
    cin >> n >> m;

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

    // 按列处理
    for(int j = 1; j <= m; j++){
        int b = n, cnt = 0;  // b 表示当前这一段的下边界，cnt 表示这一段中的箱子数

        // 从下往上扫描
        for(int i = n; i >= 0; i--){
            // 不是挡板，并且不是第 0 行（第 0 行是人为加的边界）
            if(a[i][j] != '-' && i != 0){
                // 如果当前是箱子，就存起来
                if(a[i][j] != '.'){
                    c[++cnt] = a[i][j];
                }
            }else{
                // 遇到挡板，或者扫到最顶端，说明当前这一段结束
                int cnt1 = 1;

                // 重新填这一段：下面放箱子，上面放空格
                for(int k = b; k > i; k--){
                    if(cnt1 <= cnt){
                        a[k][j] = c[cnt1++];
                    }else{
                        a[k][j] = '.';
                    }
                }

                // 清空这一段的记录，准备处理上一段
                cnt = 0;
                b = i - 1;
            }
        }
    }

    // 输出结果
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << a[i][j];
        }
        cout << endl;
    }

    return 0;
}

---

补充说明

这份代码有一个很巧妙的地方，就是：

for(int i=n; i>=0; i--)

它故意让 i 扫到 0，把第 0 行当作一个虚拟边界。
这样最上面一段在循环结束时也能被统一处理，不需要额外再写一遍收尾代码。

这个技巧在分段模拟题里很常见。

先设矩阵中的最大值是 mx。

一次操作只能让一整行和一整列的数减 1，所以一个数最多只会减小 1。
因此操作后的最大值只可能是：

• mx
• mx-1

所以问题就变成了：

能不能找到一行和一列，把所有值等于 mx 的位置全部覆盖掉？

• 如果能全部覆盖，那么这些最大值都会减一，答案就是 mx-1。
• 如果不能全部覆盖，那么一定还会剩下某个最大值没变，答案就是 mx。

---

如何判断

先把所有等于 mx 的位置存下来。

设第一个最大值位置是 (r1,c1)。

如果后来找到一个最大值位置 (r2,c2)，满足：

• r2 != r1
• c2 != c1

那么若想同时覆盖这两个点，只可能有两种选法：

• 选第 r1 行和第 c2 列
• 选第 r2 行和第 c1 列

把这两种情况分别检查一下：

• 如果有一种能覆盖所有最大值，输出 mx-1
• 否则输出 mx

如果根本找不到这样的 (r2,c2)，说明所有最大值本来就在同一行或同一列上，一定可以全部覆盖，直接输出 mx-1。

---

复杂度

每组数据只需要扫几遍矩阵，时间复杂度是 O(nm)。

---

参考代码

#include<bits/stdc++.h>
using namespace std;

// a[i][j] 表示矩阵中的元素
// 这里用 vector 存每一行
vector<int> a[100010];

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n, m;
        int mx = 0;   // 记录当前测试用例中的最大值
        cin >> n >> m;

        // 读入矩阵，同时求出整个矩阵的最大值 mx
        for (int i = 1; i <= n; i++) {
            a[i].resize(m + 10);  // 开够空间，方便 1 下标使用
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
                mx = max(mx, a[i][j]);
            }
        }

        // v 用来保存所有值等于 mx 的位置
        vector<pair<int, int> > v;

        // 下面这四个变量用于构造两种候选方案：
        // 若找到两个最大值点 (r1,c1) 和 (r2,c2)，且它们不同行不同列，
        // 那么若想同时覆盖这两个点，只可能选：
        // 1. 第 r1 行 + 第 c2 列
        // 2. 第 r2 行 + 第 c1 列
        int x1 = -1, y1 = -1; // 第一种方案：选第 x1 行和第 y1 列
        int x2 = -1, y2 = -1; // 第二种方案：选第 x2 行和第 y2 列

        // 枚举整个矩阵，找出所有最大值的位置
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] == mx) {
                    // 把这个最大值的位置存下来
                    v.push_back({i, j});

                    // 如果这不是第一个最大值点，就尝试和第一个点配对
                    if (v.size() > 1) {
                        // 只有当当前点和第一个点“既不同行，也不同列”时，
                        // 才需要真正讨论覆盖方案
                        if (i != v[0].first && j != v[0].second) {
                            // 第一个最大值点是 (v[0].first, v[0].second)
                            // 当前最大值点是 (i, j)

                            // 两种可能的覆盖方案：
                            // 方案 1：选第一个点的行 + 当前点的列
                            x1 = v[0].first;
                            y1 = j;

                            // 方案 2：选当前点的行 + 第一个点的列
                            x2 = i;
                            y2 = v[0].second;
                        }
                    }
                }
            }
        }

        // 如果 x1 仍然是 -1，说明没有找到“既不同行也不同列”的最大值点
        // 也就是说，所有最大值都和第一个最大值在同一行或同一列上
        // 那么一定能用“一行一列”把所有最大值全部覆盖，答案就是 mx-1
        if (x1 == -1) {
            cout << mx - 1 << endl;
        } else {
            int cnt1 = 0, cnt2 = 0;

            // 检查方案 1 和方案 2 分别能覆盖多少个最大值点
            for (int i = 0; i < (int)v.size(); i++) {
                // 如果一个最大值点在方案 1 选中的那一行或那一列上，
                // 就说明它会被减 1
                if (v[i].first == x1 || v[i].second == y1) cnt1++;

                // 同理检查方案 2
                if (v[i].first == x2 || v[i].second == y2) cnt2++;
            }

            // 只要两种方案中有一种能覆盖全部最大值，
            // 那么所有最大值都能减 1，答案就是 mx-1
            if (cnt1 == (int)v.size() || cnt2 == (int)v.size()) {
                cout << mx - 1 << endl;
            } else {
                // 否则至少有一个最大值无法被覆盖
                // 它不会减 1，最终答案还是 mx
                cout << mx << endl;
            }
        }
    }

    return 0;
}

---

题意分析

一次操作可以选择 i < j，然后：

• 把 S[i] 改成 A
• 把 S[j] 改成 B

所以一次操作本质上可以同时修正两类错误：

• 某个位置本来是 B，目标却要变成 A
• 某个位置本来是 A，目标却要变成 B

记这两种位置分别为：

• BA 型：S[i]='B' , T[i]='A'
• AB 型：S[i]='A' , T[i]='B'

因为操作要求 i<j，所以：

• 一个前面的 BA 型位置，可以和后面的 AB 型位置直接配成一次操作；
• 如果不能直接配对，就要看后面或前面是否还有位置能“帮忙”，否则无解。

---

程序思路

代码中用了两个指针：

• A：寻找下一个 BA 型位置
• B：寻找下一个 AB 型位置

也就是分别找：

s1[A]=='B' && s2[A]=='A'
s1[B]=='A' && s2[B]=='B'

然后分类讨论：

1. A < B

说明前面有一个 BA 型，后面有一个 AB 型。
这样可以直接用一次操作同时解决这两个位置，所以二者都向后移动，答案加一。

如果这时已经没有可用的 AB 型位置了，就看后面还有没有目标为 B 的位置可以帮忙，如果没有就无解。

---

2. A > B

说明当前找到的 AB 型在前，BA 型在后。
由于操作必须满足 i<j，这种顺序不能直接配对。

这时只能要求前面存在某个目标为 A 的位置来帮助完成操作。
如果前面根本没有这样的地方，就无解；否则把这个 AB 型处理掉，答案加一。

---

辅助数组含义

haveA[i]

表示在 T 的前缀 0...i 中，是否出现过字符 A。

作用：当出现 A>B 时，判断前面有没有位置可以作为左端点。

---

haveB[i]

表示在 T 的后缀 i...n-1 中，是否出现过字符 B。

作用：当只剩下 BA 型位置时，判断后面还有没有位置可以作为右端点。

---

为什么这样做是对的

因为每次操作左边必须改成 A，右边必须改成 B，所以操作方向是固定的：

• 左边负责处理需要变成 A 的位置
• 右边负责处理需要变成 B 的位置

因此最优做法就是尽量把一个 BA 型和一个后面的 AB 型直接配成一对。
如果顺序不对，就只能借助别的位置。
一旦连借助位置都不存在，就一定无解。

---

复杂度分析

两个指针都只会从左到右扫一遍，辅助数组也只需线性预处理。

所以总时间复杂度是：

• O(n)

空间复杂度是：

• O(n)

---

参考代码（简易注释）

#include<bits/stdc++.h>
using namespace std;

string s1, s2;
int haveA[200010], haveB[200010];

int main(){
    int n, A = 0, B = 0;
    cin >> n;
    cin >> s1 >> s2;

    // haveA[i] 表示：在 T 的前缀 [0..i] 中是否出现过 A
    for(int i = 0; i < n; i++){
        if(s2[i] == 'A'){
            haveA[i] = 1;
        }else if(i > 0){
            haveA[i] = haveA[i - 1];
        }
    }

    // haveB[i] 表示：在 T 的后缀 [i..n-1] 中是否出现过 B
    for(int i = n - 1; i >= 1; i--){
        if(s2[i] == 'B'){
            haveB[i] = 1;
        }else{
            haveB[i] = haveB[i + 1];
        }
    }

    int ans = 0, ok = 0;

    // A 指针找 BA 型：S[i]='B', T[i]='A'
    // B 指针找 AB 型：S[i]='A', T[i]='B'
    while(A < n || B < n){

        while(A < n && (s1[A] != 'B' || s2[A] != 'A')) A++;
        while(B < n && (s1[B] != 'A' || s2[B] != 'B')) B++;

        // 两类错误位置都找不到了，结束
        if(A >= n && B >= n) break;

        if(A < B){
            // 前面是 BA，后面是 AB，可以直接配成一次操作
            if(B < n){
                A++;
                B++;
            }else if(haveB[A + 1]){
                // 没有 AB 型了，但后面还存在目标为 B 的位置，可以借助处理
                A++;
            }else{
                // 后面连一个可作为右端点的位置都没有，无解
                ok = 1;
                break;
            }
        }else{
            // A > B，说明 AB 在前、BA 在后，不能直接配
            // 必须看前面是否存在目标为 A 的位置可以借助
            if(haveA[B - 1] == 0){
                ok = 1;
                break;
            }
            B++;
        }

        ans++;
    }

    if(ok == 1) cout << -1;
    else cout << ans;

    return 0;
}

---