头像

Miku


访客:137

离线:1个月前


活动打卡代码 AcWing 96. 奇怪的汉诺塔

Miku
3个月前

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

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int[] d=new int[15];//有三根柱子时
        int[] f=new int[15];//有四根柱子时
        d[1]=0;
        d[1]=1;//三根柱子一个盘子,只需一次
        for(int i=2;i<=12;i++) {
            d[i]=1+d[i-1]*2;//i-1 A->B,i A->C,i-1 B->C
        }

        Arrays.fill(f,Integer.MAX_VALUE/2);

        f[0]=0;
        for(int i=1;i<=12;i++) {
            for(int j=0;j<i;j++) {
                f[i]=Math.min(f[i], f[j]*2+d[i-j]); 
                //先把上面j个放到B\C上,然后剩下的i-j个当作用三个柱子转移
            }
        }

        for(int i=1;i<=12;i++) {
            System.out.println(f[i]);
        }

    }
}




Miku
3个月前


import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int n;
    static ArrayList<Integer> list=new ArrayList<Integer>();
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
         n=sc.nextInt();

        dfs(0,0);
    }
    private static void dfs(int u, int state) {
        if(u==n) {
            for(int num:list) {
                System.out.print(num+" ");
            }
            System.out.println();
            return;
        }
        for(int i=0;i<n;i++) {
            if(((state>>i)&1)==0) {
                list.add(i+1);
                dfs(u+1,state|(1<<i));
                list.remove(list.size()-1);
            }
        }
    }

}



活动打卡代码 AcWing 95. 费解的开关

Miku
3个月前


import java.util.Scanner;

public class Main {

    static int[] dx = { 0, 0, 0, -1, 1 };
    static int[] dy = { 0, -1, 1, 0, 0 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] light = new char[5][5];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 5; j++) {
                light[j] = sc.next().toCharArray();
            }
            System.out.println(work(light));

        }

    }

    static int work(char[][] light) {
        int min = Integer.MAX_VALUE;
        char[][] map = new char[5][5];
        for (int i = 0; i < (1 << 5); i++) {
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    map[j][k] = light[j][k];
                }
            }
            int res = 0;

            for (int j = 0; j < 5; j++) {
                if (((i >> j) & 1) == 1) {
                    res += 1;
                    turn(0, j, map);
                }
            }
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 5; k++) {
                    if (map[j][k] == '0') {
                        res += 1;
                        turn(j + 1, k, map);
                    }
                }
            }
            boolean isOK = true;
            for (int j = 0; j < 5; j++) {
                if (map[4][j] == '0') {
                    isOK = false;
                    break;
                }
            }
            if (isOK) {
                min = Math.min(res, min);
            }
        }
        if(min>6) return -1;
        return min;
    }

    private static void turn(int i, int j, char[][] map) {
        for (int n = 0; n < 5; n++) {
            int x = i + dx[n];
            int y = j + dy[n];
            if (x >= 0 && x < 5 && y >= 0 && y < 5) {
                map[x][y] ^= 1;
            }
        }

    }

}




Miku
3个月前


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

public class Main {
    static int n;
    static int m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dfs(0, 0, 0);
    }

    private static void dfs(int u, int state, int count) {
        if(count+n-u<m) {
            return;
        }
        if (count == m) {
            for (int i = 0; i < n; i++) {
                if (((state >> i) & 1) == 1) {
                    System.out.print(i + 1 + " ");
                }
            }
            System.out.println();
            return;
        }

        dfs(u + 1, state | 1 << u, count+1);
        dfs(u + 1, state, count);

    }

}




Miku
3个月前
package 蓝桥;

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

public class Main {
    static int n;
    static int m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dfs(0, 0, 0);
    }

    private static void dfs(int u, int state, int count) {
        if(count+n-u<m) {
            return;
        }
        if (count == m) {
            for (int i = 0; i < n; i++) {
                if (((state >> i) & 1) == 1) {
                    System.out.print(i + 1 + " ");
                }
            }
            System.out.println();
            return;
        }
        dfs(u + 1, state | 1 << u, count+1);
        dfs(u + 1, state, count);

    }

}




Miku
3个月前


import java.util.Scanner;

public class Main {
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0, 0);
    }

    private static void dfs(int u, int state) {
        if (u == n) {
            for (int i = 0; i < n; i++) {
                if (((state >> i) & 1) == 1) {
                    System.out.print(i + 1 + " ");
                }
            }
            System.out.println();
            return;
        }
        dfs(u+1,state);
        dfs(u+1,state|1<<u);
    }

}




Miku
3个月前

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] weight = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                weight[i][j] = sc.nextInt();
            }
        }
        //m为所有状态的二进制表示,如n=2时,m=100,可表示000 001 010 011四种状态
        //即 都没经过 经过0号点 经过1号点 经过0号店和1号点四种情况
        int m = 1 << n;
        int dp[][] = new int[m][n];//第一维用下标表示所有状态,第二维下标表示点号,值表示目前总权
        for(int i=0;i<m;i++) {//初始化所有权为+∞
            Arrays.fill(dp[i], Integer.MAX_VALUE/4);//除小一点的数都可以,只是为了防止相加时溢出
        }
        dp[1][0]=0;//意味在出发点0号点,状态为000001(即只经历过0号点),权为0
        for (int i = 0; i < m; i++) {//遍历所有状态
            for (int j = 0; j < n; j++) {//遍历所有点
                if (((i >> j) & 1) == 1) {//如果这种状态下经历过j号点
                    for (int k = 0; k < n; k++) {//搜索从k号点到j号点的最小权
                        if ((((i - (1 << j)) >> k) & 1) == 1) {
                            //如果该状态经历过k点但没有经历过j点,即是可行状态
                            //取转移中的最小值并记录
                            dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + weight[k][j]);
                        }
                    }
                }
            }
        }
        //则dp[m-1][n-1],即经历过所有点且终点在n-1号点时的权就是结果
        System.out.println(dp[m-1][n-1]);
    }

}



活动打卡代码 AcWing 91. 最短Hamilton路径

Miku
3个月前

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] weight = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                weight[i][j] = sc.nextInt();
            }
        }
        //m为所有状态的二进制表示,如n=2时,m=100,可表示000 001 010 011四种状态
        //即 都没经过 经过0号点 经过1号点 经过0号店和1号点四种情况
        int m = 1 << n;
        int dp[][] = new int[m][n];//第一维用下标表示所有状态,第二维下标表示点号,值表示目前总权
        for(int i=0;i<m;i++) {//初始化所有权为+∞
            Arrays.fill(dp[i], Integer.MAX_VALUE/4);//除小一点的数都可以,只是为了防止相加时溢出
        }
        dp[1][0]=0;//意味在出发点0号点,状态为000001(即只经历过0号点),权为0
        for (int i = 0; i < m; i++) {//遍历所有状态
            for (int j = 0; j < n; j++) {//遍历所有点
                if (((i >> j) & 1) == 1) {//如果这种状态下经历过j号点
                    for (int k = 0; k < n; k++) {//搜索从k号点到j号点的最小权
                        if ((((i - (1 << j)) >> k) & 1) == 1) {
                            //如果该状态经历过k点但没有经历过j点,即是可行状态
                            //取转移中的最小值并记录
                            dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + weight[k][j]);
                        }
                    }
                }
            }
        }
        //则dp[m-1][n-1],即经历过所有点且终点在n-1号点时的权就是结果
        System.out.println(dp[m-1][n-1]);
    }

}



活动打卡代码 AcWing 90. 64位整数乘法

Miku
3个月前


import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long p = sc.nextLong();

        System.out.println(pow(a, b, p));
    }

    static public long pow(long a, long b, long p) {
        if (b == 0)
            return 0;
        long ans = 0;
        while (b > 0) {
            if ((b & 1) == 1) {
                ans += a;
                ans %= p;
            }
            a *= 2;
            a %= p;
            b >>= 1;
        }
        return  ans;
    }

}



活动打卡代码 AcWing 89. a^b

Miku
3个月前


import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long b = sc.nextInt();
        long p = sc.nextInt();

        System.out.println(pow4(a, b, p));
    }

    static public long pow4(long a, long b, long p) {
        if (b == 0)
            return 1 % p;
        long ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                ans *= a;
                ans %= p;
            }
            a *= a;
            a %= p;
            b >>= 1;
        }
        return  ans;
    }

}