当前位置:网站首页>Alice and Bob (2021牛客暑期多校训练营1)
Alice and Bob (2021牛客暑期多校训练营1)
2022-07-06 09:25:00 【是小张张呀 zsy】
Alice and Bob
2021牛客暑期多校训练营1第一题,当时没做出来,看了这个博主的博客,瞬间懂了
题目链接:https://ac.nowcoder.com/acm/contest/11166/A
来源:牛客网
题目描述
Alice and Bob like playing games. There are two piles of stones with numbers n and m. Alice and Bob take turns to operate, each operation can take away k(k>0) stones from one pile and take away 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≤10^4 ) denotes the total number of test cases.
Each test case contains two integers n,m(1≤n,m≤5×10^ 3) 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
题目大意:
两人博弈,每次一个人从一堆中拿走一个,同时从另一堆中拿走k*s个,问能谁先不能拿;
思路:
枚举,暴力,其实思路还是很简单的,如果能一次操作能取光石头此时为必胜态,我们用一个二维数组f[i][j]来表示第一堆石头数量为i第二堆石头数量为j的情况,f[i][j]=1表示状态面临两堆石头数量为i,j时可以一步取光石头,f[i][j]=0表示状态面临两堆石头数量为i,j时无法一次取光石头。根据题目f[k][sk]或f[sk][k]一定能够一次性取完,所以枚举s与k找出所有先手必胜的状态
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
bool f[5001][5001];
int main()
{
for(int i=0;i<=5000;i++)
{
for(int j=0;j<=5000;j++)
{
if(f[i][j]==0)
{
for(int k=1;k+i<=5000;k++)
{
for(int s=0;s*k+j<=5000;s++)
f[i+k][j+s*k]=1;
}
for(int k=1;k+j<=5000;k++)
{
for(int s=0;s*k+i<=5000;s++)
f[i+s*k][j+k]=1;
}
}
}
}
int t,n,m;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
if(f[n][m]==0)
cout<<"Bob"<<endl;
else
cout<<"Alice"<<endl;
}
}
边栏推荐
- C语言学习笔记
- Research Report on market supply and demand and strategy of Chinese hospital cleaning chemicals industry
- Automated testing problems you must understand, boutique summary
- csapp shell lab
- How to write the bug report of software test?
- cs零基础入门学习记录
- Hospital privacy screen Industry Research Report - market status analysis and development prospect forecast
- How to change XML attribute - how to change XML attribute
- Intensive learning notes: Sutton book Chapter III exercise explanation (ex17~ex29)
- LeetCode#198. raid homes and plunder houses
猜你喜欢
Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
STM32学习记录:玩转按键控制蜂鸣器和LED
Do you know the performance testing terms to be asked in the software testing interview?
Leetcode notes - dynamic planning -day7
STM32学习记录:输入捕获应用
Learning record: USART serial communication
STM32 learning record: input capture application
12306: mom, don't worry about me getting the ticket any more (1)
ucore lab7
学习记录:TIM—电容按键检测
随机推荐
LeetCode#36. Effective Sudoku
Es6---es6 content details
0 - 1 problème de sac à dos (1)
Medical colposcope Industry Research Report - market status analysis and development prospect forecast
Market trend report, technical innovation and market forecast of geosynthetic clay liner in China
FSM and I2C experiment report
Visual analysis of data related to crawling cat's eye essays "sadness flows upstream into a river" | the most moving film of Guo Jingming's five years
China's earthwork tire market trend report, technical dynamic innovation and market forecast
Record of force deduction and question brushing
Report on the market trend, technological innovation and market forecast of printing and decorative paper in China
Cost accounting [21]
学习记录:TIM—电容按键检测
Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
Cost accounting [17]
How to write the bug report of software test?
LeetCode#62. Different paths
JS --- all knowledge of JS objects and built-in objects (III)
Research Report on market supply and demand and strategy of geosynthetics industry in China
Research Report on market supply and demand and strategy of China's land incineration plant industry
Research Report on market supply and demand and strategy of Chinese hospital cleaning chemicals industry