头像

Archer

bjuter




离线:6小时前


活动打卡代码 AcWing 1118. 分成互质组

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])) {
                g[i].add(a[u]);
                dfs(u + 1, k);
                g[i].remove(g[i].size() - 1);
            }
        }
        // 不能加入旧组,只能新开组
        g[k].add(a[u]);
        dfs(u + 1, k + 1);
        g[k].remove(g[k].size() - 1);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        s = cin.readLine().split(" ");
        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);
    }
}


活动打卡代码 AcWing 1117. 单词接龙

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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);

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

        char start = cin.readLine().charAt(0);

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


活动打卡代码 AcWing 1116. 马走日

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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int T = Integer.parseInt(s[0]);
        while (T-- > 0) {
            s = cin.readLine().split(" ");
            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);

        }
    }
}


活动打卡代码 AcWing 1112. 迷宫

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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int k = Integer.parseInt(s[0]);
        while (k -- > 0) {
            s = cin.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            for (int i = 0; i < n; i++) {
                String str = cin.readLine();
                for (int j = 0; j < n; j++) {
                    g[i][j] = str.charAt(j);
                    st[i][j] = false;
                }
            }

            s = cin.readLine().split(" ");
            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");
        }
    }
}


活动打卡代码 AcWing 1113. 红与黑

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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String[] s = cin.readLine().split(" ");
            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++) {
                String str = cin.readLine();
                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);
        }
    }
}


活动打卡代码 AcWing 1058. 股票买卖 V

Archer
1天前
/*
画图分析
*/
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int[] w = new int[n + 1];
        s = cin.readLine().split(" ");
        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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int[] w = new int[n + 1];
        s = cin.readLine().split(" ");
        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]));
    }
}


活动打卡代码 AcWing 1057. 股票买卖 IV

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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        int[] w = new int[n + 1];
        int[][] f = new int[m + 1][2];
        s = cin.readLine().split(" ");
        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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        s = cin.readLine().split(" ");
        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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        s = cin.readLine().split(" ");
        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);
    }
}


活动打卡代码 AcWing 1049. 大盗阿福

Archer
1天前
/*
状态机Dp:
状态机中边表示权重,在这里表示收益
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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int T = Integer.parseInt(s[0]);
        while (T-- > 0) {
            s = cin.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int[] w = new int[n + 1];
            int[][] f = new int[n + 1][2];
            s = cin.readLine().split(" ");
            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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        int T = Integer.parseInt(s[0]);
        while (T-- > 0) {
            s = cin.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int[] w = new int[n + 1];
            int[] f = new int[n + 1];
            s = cin.readLine().split(" ");
            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]);

        }
    }
}


活动打卡代码 AcWing 190. 字串变换

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) {
        Queue<String> qa = new LinkedList<>();
        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 {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        String A = s[0], B = s[1];
        while (true) {
            String str = cin.readLine();
            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) {
    Queue<String> qa = new LinkedList<>(), qb = new LinkedList<>();
    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 {
    BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    String[] s = cin.readLine().split(" ");
    String A = s[0], B = s[1];
    while (true) {
        String str = cin.readLine();
        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);
}

}
···



活动打卡代码 AcWing 1353. 滑雪场设计

Archer
2天前
/*
贪心:
最终结果一定在 i ~ i + 17 之间
所以枚举区间就行
*/

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