当前位置:网站首页>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;
}
}
边栏推荐
- Indonesian medical sensor Industry Research Report - market status analysis and development prospect forecast
- Learning record: use stm32f1 watchdog
- Research Report on printed circuit board (PCB) connector industry - market status analysis and development prospect forecast
- Crawler series of learning while tapping (3): URL de duplication strategy and Implementation
- Cost accounting [15]
- Cost accounting [13]
- ucore lab 6
- CSAPP shell lab experiment report
- ucore Lab 1 系统软件启动过程
- Research Report on market supply and demand and strategy of geosynthetics industry in China
猜你喜欢
LeetCode#62. Different paths
Learning record: USART serial communication
ucore lab 6
毕业才知道IT专业大学生毕业前必做的1010件事
FSM和i2c实验报告
51 lines of code, self-made TX to MySQL software!
Do you know the advantages and disadvantages of several open source automated testing frameworks?
MATLAB实例:阶跃函数的两种表达方式
C4D quick start tutorial - creating models
How to write the bug report of software test?
随机推荐
LeetCode#268. Missing numbers
0-1背包問題(一)
ucorelab4
Cost accounting [14]
Cost accounting [13]
Accounting regulations and professional ethics [2]
Cost accounting [23]
Learning record: use stm32f1 watchdog
Indonesian medical sensor Industry Research Report - market status analysis and development prospect forecast
Cost accounting [13]
学习记录:TIM—电容按键检测
Interview answering skills for software testing
Cost accounting [21]
Cost accounting [14]
Research Report on medical anesthesia machine industry - market status analysis and development prospect prediction
Automated testing problems you must understand, boutique summary
STM32 learning record: input capture application
Jupyter installation and use tutorial
Research Report on market supply and demand and strategy of China's Medical Automation Industry
UCORE LaB6 scheduler experiment report