自动搬运

查看原文

来自洛谷，原作者为

	xiangxiyu **

搬运于2025-08-24 23:00:48，当前版本为作者最后更新于2024-07-19 11:34:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

$10$ 可以走一步，$100$，$110$，$1010$ 可以走两步，所以只要最后留一步或两步，就赢了，所以 $\texttt{Alice}$ 要保证她走完后要留三步或四步，所以只要 $\texttt{Alice}$ 每次都走到 $3k+1$，$3k+2$ 的位置就可以保证能赢，我们会发现总步数是开始序列中逆序对的个数。

举例证明

$100$ 反转后为 $001$，$100$ 有两个逆序对，反转就相当于走了两步，$10$ 有一个逆序对，反转后就为 $01$ 相当于走了一步，最后时答案肯定是连续的 $0$ 连着连续的 $1$，逆序对个数为 $0$，我们只需要统计一下原序列中逆序对的个数，看一下能不能被 $3$ 整除就好了。

提示

逆序对个数最大为长度的平方，要开 long long。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans = 0,k = 0;
signed main() {
    string a;
    cin >> a;
    int n = a.size();
    for (int i=0;i<n;i++){
        if (a[i] == '1')  k++;
	else ans += k;//统计逆序对个数
    }
    if(ans%3!=0) cout<<"Alice";//不能整除 Alice赢
    else cout<<"Bob";//整除 Bob赢
    return 0;
}