2021牛客暑期多校训练营1

Alice and Bob

#include<iostream>
#include<cstring>

using namespace std;

const int N=5010;

int t;
int n,m;
bool f[N][N];

int main(){
//    for(int i=0;i<=5000;i++)
//        for(int j=0;j<=5000;j++){
//            if(!f[i][j]){
//                for(int k=1;k+i<=5000;k++)
//                    for(int s=0;j+s*k<=5000;s++)
//                        f[i+k][j+k*s]=1;
//                for(int k=1;k+j<=5000;k++)
//                    for(int s=0;i+s*k<=5000;s++)
//                        f[i+s*k][k+j]=1;
//            }
//        }    
    for(int i=0;i<=5000;i++)
        for(int j=0;j<=5000;j++){
            if(!f[i][j]){
                for(int k=1;i+k<=5000;k++)
                    for(int s=0;j+s*k<=5000;s++)
                        f[i+k][j+s*k]=1;
                for(int k=1;j+k<=5000;k++)
                    for(int s=0;i+s*k<=5000;s++)
                        f[i+s*k][j+k]=1;
        }
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        if(f[n][m])    puts("Alice");
        else    puts("Bob");
    }
} 

Hash Function

#include<iostream>
#include<map>
#include<algorithm>

using namespace std;

const int N=500010;

int n;
int a[N];
map<int,int> mp;

int head=1;

bool check(int x){
    while(a[head]<x){
        mp[a[head]%x]=1;
        ++head;
    }
    for(int i=head;i<=n;i++){
        if(!mp[a[i]%x])    mp[a[i]%x]=1;
        else{
            for(int j=head;j<i;j++)    mp[a[j]%x]=0;
            return false;
        }
    }
    return true;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=n;;i++){
        if(check(i)){
            printf("%d",i);
            break;
        }
    }
}