AcWing 4875. 整数游戏 - AcWing

AcWing 4875. 整数游戏原题链接困难

作者：

炽热的 , 2023-03-18 20:15:15 , 所有人可见 , 阅读 952

29

3

最小值是最快变成 $0$ 的，如果第一个元素是最小值则先手必败，否则后手必败

若`第一个元素`是`最小值`且不是 $0$ (是 $0$ 直接输了，没必要讨论)：

则先手 $Alice$ 减 $1$ 后，不管与谁交换值，交换后都比之前大，由于第一个元素不是 $0$ , 所以交换后轮到 $Bob$ 也必然不是 $0$。而 $Bob$ 只需要做一件事，不断将最小值扔回给 $Alice$ ，则 $Alice$ 必然最先达到 $0$，必败。

若第一个元素不是最小值

则 $Alice$ 在减 $1$ 后，直接选择最小值扔给 $Bob$，转变为 $Bob$ 先手拿到最小值，则转变上面那种情况，必败。

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

void solve() {
    scanf("%d", &n);
    int minv = 2e9;
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        if (a[i] < minv) minv = a[i];
    }
    puts(a[1] == minv ? "Bob" : "Alice");
}

int main() {
    int _; scanf("%d", &_);
    while (_ -- ) solve();
    return 0;
}

16 评论

理论_都是理论 2个月前

回复

啊，头好痛，好像要长脑子了

Yuzhao_Li 2个月前

回复

好强瞬间理解了 orz 直击重点爱了爱了

szh_2003 2个月前

回复

我当时写的时候一点没思考，看样例猜出来的，运气好过了。

炽热的 2个月前

回复

能猜出来也是实力

上海STYLE 2个月前

回复

强的，我一开始以为是博弈就用异或乱搞……

上海STYLE 2个月前

回复

好神奇的变量名（关注点错）

炽热的 2个月前

回复

哈哈哈哈

人生啊人生 2个月前

回复

为什么令N=1e5 + 10？

炽热的 2个月前

回复

因为习惯

NinoNeumannFeuerbach 2个月前

回复

orz

_mayiwei 2个月前

回复

第一次觉得自己没有智商

炽热的 2个月前

回复

可能是看到以为是博弈被吓跑了

上海STYLE 2个月前

回复

我其实觉得这个东西和智商没啥关系……感觉是如果以前接触过类似的问题才会往这个方向去想，否则确实是打死也想不出来……

_mayiwei 2个月前回复了炽热的的评论

回复

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e8+5;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int c,x,ans,flag=1;
        cin>>c;
        ans=c;
        for(int i=2;i<=n;i++){
            cin>>x;
            if(x&1==1)ans=min(ans,x);
        }
        if(n==2){
            if(c<=ans)puts("Bob");
            else puts("Alice");
        }else
        if(c<=ans)puts("Bob");
        else puts("Alice");
    }
    return 0;
}

_mayiwei 2个月前回复了炽热的的评论

回复

加了一些没用的特判666

星河依旧长明 2个月前回复了 _mayiwei 的评论

回复

666