解题思路

题目要求计算将字符串中的子串"xy"替换成"yx"，最少需要多少次操作才能让字符串中不存在"xy"。

关键发现：

  1. 每次替换"xy"为"yx"，相当于将x向右移动一位
  2. 对于每个x，需要统计其右侧有多少个非x字符
  3. 最终答案需要对 取模

解题思路：

  1. 从左到右遍历字符串
  2. 遇到 'x' 时，更新当前 x 的贡献：
  3. 遇到其他字符时，将当前累积的 x 的贡献加到总和：

代码

#include <iostream>
using namespace std;

const int MOD = 1000000007;

int main() {
    string s;
    cin >> s;
    
    long long n = 0;  // 总替换次数
    long long m = 0;  // 当前x的贡献
    
    for (char c : s) {
        if (c == 'x') {
            m = (2 * m + 1) % MOD;
        } else {
            n = (n + m) % MOD;
        }
    }
    
    cout << n << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        long n = 0;  // 总替换次数
        long m = 0;  // 当前x的贡献
        
        for (char c : s.toCharArray()) {
            if (c == 'x') {
                m = (2 * m + 1) % MOD;
            } else {
                n = (n + m) % MOD;
            }
        }
        
        System.out.println(n);
    }
}

MOD = 1000000007

s = input()
n = 0  # 总替换次数
m = 0  # 当前x的贡献

for c in s:
    if c == 'x':
        m = (2 * m + 1) % MOD
    else:
        n = (n + m) % MOD

print(n)

算法及复杂度

  • 算法：动态规划（状态压缩）
  • 时间复杂度： - 为字符串长度，只需要遍历一次字符串
  • 空间复杂度： - 只使用了常数个变量