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

· · 题解

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

题意

题目要求我们通过若干次绘制操作，将一个全 * 的初始字符串转换成目标字符串 s。每次操作可以选择一个长度至少为 5 的子串，将其替换为箭头字符串：

我们需要判断是否能在不超过 n 次操作内完成转换，并给出具体操作方案。

思路

通过分析发现，最终字符串 s 中所有的 > 必须位于某次操作的起点或最后三个位置，因为操作的中间部分只能是 -。因此我们可以采用贪心策略从后往前构造操作。

  1. 初步检查。

  2. 从后往前处理：

    • 首先处理末尾的 >>> 部分，尽可能多地构造从位置 1 开始的覆盖操作。
    • 然后处理中间剩余部分，为每个 > 构造单独的操作。

  3. 验证可行性，确保中间部分至少有一个 >。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        int n=s.size();
        s=' '+s; // 添加前导空格，使下标从1开始

        // 初步检查：长度、首尾字符
        if(s[n]!='>'||s[n-1]!='>'||s[n-2]!='>'||s[1]!='>'||n<5){
            cout<<"No\n";
            continue;
        } 

        int r=n+1; // 记录当前未覆盖区域的右边界
        vector<pair<int,int> > v;// 存储操作序列

        // 第一步：处理末尾的>>>部分
        // 从后往前，每遇到连续的>>>就构造一个从位置1开始的覆盖操作
        for(int j=n;j>=5;j--){
            if(s[j-2]=='>'){// 检查j-2,j-1,j是否构成>>>
                r--;// 缩小未覆盖区域
                v.push_back({1,j});// 添加从1到j的操作
            }
            else break;// 不再连续，停止
        }

        // 第二步：处理中间剩余部分
        bool f=0;// 标记是否找到有效的'-'
        for(int i=2;i<=r-3;i++){// 遍历未覆盖区域
            if(s[i]=='-')f=1;// 找到至少一个'-'

            // 对于每个'>'，构造一个操作覆盖到当前边界r
            if(s[i]=='>'&&i!=r-3){// 避免在边界处重复操作
                v.push_back({i,r-i+1});// 添加从i开始，长度为r-i+1的操作
            }
        }
        // 验证：必须至少有一个'-'才是有效构造
        if(f==0)cout<<"No\n";
        else{
            cout<<"Yes "<<v.size()<<"\n"; // 输出操作数量
            for(auto o:v)cout<<o.first<<" "<<o.second<<"\n";// 输出每个操作
        }
    }
    return 0;
}