#include <iostream>

using namespace std;

bool is_prime(int n){
    if(n <= 1) return false;
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0) return false;
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n ; i ++){
        int a;
        cin >> a;
        cout << (is_prime(a) ? "Yes" : "No") << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010, M = N * 31;

int n, idx, a[N], son[M][2];

void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i--){
        int s = son[p][x >> i & 1];
        if(!s) son[p][x >> i & 1] = ++ idx;
        p = son[p][x >> i & 1];
    }
}

int query(int x){
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--){
        int s = x >> i & 1;
        if(son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }else
            p = son[p][s];
    }
    return res;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        insert(a[i]);
    }

    int res = 0;
    for(int i = 0;i < n; i++){
        res = max(res, query(a[i]));
    }

    cout << res << endl;
    return 0;
}

#include <iostream>
#include <cstring>


using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;

void init(){
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

void insert(int k, int x){
    e[idx] = x;
    l[idx] = k, r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx ++;
}

void del(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(){
    cin >> m;
    init();
    while(m --){
        string op;
        int k, x;
        cin >> op;
        if(op == "L"){
            cin >> x;
            insert(0, x);
        }else if(op == "R"){
            cin >> x;
            insert(l[1], x);
        }else if(op == "D"){
            cin >> k;
            del(k + 1);
        }else if(op == "IL"){
            cin >> k >> x;
            insert(l[k + 1], x);
        }else{
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for(int i = r[0]; i != 1; i = r[i]){
        cout << e[i] << " ";
    }

    return 0;

}

#include <iostream>

using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
int h[N], p[N];
char str[N];

ULL get(int x, int y){
    return h[y] - h[x - 1] * p[y - x + 1];
}


int main(){
    cin >> n >> m;
    scanf("%s", str + 1);

    p[0] = 1;
    for(int i = 1; i <= n; i++){
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }

    while(m --){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

拉链法

#include <iostream>
#include <cstring>

using namespace std;
const int N = 100003;//大于10的5次方的第一个质数，在hash中模上质数产生哈希冲突的概率小
int n;
int h[N], e[N], ne[N], idx;

void insert(int x){
    int k = (x % N + N) % N;
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}

bool find(int x){
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i]){
        if(e[i] == x)
            return true;
    }
    return false;
}


int main(){
    cin >> n;
    char op[10];
    int x;
    memset(h, -1, sizeof h);
    while(n--){
        scanf("%s%d", op, &x);
        if(*op == 'I'){
            insert(x);
        }else{
            if(find(x)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

开放寻址法

···

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
const int N = 200003/开放寻址法数组大小通常要开到数据范围的2倍/, null = 0x3f3f3f3f;
int h[N];
int find(int x){
int k = (x % N + N) % N;

while(h[k] != null && h[k] != x){
    k++;
    if(k == N) k = 0;
}

return k;

}

int main(){
int n;
cin >> n;
memset(h, 0x3f, sizeof h);
while(n –){
char op[2];
int x;
scanf(“%s%d”, op, &x);
int k = find(x);
if(*op == ‘I’){
h[k] = x;
}else{
if(h[k] != null) cout << “Yes” << endl;
else cout << “No” << endl;
}
}
return 0;
}
···

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int n, hh = 0, tt = -1;
int q[N];

void push(int x){
    q[++ tt] = x;
}

void pop(){
    hh++;
}

bool empty(){
    return hh > tt;
}

int query(){
    return q[hh];
}


int main(){
    cin >> n;
    char op[10];
    int x;
    while(n --){
        cin >> op;
        if(!strcmp(op, "push")){
            cin >> x;
            push(x);
        }else if(!strcmp(op, "pop")){
            pop();
        }else if(!strcmp(op, "empty")){
            cout << (empty() ? "YES" : "NO") << endl;
        }else {
            cout << query() << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;
const int N = 100010;
int s[N];
int n, tt = -1;

void push(int x){
    s[++ tt] = x;
}

void pop(){
    tt--;
}

bool empty(){
    return tt == -1;
}

int query(){
    return s[tt];
}


int main(){
    cin >> n;
    char op[10];

    int x;
    while(n --){
        cin >> op;
        if(!strcmp(op, "push")){
            cin >> x;
            push(x);
        }else if(!strcmp(op, "pop")){
            pop();
        }else if(!strcmp(op, "empty")){
            cout << (empty() ? "YES" : "NO") << endl;
        }else{
            cout << query() << endl;
        }
    }


    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int h[N], ph[N], hp[N], cnt;

void heap_swap(int x, int y){
    swap(ph[hp[x]], ph[hp[y]]);
    swap(hp[x], hp[y]);
    swap(h[x], h[y]);
}

void down(int u){
    int t = u;
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        heap_swap(u, t);
        down(t);
    }
}

void up(int u){
    while(u / 2 && h[u / 2] > h[u]){
        heap_swap(u / 2, u);
        u /= 2;
    }
}

int main(){
    int n, m = 0;
    cin >> n;
    while(n--){
        char op[5];
        cin >> op;
        int k, x;
        if(!strcmp(op, "I")){
            cin >> x;
            cnt++;
            m++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }else if(!strcmp(op, "PM")){
            cout << h[1] << endl;
        }else if(!strcmp(op, "DM")){
            heap_swap(1, cnt);
            cnt--;
            down(1);
        }else if(!strcmp(op, "D")){
            cin >> k;
            k = ph[k];
            heap_swap(k, cnt);
            cnt --;
            down(k), up(k);
        }else{
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m;
int h[N], cnt;

void down(int u){
    int t = u;
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(t != u){
        swap(h[t], h[u]);
        down(t);
    }

}


int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> h[i];
    cnt = n;
    for(int i = n / 2; i; i--) down(i);
    while(m --){
        cout << h[1] << " ";
        h[1] = h[cnt --];
        down(1);
    }

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> s[i];
        for(int j = 0; j < s[i]; j++){
            cin >> v[i][j] >> w[i][j];
        }
    }

    //枚举数量
    for(int i = 1; i <= n; i++){
        //枚举体积
        for(int j = m; j >= 0; j--){
            //枚举物品数
            for(int k = 0; k < s[i]; k++){
                if(v[i][k] <= j){
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }

    cout << f[m] << endl;
    return 0;

}