A - Alice and Bob

2024-01-28 15:58
文章标签 alice bob

本文主要是介绍A - Alice and Bob,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Alice and Bob

题目描述

Alice and Bob like playing games. There are two piles of stones with numbers n{n}n and m{m}m. Alice and Bob take turns to operate, each operation can take away k(k>0){k}(k>0)k(k>0) stones from one pile and take away s×k(s≥0)s \times k(s \geq 0)s×k(s≥0) stones from another pile. Alice plays first. The person who cannot perform the operation loses the game. 

Please determine who will win the game if both Alice and Bob play the game optimally.

输入描述:

The first line contains an integer T(1≤T≤104)T(1 \le T \le 10^4)T(1≤T≤104) denotes the total number of test cases.
Each test case contains two integers n,m(1≤n,m≤5×103)n,m(1 \le n,m \leq 5 \times 10^3)n,m(1≤n,m≤5×103) in a line, indicating the number of two piles of stones.

输出描述:

For each test case, print "Alice" if Alice will win the game, otherwise print "Bob".

示例1

输入

复制

5
2 3
3 5
5 7
7 5
7 7

输出

复制

Bob
Alice
Bob
Bob
Alice

思路:题意为当Alice操作完之后就没有了就是Alice赢。将两堆看作一个二维数组,所以我们记录下Alice赢的情况,标记为1,注意可以先取堆A,也可先取堆B。sg函数(虽然我也不太懂,hhh),此处用dp[N]][N]表示,初始化为0,即必输的状态。然后暴力枚举赢的状态,标记为1.

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define N 5010
bool dp[N][N];//为1即Alice win
int t,n,m;
int main(){
    //暴力打表 hhh
    for(int i=0;i<=5000;i++)
    for(int j=0;j<=5000;j++){
            if(!dp[i][j]){
                //暴力枚举Alice必赢的情况
                for(int k=1;i+k<=5000;k++)//先取堆A:i,再取堆B :j
                for(int s=0;j+k*s<=5000;s++)
                dp[i+k][j+k*s]=1;
                    
                
                for(int k=1;j+k<=5000;k++)//先取堆B:j,再取堆A:i
                for(int s=0;i+k*s<=5000;s++)
                dp[i+s*k][j+k]=1;
        }
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        if(dp[n][m]) printf("Alice\n");
        else printf("Bob\n");
    }
    return 0;
}

这篇关于A - Alice and Bob的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/654103

相关文章

杨bob的技术之旅

杨bob今天正式入驻csdn,以后要把自己每一点滴写成文章,这也是冲高阶的毕竟之路

XTOJ 1168 Alice and Bob (记忆化搜索)

OJ题目 : click here ~~ 题意分析:给一个数n,Alice可取1,2 , 4 ……2的i次方 ,Bob可取1,3,9……3的i次方。Alice先取,后Bob。轮流来,每个人至少取1。求n变成0,至少需要取多少次。记忆化搜索 = 搜索 + dp 。 AC_CODE #define gril 0#define boy 1using namespace std;const

Leetcode 3273. Minimum Amount of Damage Dealt to Bob

Leetcode 3273. Minimum Amount of Damage Dealt to Bob 1. 解题思路2. 代码实现 题目链接:3273. Minimum Amount of Damage Dealt to Bob 1. 解题思路 这一题代码并不复杂,关键就是想明白为啥。 我直接的一个思路就是贪婪算法,考察任意两个怪 i , j i, j i,j之间处理的先后关系,其结果

[H贪心] lc3273. 对 Bob 造成的最少伤害(贪心+排序+推公式+双周赛138_4)

文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接:3273. 对 Bob 造成的最少伤害 题单: na na 2. 题目解析 略低于正常难度的 T4。 显然我们应该尽可能的将伤害高的先消掉,然后写完代码就会发现 WA 了。想太简单了,那就推推公式看看怎么回事吧。这里直接贴一下 蛙佬 的题解吧。简洁移动,也很容易能发现这个。 来自: 作者:TsRea

hdu4111 Alice and Bob 博弈论

题意:有N堆石子,每堆石子有一个数目,现有两个人博弈,每个人每次可以进行两个操作中的一个: 1、从某堆拿掉一个石子(若某堆石子为0了,那么这堆就不存在了);2、合并两堆石子 没有操作的就输。问是哪个赢 统计1的个数c,以及非1情况下的步数s,包括合并。 c为奇数,s不等于2:那么先手必胜。 s为2或者为0:c为3的倍数是先手必败。 否则的话,s为奇数时先手必胜。 首先没有1的情况下很好证明,就是

hdu5208 Where is Bob 数位dp

维护四个数的上下边界条件,转移使最小值最大即可。 数位dp有时只对dp赋一次-1,这时边界条件满足一定条件与后面的数是什么无关,可以直接返回,在此题中条件太苛刻,用处不大,会tle。 也可以每次都赋一次-1,这时算出一个状态的值就能赋给dp,再次用到时直接返回。 #include<iostream>#include<cstdio>#include<cmath>#include<al

XTU 1185 Bob's Problem

Bob's Problem Accepted : 53 Submit : 356Time Limit : 1000 MS Memory Limit : 65536 KB 题目描述 Bob今天碰到一个问题,他想知道x3+y3 = c 是否存在正整数解? 输入 第一行是一个整数K(K≤20000),表示样例的个数。 以后每行一个整数c(2≤c≤109) 输出 每行输出一个样例的结果,

贪心+构造,CF 1592F1 - Alice and Recoloring 1

目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 1592F1 - Alice and Recoloring 1 二、解题报告 1、思路分析

【递归+二叉树思想+搜索】 Alice and the Cake题解

Alice and the Cake题解 AC记录:记录-洛谷 题面翻译(大概就是题目大意) 执行恰好 n − 1 n-1 n−1 次操作,每次操作可以选择当前所有蛋糕中满足其重量 w ⩾ 2 w\geqslant 2 w⩾2 的一块,然后将其分为质量分别为 ⌊ w 2 ⌋ \lfloor\dfrac w2\rfloor ⌊2w​⌋ 和 ⌈ w 2 ⌉ \lceil\dfrac

POJ 1704 Georgia and Bob题解

【题目大意】:    一个很长的格子列上有N 个棋子,开始位置一定,两人轮流操作(Georgia先手),每次移动一枚棋子,要求只能向左移且至少移动一格,而且不能越过任何棋子,最后谁无法移动棋子谁就输。 【分析】:    我们考虑从后往前将棋子两两配对(若N为奇数则想象有一个棋子放在第0号位置,将第一个棋子与其配对即可)。这样我们考虑:游戏的最终目的是将任意两棋间间距变为0。若先手移动了某对