题解：P15072 [ICPC 2024 Chengdu R] Arrow a Row

· · 题解

思路

可行性

通过题意可以知道一个合法的箭头串必须有以下条件：

所以可以很容易推出如果要用若干合法的箭头串绘制出来给定串则给定串开头必须是 >，结尾必须是 >>> 且所有字符不能全为 >，前两个条件很容易发现，最后一个条件是因为任意一个合法箭头串都至少有一个 -，所以不可能全为 >。

如何构造

可行性判断完后我们考虑构造。由于题目中说操作数只需不超过给定串长度即可，于是我们可以直接构造一个绝对可行的操作，因为只要不完全覆盖前面的操作，最劣情况绝对不可能超过给定串长度。

由于箭头串可以覆盖，所以考虑从外到内构造。本蒟蒻使用了一种最懒人的构造方法，先从末尾向前找最后一段连续的 >>>，并记录对应的绘制操作，再从前往后遍历，如果为 > 便以这个地方为开头，找到的从末尾向前最后一段连续的 >>> 为结尾绘制，这样可以既是从外到内不会被覆盖影响，又保证绝对可行，代码还出奇简单。

示例

例如 >->>>->->>>>，按照逻辑找到最后一段 >>>（9 \sim 11），并绘制 \{1,12\},\{1,11\}，再从前往后遍历找 > 并绘制 \{3,9\},\{4,8\},\{5,7\},\{7,5\}。 总操作次数 6，小于长度 12，且满足要求。

可结合代码进一步理解构造逻辑。

code

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

int main()
{
    int T;
    cin >> T;
    while (T --) // 多测
    {
        string s;
        cin >> s;
        int n = s.size();
        s = " " + s; // 转换为1-based索引
        int flag = 1; // 标记字符串是否全为'>'
        for (int i = 1; i <= n; ++ i)
        {
            if (s[i] == '-') // 存在'-'则说明不是全'>'
            {
                flag = 0;
                break;
            }
        }
        // 不可行条件：全为'>' 或 开头不是'>' 或 最后三位不是">>>"
        if (flag || s[1] != '>' || s.substr(n - 2, 3) != ">>>")
        {
            cout << "No" << endl; 
            continue;
        }
        // lst：从字符串末尾向前遍历，最后一段连续">>>"的结束位置
        // cnt：绘制操作的总次数
        int lst = n, cnt = 0; 
        vector<pair<int, int>> ans; // 存储每次操作的(起始位置, 长度)

        // 从末尾向前找最后一段连续的">>>"，并记录对应的绘制操作
        for (int i = n; i >= 3; -- i) // i>=3才满足3字符长度
        {
            // 检查以i为结尾的3个字符是否是">>>"
            if (s.substr(i - 2, 3) == ">>>")
            {
                cnt ++;
                lst = i; // 更新lst为当前">>>"的结束位置
                ans.push_back({1, i}); // 绘制从位置1到i的箭头字符串
            }
            else
            {
                break; // 遇到第一个非">>>"的位置，停止遍历
            }
        }
        // 遍历构造剩余需要的'>'位置（避免重复覆盖，遍历到lst-4）
        for (int i = 2; i <= lst - 4; ++ i)
        {
            if (s[i] == '>') // 当前位置若是'>'，则绘制以i为起点、lst为终点的箭头串
            {
                cnt ++;
                ans.push_back({i, lst - i + 1}); // 长度=终点-起点+1
            }
        }
        // 输出方案
        cout << "Yes " << cnt << endl;
        for (auto pr : ans)
        {
            cout << pr.first << ' ' << pr.second << endl;
        }
    }
    return 0;
}

时间复杂度 O(\sum n)。