fzu 2275 Game

2024-04-01 19:18
文章标签 game fzu 2275

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

Problem 2275 Game

Accept: 18    Submit: 56
Time Limit: 1000 mSec    Memory Limit : 262144 KB

Problem Description

Alice and Bob is playing a game.

Each of them has a number. Alice’s number is A, and Bob’s number is B.

Each turn, one player can do one of the following actions on his own number:

1. Flip: Flip the number. Suppose X = 123456 and after flip, X = 654321

2. Divide. X = X/10. Attention all the numbers are integer. For example X=123456 , after this action X become 12345(but not 12345.6). 0/0=0.

Alice and Bob moves in turn, Alice moves first. Alice can only modify A, Bob can only modify B. If A=B after any player’s action, then Alice win. Otherwise the game keep going on!

Alice wants to win the game, but Bob will try his best to stop Alice.

Suppose Alice and Bob are clever enough, now Alice wants to know whether she can win the game in limited step or the game will never end.

Input

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: Two number A and B. 0<=A,B<=10^100000.

Output

For each test case, if Alice can win the game, output “Alice”. Otherwise output “Bob”.

Sample Input

411111 11 1111112345 54321123 123

Sample Output

AliceBobAliceAlice 



核心是kmp。。。。。




#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char a[1111111];
char b[1111111];
int next[1111111];
int la,lb;
void getn()
{
int i=0,j;  
    j=next[0]=-1;  
    for(i=0;i<lb;)  
    {  
        if(j==-1||b[i]==b[j])  
            next[++i]=++j;  
        else
            j=next[j];  
    }  
}
bool kmp()
{
getn();  
    int i=0,j=0;  
    for(i=0;i<la;)  
    {  
        if(j==-1||a[i]==b[j])  
        {  
            i++;  
            j++;  
        }  
        else  
            j=next[j];  
        if(j>=lb)  
            return 1;  
    }  
    if(j>=lb)  
        return 1;  
    return 0;  
}
int main() {
int T;
cin>>T;
while(T--)
{
cin>>a>>b;
la=strlen(a);
lb=strlen(b);
int i,j;
int flag=1;
for(i=0;i<lb;i++)
{
if(b[i]=='0')continue;
flag=0;break;
}
for(i=lb-1;i>=0;i--)
if(b[i]=='0')b[i]='\0';
else break;
if(flag==1||kmp())
{
cout<<"Alice"<<endl;
}
else {
reverse(b,b+lb);
if(kmp())
cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
}

}
return 0;
}


这篇关于fzu 2275 Game的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

fzu 2277 Change 线段树

Problem 2277 Change Time Limit: 2000 mSec    Memory Limit : 262144 KB  Problem Description There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.

fzu 2275 Game KMP

Problem 2275 Game Time Limit: 1000 mSec    Memory Limit : 262144 KB  Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i

10400 -Game Show Math

这道题的话利用了暴力深搜,尽管给了20S,但是这样还会超时,所以就需要利用回溯进行减枝,因为是DFS,所以用一个数组vis[i][j]记录是否在状态i时候取到过j值,如果取到过的话,那么直接回溯(往后搜索已经没有意义了,之前到达这个状态的时候是无法得到结果的) 还有需要注意的地方就是题目的要求,每一步的结构都在(-32000,32000)之间,所以需要一步判断,如果在这个范围外直接回溯 最后一

【FZU】1921 栀子花开 线段树果题

Problem 1921 栀子花开 Accept: 216    Submit: 745 Time Limit: 1000 mSec    Memory Limit : 32768 KB Problem Description 这是一个栀子花开的季节,也是一个离别的季节,四年一千多个日日夜夜,那校园的角角落落,留下了我们沉思的身影;那上百次的成绩排名表,印证了我们深深浅浅不断进步的

【FZU】2171 防守阵地 II 线段树

Problem 2171 防守阵地 II Accept: 96    Submit: 360 Time Limit: 3000 mSec    Memory Limit : 32768 KB Problem Description 部队中总共有N个士兵,每个士兵有各自的能力指数Xi,在一次演练中,指挥部确定了M个需要防守的地点,指挥部将选择M个士兵依次进入指定地点进行防守任务,获得

【POJ】1733 Parity game 并查集

传送门:【POJ】1733 Parity game 题目大意:给你一个长度为n的01序列,再给你m句话,每句话是一个区间【L,R】,告诉你区间【L,R】中1的个数,现在你的任务是找到从第几句话开始说的和前面矛盾,出现第一次假话的时候前面有多少是真话。 题目分析:一开始看几乎没思路啊。后来没办法了,只能跑别人的博客去看看了。。。一看到说把一个区间【L,R】拆成两个区间【0,L-1】,

【FZU】2105 Digits Count 线段树

传送门:【FZU】2105 Digits Count 题目分析:与、或、异或三种操作都是每一位相互独立的,所以可以将线段树建四棵,分别对应一位,and和or操作相当于覆盖操作,xor操作相当于反转操作,就和普通的线段树方法类似,设立两个lazy标记即可。查询的时候求得每一位的1的个数*权重(1,2,4,8),全部累加就是答案。 代码如下: #include <cst

【HDU】5426 Rikka with Game【DP】

题目链接:【HDU】5426 Rikka with Game #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;const int MAXE = 200005 ;

LeetCode 45 Jump Game II

题意: 给出一个步长数组nums,如果一个人站在i这个点上那么他可以向右最多走nums[i]步,求从左端点走到右端点的最少步数。 思路: 如果点x可以用dp[x]步到达,那么[ x + 1, x + nums[x] ]区间内的点都可以用dp[x] + 1步到达。 利用这个想法,可以O(n)的求出走一步可以到达哪些位置,走两步可以到达哪些位置,以此类推。 代码: clas

【论文笔记】Multi-Task Learning as a Bargaining Game

Abstract 本文将多任务学习中的梯度组合步骤视为一种讨价还价式博弈(bargaining game),通过游戏,各个任务协商出共识梯度更新方向。 在一定条件下,这种问题具有唯一解(Nash Bargaining Solution),可以作为多任务学习中的一种原则方法。 本文提出Nash-MTL,推导了其收敛性的理论保证。 1 Introduction 大部分MTL优化算法遵循一个通用方