【ACM】ACM宝典

2021-05-25T08:53:00
本文用于记录ACM比赛时常用的算法和模板

全排列

public class Main {
    public static void main(String[] args) {
        perm(new int[]{1,2,3},0,2);
    }
    public static void perm(int[] array,int start,int end) {
        if(start==end) {
            System.out.println(Arrays.toString(array));
        } else {
            for (int i = start; i <= end; i++) {
                //1，2，3的全排列这块相当于将其中一个提了出来，下次递归从start+1开始
                swap(array,start,i);
                perm(array,start+1,end);
                //这块是复原数组，为了保证下次另外的同级递归使用数组不会出错
                //这块可以通过树来理解，每次回退一步操作，交换回去
                swap(array,start,i);
            }
        }
    }
    public static void swap(int[] array,int i,int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

快速幂

public static long fastPow(long k,long e,long mod) {
        long ans=1;
        while(k>=1)
        {
            if ((k&1)>=1) {
                ans*=e%mod;
            }
            e*=e%mod;
            k>>=1;
        }
        return ans;
    }

快速输入输出

//第一种
public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
            String[] init = br.readLine().split(" ");
            int n = Integer.valueOf(init[0]);
            long m = Long.valueOf(init[1]);
            long q = Long.valueOf(init[2]);
            long[] x = new long[n+1];
            String[] xs = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                x[i+1] = Long.valueOf(xs[i]);
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < q; i++) {
                String s2[]=br.readLine().split(" ");
                int k = Integer.parseInt(s2[1]);
                long length = p * x[k];
                if ((length/m)%2 == 1) {
                    sb.append(m - (length%m));
                }else {
                    sb.append(length%m);
                }
                sb.append('\n');
            }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}
//第二种
public class FastScanner {
    public static void main(String[] args) {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        try {
            st.nextToken();
            int n = (int) st.nval;
            System.out.println(n);
            
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

格式化输出

public class FormatDemo {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        System.out.println("Hello World");

        double x=-10000.0/3.0;

        double y=5000.0/3.0;

        System.out.println(x);

        System.out.printf("%,10.2f\r\n",x);

        System.out.printf("%-,10.2f\r\n",x);

        System.out.printf("%+(,10.2f %2$.3f\r\n",x,y);

        System.out.printf("%+(,10.2f %1$.3f %2$.3f %<f %<.3f\r\n",x,y);

    }

}

并查集

public class DisjointSet {
    public static int n = 6;
    public static void main(String[] args) {
        int[] parent = new int[n];
        int[] rank = new int[n];
        int[][] edges = {{0,1}, {1,2}, {1,3}, {3,4},{2,5}, {4,5}};
        init(parent);
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            if (!union_vertices(x, y, parent, rank)) {
                System.out.println("Cycle detected!");
                return;
            }
        }
        System.out.println("No cycles found.");
    }

    public static void init(int parent[]) {
        for (int i = 0; i < n; i++) {
            parent[i] = -1;
        }
    }
    public static int find_root(int x, int[] parent) {
        int x_root = x;
        while (parent[x_root] != -1) {
            x_root = parent[x_root];
        }
        return x_root;
    }

    public static boolean union_vertices(int x, int y, int[] parent, int[] rank) {
        int x_root = find_root(x, parent);
        int y_root = find_root(y, parent);
        if (x_root == y_root) {
            return false;
        }
        if (rank[x_root] > rank[y_root]) {
            parent[y_root] = x_root;
        }else if (rank[x_root] < rank[y_root]){
            parent[x_root] = y_root;
        }else {
            parent[x_root] = y_root;
            rank[y_root]++;
        }
        return true;
    }
}

01背包模板

public class Knapsack {
    public static void main(String[] args) {
        int[][] plan = new int[6][21];
        int[] w = {0,2,4,8,10,13};
        int[] v = {0,3,5,9,12,15};
        int v1,v2;
        for(int id=1;id<6;id++) {
            for(int C=1;C<21;C++) {
                if(w[id]>C) plan[id][C]=plan[id-1][C];
                else {
                    v1 = plan[id-1][C-w[id]]+v[id];
                    v2 = plan[id-1][C];
                    plan[id][C] = v1 >=v2 ?v1:v2;
                }
            }
        }
        //输出背包
        for(int i=0;i<6;i++) {
            for(int j=0;j<21;j++) {
                if (j > 9 && i < 3) {
                    System.out.print(plan[i][j]+"    ");
                }else {
                    System.out.print(plan[i][j]+"   ");
                }
            }
            System.out.println();
        }
    }
}

区间调度dp模板

//根据时间做任务，选任务会占据一定的时间
public class S {
public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    State[] list = new State[n];
    for(int i = 0; i < n; i++) {
        //开始时间，得分，等待时间
        list[i] = new State(sc.nextInt(), sc.nextInt(), sc.nextInt());
    }
    Arrays.sort(list);
    int[] dp = new int[2000001]; //20000001分钟
    int index = 0;
    for (int i = 0; i < 2000000 ; i++) {
        while (index < n && list[index].m == i) {
            dp[i+list[index].w] = Math.max(dp[i+list[index].w], dp[i]+list[index].f);
            index++;
        }
        dp[i+1] = Math.max(dp[i + 1], dp[i]);
    }
    System.out.println(dp[2000000]);
}
    static class State implements Comparable<State> {
        public int m,f,w;
        public State(int a, int b, int c){
            m=a;
            f=b;
            w=c;
        }
        @Override
        public int compareTo(State s) {
            return m - s.m;
        }
    }
}

二分

  • 当 check(mid) == true 调整的是 l 时：计算 mid 的方式应该为 mid = l + r + 1 >> 1：
while (l < r) {
    long mid = l + r + 1 >> 1;
    if (check(mid)) {
        l = mid;
    } else {
        r = mid - 1;
    }
}
  • 当 check(mid) == true 调整的是 r 时：计算 mid 的方式应该为 mid = l + r >> 1：
while (l < r) {
    long mid = l + r >> 1;
    if (check(mid)) {
        r = mid;
    } else {
        l = mid + 1;
    }
}

龟速乘法（处理直接加会爆longlong）

快速乘法，采用了倍增思想：

long mul(long a, long k) {
    long ans = 0;
    while (k > 0) {
        if ((k & 1) == 1) ans += a;
        k >>= 1;
        a += a;
    }
    return ans;
}

快速幂

static long mpow(long a, long b) {
    long res = 1;
    while (b > 0) {
        if ((b & 1) == 1) {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}

区间dp

for (int l = 1; l <= n; l++) {//枚举长度
    for (int i = 1; i + l <= n + 1; i++) {//枚举起点，
        int j = i + l - 1;
        for (int k = i; k < j; k++) {//枚举分割点，更新小区间最优解
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + something);
        }
    }
}

Java快读，快输出

StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
sc.nextToken();
int t = (int)sc.nval;

PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
out.println();
out.flush();

质数筛（埃及筛）

int N = (int) 1e7;
boolean[] isPrime = new boolean[N + 5];
Arrays.fill(isPrime, true);
isPrime[1] = false;
for (int i = 2; i <= N; i++) {
    if (isPrime[i]) {
        for (int j = 2; j * i <= N; j++) {
            isPrime[i * j] = false;
        }
    }
}

阶乘因子个数(m!中含有多少k因子)

static long numberOfFactorials(long m, long k) {
    long ret = 0;
    while (m > 0) {
        ret += m / k;
        m /= k;
    }
    return ret;
}

快排

public static void quick_sort(int[] nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int x = nums[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (nums[i] < x);
        do j--; while (nums[j] > x);
        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

弗洛伊德算法--构造两点最短路径（全员）

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
        }
    }
}

狄克斯特拉算法

import java.util.Arrays;
import java.util.PriorityQueue;

public class 最短路径 {
    static int[] d = new int[2100];
    static boolean[] vis = new boolean[2100];
    static PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> d[o1] - d[o2]);

    static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    static int lcm(int x, int y) {
        return x * y / gcd(x, y);
    }

    static void dijkstra() {
        Arrays.fill(d, Integer.MAX_VALUE);
        d[1] = 0;
        vis[1] = true;
        for (int i = 2; i <= 22; i++) {
            d[i] = lcm(1, i);
            heap.add(i);
        }

        while (!heap.isEmpty()) {
            int v = heap.poll();
            if (vis[v]) continue;
            vis[v] = true;
            if (v == 2021) break;
            for (int i = Math.max(1, v - 21); i <= Math.min(2021, v + 21); i++) {
                if (!vis[i]) {
                    d[i] = Math.min(d[i], d[v] + lcm(v, i));
                    heap.add(i);
                }
            }
        }

        System.out.println(d[2021]);
    }

    public static void main(String[] args) {
        dijkstra();
    }
}
当前页面是本站的「Baidu MIP」版。发表评论请点击：完整版 »

© 2024 MIP for Typecho v0.8 , Designed by Holmesian.