题解：P12530 [XJTUPC 2025] 公道杯

· · 题解

思路

一眼奇偶性。

发现初始杯子只有空和半满两种状态。

从右往左遍历，如果该杯子半满，将其向右倒直到倒掉，记总共倒的次数为 ans。

回到题目，如果两个杯子的酒倒在了一起，则这个杯子会变空，相较于上面的情况，记该杯距最右侧（最后一个杯子的右边）的距离为 k，总共倒的次数会减少 2k。

发现 ans 的奇偶性不变。

易知若 ans 为奇数，则最后一次操作是 Alice 完成的，Alice 必胜，反之 Bob 必胜。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
long long ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='H') ans+=s.size()-i;   //统计 ans
    }
    if(ans%2) cout<<"Alice";
    else cout<<"Bob";
    return 0;  //完结撒花
}