Archer

bjuter

8302

Archer
14小时前

#### 按照顺序将数看是否能放到已在的组中，否则新开一个组，注意这里要按照顺序来来放入（避免重复放入）

import java.io.*;
import java.util.*;
class Main {
static int n, ans;
static int N = 11;
static int[] a = new int[N];
static boolean[] st = new boolean[N];
static ArrayList[] g = new ArrayList[N];

static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
static boolean check(List<Integer> g, int x) {
for (int i = 0; i < g.size(); i++) {
if (gcd(x, g.get(i)) > 1) return false;
}
return true;
}

static void dfs(int u, int k) {  // u个数，k个组
// if (k >= ans) return;
// if (u == n) ans = k;
if (u == n) {
ans = Math.min(ans, k);
return;
}

for (int i = 0; i < k; i++) {
if (check(g[i], a[u])) {
dfs(u + 1, k);
g[i].remove(g[i].size() - 1);
}
}
// 不能加入旧组，只能新开组
dfs(u + 1, k + 1);
g[k].remove(g[k].size() - 1);
}
public static void main(String[] args) throws IOException {
n = Integer.parseInt(s[0]);
for (int i = 0; i < n; i++){
a[i] = Integer.parseInt(s[i]);
g[i] = new ArrayList<Integer>();
}
ans = Integer.MAX_VALUE;
dfs(0, 0);
System.out.println(ans);
}
}


Archer
16小时前
import java.io.*;
class Main {
static int n, ans;
static int N = 22;
static String[] word = new String[N];
static int[] used = new int[N]; // 每个单词使用的数量
static int[][] g = new int[N][N]; // i结尾和j开头单词能够相连的最小连接单词数，因为只有最小，连接的长度可能最长
static void dfs(String dragon, int last) {
ans = Math.max(ans, dragon.length());
used[last] ++;
for (int i = 0; i < n; i++) {
if (g[last][i] != 0 && used[i] < 2) {
dfs(dragon + word[i].substring(g[last][i]), i); // 将满足条件的拼接
}
}
used[last] --;
}
public static void main(String[] args) throws IOException {
n = Integer.parseInt(s[0]);

for (int i = 0; i < n; i++) word[i] = cin.readLine();

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++ ) {
String a = word[i], b = word[j];
int al = a.length(), bl = b.length();
for (int k = 1; k < Math.min(al, bl); k++) {
if (a.substring(al - k, al).equals(b.substring(0, k))) {
g[i][j] = k;
break;
}
}
}
}
for (int i = 0; i < n; i++) {
if (word[i].charAt(0) == start) {
dfs(word[i], i); // i 表示当前是哪一个单词的结尾
}
}
System.out.println(ans);
}
}


Archer
17小时前
import java.io.*;
class Main {
static int N = 10;
static int n, m, ans;
static boolean[][] st = new boolean[N][N];
static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
static void dfs(int x, int y, int u) { // u 表示遍历到第几个格子了
if (u == n * m) {
ans++;
return;
}
st[x][y] = true;
for (int i = 0; i < 8; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b]) {
dfs(a, b, u + 1);
}
}
st[x][y] = false;
}
public static void main(String[] args) throws IOException {
int T = Integer.parseInt(s[0]);
while (T-- > 0) {
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
int x = Integer.parseInt(s[2]), y = Integer.parseInt(s[3]);

// 这里st不需要初始化，因为每一次dfs执行完都会恢复现场，这是标志棋牌外的走法

ans = 0;
dfs(x, y, 1);
System.out.println(ans);

}
}
}


Archer
18小时前
import java.io.*;
class Main {
static int n;
static int N = 110;
static char[][] g = new char[N][N];
static boolean[][] st = new boolean[N][N];
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static boolean dfs(int stx, int sty, int edx, int edy) {
if (g[stx][sty] == '#') return false;
st[stx][sty] = true;
if (stx == edx && sty == edy) return true;
for (int i = 0; i < 4; i++) {
int x = stx + dx[i], y = sty + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n && !st[x][y]) {
if (dfs(x, y, edx, edy)) return true;
}
}
// st[stx][sty] = false;  将这一行注释掉之后就能ac,否则tle
return false;
}
public static void main(String[] args) throws IOException {
int k = Integer.parseInt(s[0]);
while (k -- > 0) {
n = Integer.parseInt(s[0]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = str.charAt(j);
st[i][j] = false;
}
}

int stx = Integer.parseInt(s[0]), sty = Integer.parseInt(s[1]);
int edx = Integer.parseInt(s[2]), edy = Integer.parseInt(s[3]);
if (dfs(stx, sty, edx, edy)) System.out.println("YES");
else System.out.println("NO");
}
}
}


Archer
18小时前
import java.io.*;
class Main {
static int N = 22;
static int n, m;
static char[][] g = new char[N][N];
static int ans;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static void dfs(int x, int y) {
ans++;
g[x][y] = '#';
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < n && a >= 0 && b < m && b >= 0 && g[a][b] == '.') {
dfs(a, b);
}
}
}
public static void main(String[] args) throws IOException {
while (true) {
m = Integer.parseInt(s[0]);
n = Integer.parseInt(s[1]);
if (n == 0 && m == 0) break;
int stx = 0, sty = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
g[i][j] = str.charAt(j);
if (g[i][j] == '@') {
stx = i;
sty = j;
}
}
}
ans = 0;
dfs(stx, sty);
System.out.println(ans);
}
}
}


Archer
1天前
/*

*/
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s[0]);
int[] w = new int[n + 1];
for (int i = 1; i <= n; i++) {
w[i] = Integer.parseInt(s[i - 1]);
}

int[][] f = new int[n + 1][3];
// 这里f[][0]表示持有股票，可卖出，f[][1] 卖出股票第一天（冷冻期），f[][2] 卖出股票第二天，可买入、
// 初始化
f[0][0] = f[0][1] = -0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - w[i]);
f[i][1] = f[i - 1][0] + w[i];
f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
}

// 出口
System.out.println(Math.max(f[n][1], f[n][2]));
}
}

/*

*/
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s[0]);
int[] w = new int[n + 1];
for (int i = 1; i <= n; i++) {
w[i] = Integer.parseInt(s[i - 1]);
}

int[] f = new int[3];
// 这里f[][0]表示持有股票，可卖出，f[][1] 卖出股票第一天（冷冻期），f[][2] 卖出股票第二天，可买入、
// 初始化
f[0] = f[1] = -0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
int f_0 = f[0], f_1 = f[1], f_2 = f[2];
f[0] = Math.max(f_0, f_2 - w[i]);
f[1] = f_0 + w[i];
f[2] = Math.max(f_1, f_2);
}

// 出口
System.out.println(Math.max(f[1], f[2]));
}
}


Archer
1天前
/*
买入算作第j次交易开始，买卖完算作一次交易
可买入：f[i][j][0] 表示在第i处，手中无货，并且正在进行第j次交易，可卖出到买入这相当于第j次交易执行了一半
可卖出：f[i][j][1] 表示在第i处，手中有货，并且正在进行第j次交易，这相当于第j次交易刚开始，从j-1转移而来
*/
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
int[] w = new int[n + 1];
int[][] f = new int[m + 1][2];
for (int i = 1; i <= n; i++) {
w[i] = Integer.parseInt(s[i - 1]);
}
f[0][0] = 0;
for (int i = 0; i <= m; i++) {
f[i][1] = -0x3f3f3f3f;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[j][0] = Math.max(f[j][0], f[j][1] + w[i]);
f[j][1] = Math.max(f[j][1], f[j - 1][0] - w[i]);
}
}
int res = 0;
for (int i = 0; i <= m; i++) res = Math.max(res, f[i][0]);
System.out.println(res);
}
}

import java.io.*;
class Main {
static int N = 100010, M = 110;
static int[] w = new int[N];
static int INF = 0x3f3f3f3f;

public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
for (int i = 1; i <= n; i++) w[i] = Integer.parseInt(s[i - 1]);
int[][][] f = new int[n + 1][M][2];  // 会导致tle
for (int i = 0; i <= n; i++) {
f[i][0][0] = 0;
for (int j = 0; j <= m; j++)
f[i][j][1] = -INF;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j][0] = Math.max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
}
}
int res = 0;
for (int i = 0; i <= m; i++) res = Math.max(res, f[n][i][0]);
System.out.println(res);
}
}

import java.io.*;
class Main {
static int N = 100010, M = 110;
static int[] w = new int[N];
static int INF = 0x3f3f3f3f;
static int[][] f = new int[M][2];
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
for (int i = 1; i <= n; i++) w[i] = Integer.parseInt(s[i - 1]);
f[0][0] = 0;
for (int j = 0; j <= m; j++)
f[j][1] = -INF;

for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
f[j][0] = Math.max(f[j][0], f[j][1] + w[i]);
f[j][1] = Math.max(f[j][1], f[j - 1][0] - w[i]);
}
}
int res = 0;
for (int i = 0; i <= m; i++) res = Math.max(res, f[i][0]); // 完整交易
System.out.println(res);
}
}


Archer
1天前
/*

f[i][j] j = 0/1, 表示第i家店铺中，当前处于0未抢，1抢的最大受益
f[i][0] = f[i - 1][0]   f[i - 1][1];
f[i][1] = f[i - 1][0] + w[i]; 可以画图表示只能从 0状态转移而来，这个权边表示第i加店铺抢

*/

import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
int T = Integer.parseInt(s[0]);
while (T-- > 0) {
int n = Integer.parseInt(s[0]);
int[] w = new int[n + 1];
int[][] f = new int[n + 1][2];
for (int i = 1; i <= n; i++) {
w[i] = Integer.parseInt(s[i - 1]);
}

f[0][0] = 0;
f[0][1] = Integer.MIN_VALUE; // 表示前0家店铺，不可能处于抢的状态

for (int i = 1; i <= n; i++) {
f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]);
f[i][1] = f[i - 1][0] + w[i];
}
System.out.println(Math.max(f[n][0], f[n][1]));

}
}
}


#### 建议使用背包模型，LeetCode另外一个打家劫舍也是背包模型更容易理解

/*

*/

import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
int T = Integer.parseInt(s[0]);
while (T-- > 0) {
int n = Integer.parseInt(s[0]);
int[] w = new int[n + 1];
int[] f = new int[n + 1];
for (int i = 1; i <= n; i++) {
w[i] = Integer.parseInt(s[i - 1]);
}

f[0] = 0;
f[1] = w[1];
for (int i = 2; i <= n; i++) {
f[i] = Math.max(f[i - 1], f[i - 2] + w[i]); // i >= 2
}
System.out.println(f[n]);

}
}
}


Archer
1天前

#### 普通的BFS，TLE

/*

*/
import java.io.*;
import java.util.*;
class Main {
static int N = 25;
static int n; // 多少种匹配规则
static String[] a = new String[N], b = new String[N];
static int bfs(String A, String B) {
Map<String, Integer> mapa = new HashMap<>();
qa.offer(A);
mapa.put(A, 0);
while (!qa.isEmpty()) {
String start = qa.poll();
for (int i = 0; i < start.length(); i++) {
for (int j = 0; j < n; j++) {
if (i + a[j].length() > start.length()) continue;
if (start.substring(i, i + a[j].length()).equals(a[j])) { // 满足比配
String state = start.substring(0, i) + b[j] + start.substring(i + a[j].length());
if (mapa.get(state) != null) continue;
if (state.equals(B)) return mapa.get(start) + 1;
mapa.put(state, mapa.get(start) + 1);
if (mapa.get(state) > 11) return 11;
qa.offer(state);
}
}
}
}
return 11;
}
public static void main(String[] args) throws IOException {
String A = s[0], B = s[1];
while (true) {
if (str == null) break;
s = str.split(" ");
a[n] = s[0];
b[n] = s[1];
n++;
}
int step = bfs(A, B);
if (step > 10) System.out.println("NO ANSWER!");
else System.out.println(step);
}
}


#### 因此就要想到优化，时间复杂度和空间复杂度分析


/

/
import java.io.;
import java.util.
;
class Main {
static int N = 25;
static int n; // 多少种匹配规则
static String[] a = new String[N], b = new String[N];
// 从1向2扩展
static int extend(Queue[HTML_REMOVED] q1, Map[HTML_REMOVED] map1,
Queue[HTML_REMOVED] q2, Map[HTML_REMOVED] map2, String[] s1, String[] s2) {

    String start = q1.poll();
for (int i = 0; i < start.length(); i++) {
for (int j = 0; j < n; j++) {
if (i + s1[j].length() > start.length()) continue;
if (start.substring(i, i + s1[j].length()).equals(s1[j])) { // 满足比配
String state = start.substring(0, i) + s2[j] + start.substring(i + s1[j].length());
if (map1.get(state) != null) continue;
if (map2.get(state) != null) return map1.get(start) + 1 + map2.get(state);
map1.put(state, map1.get(start) + 1);
q1.offer(state);
}
}
}
return 11;
}
static int bfs(String A, String B) {
Map<String, Integer> mapa = new HashMap<>(), mapb = new HashMap<>();// 分别表示到起点的距离
qa.offer(A);
mapa.put(A, 0);
qb.offer(B);
mapb.put(B, 0);
while (!qa.isEmpty() && !qb.isEmpty()) { // 如果当一个为空的时候，那么就表示不连通
// 为了降低扩展的复杂度，选择队列中元素较少的来扩展
int t = 0;
if (qa.size() <= qb.size()) t = extend(qa, mapa, qb, mapb, a, b); // 从 A 向 B 方向扩展
else t = extend(qb, mapb, qa, mapa, b, a);
if (t <= 10) return t;
}
return 11;
}
public static void main(String[] args) throws IOException {
String A = s[0], B = s[1];
while (true) {
if (str == null) break;
s = str.split(" ");
a[n] = s[0];
b[n] = s[1];
n++;
}
int step = bfs(A, B);
if (step > 10) System.out.println("NO ANSWER!");
else System.out.println(step);
}


}
···

Archer
2天前
/*

*/

import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] h = new int[n];
for (int i = 0; i < n; i++) {
h[i] = sc.nextInt();
}

int res = 0x3f3f3f3f;
for (int i = 0; i + 17 <= 100; i++) {
int cost = 0, l = i, r = i + 17;
for (int j = 0; j < n; j++) {
if (h[j] > r) cost += (h[j] - r) * (h[j] - r);
if (h[j] < l) cost += (l - h[j]) * (l - h[j]);
}
res = Math.min(res, cost);
}
System.out.println(res);
}
}
`