题目链接

删得回文串

题目描述

给定一个由小写字母构成的字符串。Alice 和 Bob 轮流进行操作，Alice 先手。每次操作，玩家可以从当前字符串中删除任意一个字符。如果删除后，新形成的字符串能够通过重排字符构成一个回文串，则执行该操作的玩家获胜。如果不能，则游戏继续，轮到对方操作。假设双方都采取最优策略，判断谁将获胜。

解题思路

这是一个博弈论问题。解题的关键是找到决定胜负的关键状态量。

首先，一个字符串能被重排为回文串，当且仅当字符串中最多只有一种字符出现了奇数次。 我们可以定义一个关键指标 ，表示字符串中出现奇数次的字符种类的数量。一个玩家获胜，就是通过自己的操作，使得新字符串的 。

根据题目给出的博弈过程和最优策略假设，我们可以通过分析 值的变化规律来判断胜负。最终的胜负关系可以总结为以下规律：

  • 情况一： 此时字符串本身已经可以重排为回文串（例如 "aabb"）。但规则要求玩家必须操作。Alice 删除任意一个字符，都会使新字符串的 。Alice 执行了制胜操作，因此 Alice 获胜。

  • 情况二： 当游戏进行时，胜负手与 的奇偶性相关。

    • 如果初始的 是奇数，Alice 作为先手，拥有主动权。她总能通过操作将局面交给一个 为偶数的状态给 Bob。在这种轮换中，Alice 始终占据优势。因此，Alice 获胜。
    • 如果初始的 是偶数，Alice 无论如何操作，都会将一个 为奇数的状态交给 Bob。此时 Bob 取得了优势地位。因此，Bob 获胜。

最终结论： 将以上情况合并，我们可以得到最终的判断规则：

  • 如果初始的 或 是奇数，则 Alice 获胜。
  • 如果初始的 是大于 0 的偶数，则 Bob 获胜。

代码

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    string s;
    cin >> s;

    map<char, int> counts;
    for (char c : s) {
        counts[c]++;
    }

    int odd_count = 0;
    for (auto const& [key, val] : counts) {
        if (val % 2 != 0) {
            odd_count++;
        }
    }

    if (odd_count == 0 || odd_count % 2 != 0) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        int odd_count = 0;
        for (int count : counts.values()) {
            if (count % 2 != 0) {
                odd_count++;
            }
        }

        if (odd_count == 0 || odd_count % 2 != 0) {
            System.out.println("Alice");
        } else {
            System.out.println("Bob");
        }
    }
}

from collections import Counter

def solve():
    s = input().strip()
    if not s:
        return

    counts = Counter(s)
    
    odd_count = 0
    for count in counts.values():
        if count % 2 != 0:
            odd_count += 1
    
    if odd_count == 0 or odd_count % 2 != 0:
        print("Alice")
    else:
        print("Bob")

solve()

算法及复杂度

  • 算法：计数、博弈论
  • 时间复杂度：我们需要遍历一次字符串来统计字符频率，然后遍历一次频率表。总时间复杂度为 ，其中 是字符串长度， 是字符集大小（本题中为 26）。由于 是常数，时间复杂度可简化为 。
  • 空间复杂度：需要一个大小为 的数组来存储字符频率，因此空间复杂度为 ，即 。