题解

题目分析

米小游有一个长度为 $n$ 的字符串 $s$，她需要选择两个区间 $[a,b]$ 和 $[c,d]$，分别对这两个区间执行翻转操作。如果翻转后的字符串与原始字符串相同，则输出 YES 和对应的区间；否则输出 NO。

解题思路

1. 翻转操作的性质：

   • 翻转操作会改变字符串中某些字符的顺序。
   • 如果翻转后的字符串与原始字符串相同，说明翻转操作对字符串的影响被抵消了。

2. 寻找回文子串：

   • 回文子串是指正读和反读都相同的子串。
   • 如果字符串中存在两个互不重叠的回文子串，那么对这两个区间分别执行翻转操作，翻转后的字符串可能与原始字符串相同。

3. 实现步骤：

   • 遍历字符串，寻找所有长度为 2 或 3 的回文子串。
   • 检查是否存在两个互不重叠的回文子串。
   • 如果存在，输出 YES 和对应的区间；否则输出 NO。

代码实现

Python 代码

def main():
    n = int(input())
    s = input()
    palindromes = []
 
    # 寻找所有长度为2或3的回文子串 
    for i in range(n):
        # 检查长度为2的回文 
        if i + 1 < n and s[i] == s[i + 1]:
            palindromes.append((i, i + 1))
        # 检查长度为3的回文 
        if i + 2 < n and s[i] == s[i + 2]:
            palindromes.append((i, i + 2))
 
    # 检查是否存在两个互不重叠的回文子串 
    for i in range(len(palindromes)):
        a1 = palindromes[i][0] + 1  # 转换为1-based索引 
        b1 = palindromes[i][1] + 1 
        for j in range(i + 1, len(palindromes)):
            a2 = palindromes[j][0] + 1 
            b2 = palindromes[j][1] + 1 
            if b1 < a2:  # 确保区间不重叠 
                print("YES")
                print(a1, b1, a2, b2)
                return 
 
    # 如果没有找到，则输出NO 
    print("NO")
 
if __name__ == "__main__":
    main()

java代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        List<int[]> palindromes = new ArrayList<>();
 
        // 寻找所有长度为2或3的回文子串 
        for (int i = 0; i < n; i++) {
            // 检查长度为2的回文 
            if (i + 1 < n && s.charAt(i) == s.charAt(i + 1)) {
                palindromes.add(new int[]{i, i + 1});
            }
            // 检查长度为3的回文 
            if (i + 2 < n && s.charAt(i) == s.charAt(i + 2)) {
                palindromes.add(new int[]{i, i + 2});
            }
        }
 
        // 检查是否存在两个互不重叠的回文子串 
        for (int i = 0; i < palindromes.size(); i++) {
            int a1 = palindromes.get(i)[0] + 1; // 转换为1-based索引 
            int b1 = palindromes.get(i)[1] + 1;
            for (int j = i + 1; j < palindromes.size(); j++) {
                int a2 = palindromes.get(j)[0] + 1;
                int b2 = palindromes.get(j)[1] + 1;
                if (b1 < a2) { // 确保区间不重叠 
                    System.out.println("YES");
                    System.out.println(a1 + " " + b1 + " " + a2 + " " + b2);
                    return;
                }
            }
        }
 
        // 如果没有找到，则输出NO 
        System.out.println("NO");
    }
}

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<pair<int, int>> palindromes;
 
    // 寻找所有长度为2或3的回文子串 
    for (int i = 0; i < n; ++i) {
        // 检查长度为2的回文 
        if (i + 1 < n && s[i] == s[i+1]) {
            palindromes.emplace_back(i, i+1);
        }
        // 检查长度为3的回文 
        if (i + 2 < n && s[i] == s[i+2]) {
            palindromes.emplace_back(i, i+2);
        }
    }
 
    // 检查是否存在两个互不重叠的回文子串 
    for (size_t i = 0; i < palindromes.size(); ++i) {
        int a1 = palindromes[i].first + 1; // 转换为1-based索引 
        int b1 = palindromes[i].second + 1;
        for (size_t j = i + 1; j < palindromes.size(); ++j) {
            int a2 = palindromes[j].first + 1;
            int b2 = palindromes[j].second + 1;
            if (b1 < a2) { // 确保区间不重叠 
                cout << "YES" << endl;
                cout << a1 << " " << b1 << " " << a2 << " " << b2 << endl;
                return 0;
            }
        }
    }
 
    // 如果没有找到，则输出NO 
    cout << "NO" << endl;
    return 0;
}

题目内容

米小游有一个长度为 $n$ 的字符串 $s$ ，下标从 $1$ 开始。

定义对一个区间 $[l,r]$ 执行翻转操作为将原来的

$s_ls_{l+1}s_{l+2}...s_{r-1}s_r$变为$s_rs_{r-1}...s_{l-1}s_l$。

她现在准备选定 $4$ 个 整数 $a,b,c,d(1≤a＜b＜c＜d≤n)$，然后先对区间 $[a,b]$ 执行翻转操作，然后再对区间 $[c,d]$ 执行翻转操作。如果操作完成之后，现在的字符串和初始字符串能够保持相同，输出 “$YES$”，然后输出这样的 $4$ 个整数，若有多组解，输出任意一个满足条件的解。否则输出“$NO$ ”。

输入描述

第一行一个整数 $n (1≤n≤10^5)$，表示字符串长度。

第二行一个长度为 $n$ 的字符串 $s$，保证输入仅由小写字母组成。

输出描述

若可以满足题意，第一行输出“ $YES$ ”，第二行输出 $4$ 个整数，代表 $a,b,c,d$，以空格隔开，若有多组解，输出任意一个。

若不能，输出“ $NO$ ”

样例1

输入

4
abcd

输出

NO

样例2

输入

13
abbagggfkfggc

输出

YES
1 4 6 12