Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by IntelliJ IDEA.
 * User: zm
 * Date: 2023/5/30
 */
public class Main {
    static int N = 510,n,m,max = 0x3f3f3f;
    static int[][] g = new int[N][N];//存放两点之间的距离
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    public static int dijkstra(){
        Arrays.fill(dist,max);
        dist[1] = 0;
        for(int i = 0; i < n; i++){
            int t = -1;
            for(int j = 1; j <= n; j++){
                if(!st[j] && (t == -1 || dist[j] < dist[t])){
                    t = j;
                }
            }
            st[t] = true;
            for(int j = 1; j <= n; j++){
                dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
            }
        }
        if(dist[n] == max)return -1;
        else return dist[n];
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 1; i <= n; i++) Arrays.fill(g[i],max);

        while(m -- > 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            g[a][b] = Math.min(g[a][b],c);//这个因为可能存在重边，所以泽出最短的
        }
        int res = dijkstra();
        System.out.println(res);
    }
}

Java

import java.util.Scanner;
public class Main{
    static int N = 100010,n,m,hh,tt,idx;
    static int[] e = new int[N],ne = new int[N],h = new int[N];
    static int[] q = new int[N];
    static int[] d = new int[N];
    public static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static boolean bfs(){
        hh = 0; tt = -1;
        for(int i = 1; i <= n; i++){
            if(d[i] == 0){
                q[++tt] = i;
            }
        }
        while(hh <= tt){
            int t = q[hh++];
            for(int i = h[t]; i != -1; i = ne[i]){
                int s = e[i];
                d[s] --;
                if(d[s] == 0){
                    q[++tt] = s;
                }
            }
        }
        return tt == n - 1;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0; i < N; i++){
            h[i] = -1;
        }
        while(m -- > 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            add(a,b);
            d[b]++;
        }
        if(bfs()){
            for(int i = 0; i < n; i++){
                System.out.print(q[i] + " ");
            }
        }else{
            System.out.println("-1");
        }
    }
}

Java

import java.util.Scanner;
public class Main{
    static int N = 100010,n,m,hh,tt,idx;
    static int[] e = new int[N],ne = new int[N],h = new int[N];
    static int[] d = new int[N],q = new int[N];
    public static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static int bfs(){
        hh = 0; tt = -1;
        d[1] = 0;
        q[++tt] = 1;
        while(hh <= tt){
            int t = q[hh++];
            for(int i = h[t]; i!= -1; i = ne[i]){
                int s = e[i];
                if(d[s] == -1){
                    d[s] = d[t] + 1;
                    q[++tt] = s;
                }
            }
        }
        return d[n];
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0; i < N; i++){
            d[i] = -1;
            h[i] = -1;
        }
        for(int i = 0; i < m; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            add(a,b);
        }
        System.out.println(bfs());
    }
}

Java

import java.util.*;
public class Demo42 {
    static int N = 100010,M = N * 2,idx,n;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static boolean[] st = new boolean[N];
    static int ans = N; 
    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static int dfs(int u){
        int res = 0;
        st[u] = true;
        int sum = 1;
        for(int i = h[u];i != -1 ; i = ne[i]){
            int j = e[i];
            if(!st[j]){ 
                int s = dfs(j);
                res = Math.max(res,s); 
                sum += s; 
            }
        }
        res = Math.max(res,n-sum);;
        ans = Math.min(res,ans);
        return sum;
    }
    public static void main(String[] ags){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 1 ; i < N ; i++ ){
            h[i] = -1;
        }

        for(int i = 0 ; i < n - 1 ; i ++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            add(a,b);
            add(b,a);
        }
        dfs(1);
        System.out.println(ans);
    }
}

Java

import java.util.Scanner;

/**
 * Created by IntelliJ IDEA.
 * User: zm
 * Date: 2023/5/26
 */
public class Main {
    static int N = 2010,n,m = 1000000007;
    static int[][] c = new int[N][N];

    public static void init() {
        for (int i = 0; i < N; i++)
            for (int j = 0; j <= i ; j++)
                if(j == 0)c[i][j] = 1;
        else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        init();
        while(n -- > 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            System.out.println(c[a][b]);
        }
    }
}

C++

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

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

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

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

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

    while(m --)
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if(get(l1, r1) == get(l2, r2))  puts("Yes");
        else                            puts("No");
    }
    return 0;
}

Java

import java.util.Scanner;
public class Main{
    static int N = 100010,P = 131;
    static long[] h = new long[N];
    static long[] p = new long[N];
    public static long get(int l , int r){
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        String s = scan.next();
        p[0] = 1;
        for(int i = 1; i <= n; i++){
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + s.charAt(i - 1);
        }
        while(m -- > 0 ){
            int l1 = scan.nextInt();
            int r1 = scan.nextInt();
            int l2 = scan.nextInt();
            int r2 = scan.nextInt();
            if(get(l1,r1) == get(l2,r2)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}

Java

import java.util.Scanner;
public class Main{
    static int N = 100003,idx;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static void add(int x){
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx++;
    }
    static void find(int x){
        int k = (x % N + N) % N;
        for(int i = h[k]; i != -1; i = ne[i]){
            if(e[i] == x){
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        idx = 0;
        for(int i = 0; i < N; i++)h[i] = -1;
        while(n -- > 0){
            String s = scan.next();
            int a = scan.nextInt();
            if(s.equals("I")){
                add(a);
            }else{
                find(a);
            }
        }
    }
}

C++

拉链法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100003;
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()
{
    int n;
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    while(n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(op[0] == 'I')    insert(x);
        else
        {
            if(find(x)) puts("Yes");
            else        puts("No");
        }
    }
    return 0;
}

开放寻址法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200003, 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;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    while(n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if(op[0] == 'I')    h[k] = x;
        else
        {
            if(h[k] != null)    puts("Yes");
            else                puts("No");
        }
    }
    return 0;
}

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

using namespace std;

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

void heap_swap(int a,int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

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)
    {
        heap_swap(t, u);
        down(t);
    }
}

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

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n--)
    {
        int k, x;
        char op[10];
        scanf("%s", op);
        if (op[0] == 'I')
        {
            scanf("%d", &x);
            m++, cnt++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt --);
            down(1);
        }
        else if (op[0] == 'D')
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt --);
            down(k), up(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;
public class Main{
    public static int qmi(int a, int k, int q){
        int res = 1;
        while(k != 0){
            if((k & 1) == 1) res = (int)((long)res * a % q);
            k >>= 1;
            a = (int)((long)a * a % q);
        }
        return res;
    }
    public static void main(String[] args)throws IOException{
        BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(re.readLine());
        while(n -- > 0){
            String[] st = re.readLine().split(" ");
            int a = Integer.parseInt(st[0]);
            int k = Integer.parseInt(st[1]);
            int q = Integer.parseInt(st[2]);

            System.out.println(qmi(a,k,q));
        }
    }
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int  N = 50010;
    static int  n, m;
    static int[] p = new int[N];
    static int[] d = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args)throws IOException {
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        for(int i =0 ; i < n; i++)p[i] = i;
        int res = 0;
        while(m -- > 0){
            String[] strs = br.readLine().split(" ");
            int t = Integer.parseInt(strs[0]);
            int x = Integer.parseInt(strs[1]);
            int y = Integer.parseInt(strs[2]);
            if(x > n || y > n)res++;
            else{
                int px = find(x),py = find(y);
                if(t == 1) {
                    if (px == py && (d[x] - d[y]) % 3 != 0) res++;
                    else if (px != py) {
                        p[px] = py;
                        d[px] = d[y] - d[x];
                    }
                }else{
                    if(px == py && (d[x] - d[y] - 1) % 3 != 0)res++;
                    else if(px != py){
                        p[px] = py;
                        d[px] = d[y] + 1 - d[x];
                    }
                }
            }
        }
        System.out.println(res);
    }
    static int find(int x){
        if(p[x] != x){
            int t = find(p[x]);
            d[x] += d[p[x]];
            p[x] = t;
        }
        return p[x];
    }
}

c++

#include <iostream>

using namespace std;

const int N = 50010;
int n, m;
int p[N], d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++)  p[i]= i;

    int res = 0;
    while(m --)
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if(x > n || y > n)  res ++;
        else
        {
            int px = find(x), py = find(y);
            if(t == 1)
            {
                if(px == py && (d[x] - d[y]) % 3)   res ++;
                else if(px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if(px == py && (d[x] - d[y] - 1) % 3)   res ++;
                else if(px != py)
                {
                    p[px] = p[y];
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d", res);
    return 0;
}