[牛客|补题] 2021牛客暑期多校训练营1

目录

• 前言
• A.Alice and Bob
• • 思路
  • code
• G.Game of Swapping Numbers
• H.Hash Function

前言

学了挺多了,感觉可以给这个系列来一个补题了

• 比赛时做出: BDF
• 预计补题 : AHG

A.Alice and Bob

思路

从f[0][0] 开始对于每一个能 扩展到的地方f[i+k][j+s·k]&&f[i+s·k][j+k] 枚举出必胜态

因为石子个数(<=5000) 因此O （n^3） 勉强可以过去

code

#include<iostream>
#include<stdio.h>
using namespace std;
bool f[5001][5001];
int main()
{
    for(int i=0; i<=5000; i++) //自小到大枚举i，j
        for(int j=0; j<=5000; j++)
        {
            if(f[i][j]==0)//对于每种必败态进行拓展
            {
                //f[i][j]与f[j][i]是等价的
                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)
        {
            puts("Bob");
        }
        else
            puts("Alice");
    }
    return 0;
}
           

G.Game of Swapping Numbers

H.Hash Function