在某一国度里流行着一种游戏。游戏规则为:现有一堆球中,每个球上都有一个整数编号i(0<=i<=100000000),编号可重复,还有一个空箱子,现在有两种动作:一种是”ADD”,表示向空箱子里放m(0<m<=100)个球,另一种是”QUERY”,表示说出M(0<M<=100)个随机整数ki(0<=ki<=100000100),分别判断编号为ki 的球是否在这个空箱子中(存在为”YES”,否则为”NO”),先答出者为胜。现在有一个人想玩玩这个游戏,但他又很懒。他希望你能帮助他取得胜利。

输入
第一行有一个整数n(0<n<=10000);
随后有n行;
每行可能出现如下的任意一种形式:
第一种:
一个字符串”ADD”,接着是一个整数m,随后有m个i;
第二种:
一个字符串”QUERY”,接着是一个整数M,随后有M个ki;

输出
输出每次询问的结果”YES”或”NO”.
样例输入

2
ADD 5 34 343 54 6 2
QUERY 4 34 54 33 66

样例输出

YES
YES
NO
NO
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e8+5;
const int fib =9191891;
int Key[maxn],Head[maxn],Next[maxn];
int top=0;
void add(int n){
    int temp=n%fib;
    Key[top]=n;
    Next[temp]=Head[temp];
    Head[temp]=top;
    top++;
}
int find(int n){
    int temp=n%fib;
    for(int i=Head[n];i!=-1;i=Next[i]){
        if(Key[i]==n){
            return 1;
        }
    }
    return 0;
}
int main(){
    int ncase;
    string str;
    int num,number;
    memset(Head,-1,sizeof(Head));
    memset(Key,0,sizeof(Key));
    cin>>ncase;
    while(ncase--){
        cin>>str;
        if(str[0]=='A'){
            cin>>num;
            for(int i=0;i<num;i++){
                cin>>number;
                add(number);
            }
        }
        else{
            cin>>num;
            for(int i=0;i<num;i++){
                cin>>number;
                if(find(number)){
                    printf("yes\n");
                }else{
                    printf("no\n");
                }
            }

        }
    }
    system("pause");
    return 0;
}

61,  83,  113, 151,  211, 281,   379,  509  683,  911     /  一千以下 

1217,  1627,  2179,  2909,  3881,  6907,  9209,   /一万以下   

12281,  16381,  21841, 29123, 38833, 51787,  69061, 92083,       /十万以下

122777, 163729, 218357,  291143, 388211, 517619, 690163, 999983,    /百万以下

1226959,   1635947,   2181271,   2908361,   3877817,   5170427,   6893911,   9191891,  /千万以下

12255871, 16341163, 21788233, 29050993, 38734667, 51646229,68861641,  91815541,/一亿以下

1e9+7 和 1e9+9 //十亿左右

122420729,163227661,217636919,290182597,386910137,515880193,687840301,917120411,/十亿以下

1222827239,1610612741, 3221225473ul, 4294967291ul                                                       /十亿以上

发表评论

电子邮件地址不会被公开。 必填项已用*标注