Miku

0

0

794

Miku
8个月前

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
8个月前


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) {
dfs(u+1,state|(1<<i));
list.remove(list.size()-1);
}
}
}

}



Miku
8个月前


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
8个月前


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
8个月前
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
8个月前


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
8个月前

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]);
}

}



Miku
8个月前

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]);
}

}



Miku
8个月前


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;
}

}



Miku
8个月前


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;
}

}