发表更新算法 / AtCoder4 分钟读完 (大约652个字)

AtCoder Beginner Contest 324

Same

1
2
3
4
5
6
7
8
public static void solve() {
    int n = io.nextInt();
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < n; i++) {
        set.add(io.nextInt());
    }
    io.println(set.size() == 1 ? "Yes" : "No");
}

3-smooth Numbers

1
2
3
4
5
6
public static void solve() {
    long n = io.nextLong();
    while (n % 2 == 0) n /= 2;
    while (n % 3 == 0) n /= 3;
    io.println(n == 1 ? "Yes" : "No");
}

Error Correction

额，很简单的题，赛时花费很长时间，代码写得很乱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void solve() {
    int n = io.nextInt();
    String t = io.next();
    List<Integer> ans = new ArrayList<>();
    for (int k = 0; k < n; k++) {
        String s = io.next();

        int i = 0;
        for (; i < s.length() && i < t.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                break;
            }
        }

        int j = 0;
        for (; j < s.length() && j < t.length(); j++) {
            if (s.charAt(s.length() - 1 - j) != t.charAt(t.length() - 1 - j)) {
                break;
            }
        }

        boolean ok = s.length() == t.length() && i + j >= t.length() - 1;
        ok |= s.length() == t.length() + 1 && i + j >= t.length();
        ok |= s.length() == t.length() - 1 && i + j >= t.length() - 1;
        if (ok) {
            ans.add(k + 1);
        }
    }

    io.println(ans.size());
    ans.forEach(i -> io.print(i + " "));
    io.println();
}

Square Permutation

还是直接使用字符串更简单，要不然还要拆位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void solve() {
    int n = io.nextInt();
    char[] s = io.next().toCharArray();
    Arrays.sort(s);
    long max = (long) Math.pow(10, n);

    int ans = 0;
    for (long i = 0; i * i < max; i++) {
        StringBuilder sb = new StringBuilder(String.valueOf(i * i));
        while (sb.length() < n) {
            sb.append("0");
        }
        char[] t = sb.toString().toCharArray();
        Arrays.sort(t);
        if (Arrays.equals(s, t)) {
            ans++;
        }
    }
    io.println(ans);
}

Joint Two Strings

记录每个字符串的子序列匹配目标字符串的最大前后缀的长度，因为答案和下标无关，所以使用排序 + 二分计算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void solve() {
    int n = io.nextInt();
    String t = io.next();

    int[] prefix = new int[n];
    int[] suffix = new int[n];
    for (int k = 0; k < n; k++) {
        String s = io.next();

        for (int i = 0; i < s.length() && prefix[k] < t.length(); i++) {
            if (s.charAt(i) == t.charAt(prefix[k])) {
                prefix[k]++;
            }
        }

        for (int i = 0; i < s.length() && suffix[k] < t.length(); i++) {
            if (s.charAt(s.length() - 1 - i) == t.charAt(t.length() - 1 - suffix[k])) {
                suffix[k]++;
            }
        }
    }

    Arrays.sort(suffix);

    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefix[i] + suffix[mid] >= t.length()) hi = mid - 1;
            else lo = mid + 1;
        }
        ans += n - lo;
    }
    io.println(ans);
}

Beautiful Path

二分答案，将除法转化为乘法，因为顶点的边限制 \(u<v\)，所以从 \(1\) 到 \(n\) 处理顶点就是拓扑序，并且一定没有环，拓扑序动态规划求最长路径即可。（额，昨天刚做拓扑序动态规划求最长路径，竟然还没做出这题。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    int[] in = new int[n];
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1, b = io.nextInt(), c = io.nextInt();
        g[u].add(new int[]{v, b, c});
        in[v]++;
    }

    double lo = 0, hi = 1e4;
    while (hi - lo >= 1e-10) {
        double mid = lo + (hi - lo) / 2;
        if (check(g, in.clone(), mid)) lo = mid;
        else hi = mid;
    }
    io.println(lo);
}

private static boolean check(List<int[]>[] g, int[] in, double x) {
    int n = g.length;
    double[] dist = new double[n];
    Arrays.fill(dist, Long.MIN_VALUE);

    dist[0] = 0;
    for (int u = 0; u < n; u++) {
        for (int[] t : g[u]) {
            int v = t[0], b = t[1], c = t[2];
            if (dist[v] < dist[u] + b - c * x) {
                dist[v] = dist[u] + b - c * x;
            }
        }
    }

    return dist[n - 1] >= 0;
}
发表更新算法 / AtCoder4 分钟读完 (大约663个字)

AtCoder Beginner Contest 322

First ABC 2

1
2
3
4
5
6
public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    int ans = s.indexOf("ABC");
    io.println(ans < 0 ? -1 : ans + 1);
}

Prefix and Suffix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    String s = io.next(), t = io.next();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) != t.charAt(i)) {
            ans |= 2;
        }
        if (s.charAt(i) != t.charAt(m - n + i)) {
            ans |= 1;
        }
    }
    io.println(ans);
}

Festival

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    for (int i = 0; i < m; i++) {
        int x = io.nextInt() - 1;
        ans[x] = 0;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ans[i] == -1) {
            ans[i] = ans[i + 1] + 1;
        }
    }
    for (int i = 0; i < n; i++) {
        io.println(ans[i]);
    }
}

Polyomino

模拟题，使用位运算似乎更简单，题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public static void solve() {
    char[][][] G = new char[3][4][4];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            G[i][j] = io.next().toCharArray();
        }
    }
    io.println(dfs(0, G, new char[4][4]) ? "Yes" : "No");
}

private static boolean dfs(int i, char[][][] G, char[][] C) {
    if (C == null) return false;
    if (i == 3) return check(C);
    for (int j = 0; j < 4; j++) {
        for (int dx = -3; dx <= 3; dx++) {
            for (int dy = -3; dy <= 3; dy++) {
                char[][] T = move(dx, dy, G[i]);
                if (T == null) continue;
                if (dfs(i + 1, G, add(T, C))) return true;
            }
        }
        G[i] = rotate(G[i]);
    }
    return false;
}

private static char[][] rotate(char[][] A) {
    char[][] B = new char[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            B[i][j] = A[3 - j][i];
        }
    }
    return B;
}

private static char[][] move(int dx, int dy, char[][] G) {
    char[][] res = new char[4][4];
    for (int i = 0; i < 4; i++) {
        Arrays.fill(res[i], '.');
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int nx = i + dx, ny = j + dy;
            if(G[i][j] == '#') {
                if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) {
                    return null;
                }
                res[nx][ny] = G[i][j];
            }
        }
    }
    return res;
}

private static char[][] add(char[][] T, char[][] C) {
    char[][] res = new char[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (C[i][j] == '#' && T[i][j] == '#') return null;
            if (C[i][j] == '#' || T[i][j] == '#') res[i][j] = '#';
            else res[i][j] = '.';
        }
    }
    return res;
}

private static boolean check(char[][] C) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (C[i][j] != '#') return false;
        }
    }
    return true;
}

Product Development

动态规划，\(dp[i][j]\) 表示从前 \(i\) 个计划中选择开发计划，使得参数到达 \(j\)，需要的最小成本，其中 \(j\) 表示 \(a_{1},a_{2},\dots,a_{k}\) 的某个取值，通过将序列看作 \(p+1\) 进制数，可以将一个序列转换为某个数值（在这里就是 \(j\)）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), p = io.nextInt();

    int[] pw = new int[k + 1];
    pw[0] = 1;
    for (int i = 1; i <= k; i++) {
        pw[i] = pw[i - 1] * (p + 1);
    }

    long[] dp = new long[pw[k]];
    Arrays.fill(dp, -1L);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        int c = io.nextInt();
        int[] a = new int[k];
        for (int j = 0; j < k; j++) {
            a[j] = io.nextInt();
        }

        for (int s = pw[k] - 1; s >= 0; s--) {
            int t = 0;
            for (int j = 0; j < k; j++) {
                int cur = s / pw[j] % (p + 1);
                int nxt = Math.min(p, cur + a[j]);
                t += nxt * pw[j];
            }
            if (dp[s] != -1 && (dp[t] == -1 || dp[t] > dp[s] + c)) {
                dp[t] = dp[s] + c;
            }
        }
    }
    io.println(dp[pw[k] - 1]);
}
发表更新算法 / AtCoder3 分钟读完 (大约401个字)

AtCoder Beginner Contest 321

321-like Checker

模拟。

1
2
3
4
5
6
7
8
9
10
11
public static void solve() {
    int n = io.nextInt();
    String s = String.valueOf(n);
    for (int i = 0; i < s.length() - 1; i++) {
        if (s.charAt(i) <= s.charAt(i + 1)) {
            io.println("No");
            return;
        }
    }
    io.println("Yes");
}

Cutoff

比赛时是暴力做的，赛后这个 \(O(1)\) 还想了半天。不多解释，代码还是比较好理解的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt(), x = io.nextInt();
    int min = 101, max = -1, sum = 0;
    for (int i = 0; i < n - 1; i++) {
        int t = io.nextInt();
        sum += t;
        min = Math.min(min, t);
        max = Math.max(max, t);
    }
    int t = x - (sum - min - max);
    if (t > max) {
        io.println(-1);
    } else {
        io.println(t <= min ? 0 : t);
    }
}

321-like Searcher

原来是使用十个二进制位来表示对应数字是否存在，通过暴力枚举算出所有可能的数，最后排序获取对应的位置即可，真的没想到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int k = io.nextInt();
    List<Long> ans = new ArrayList<>();
    for (int i = 2; i < 1 << 10; i++) {
        long x = 0L;
        for (int j = 9; j >= 0; j--) {
            if ((i >> j & 1) == 1) {
                x = x * 10 + j;
            }
        }
        ans.add(x);
    }
    Collections.sort(ans);
    io.println(ans.get(k - 1));
}

Set Menu

二分，状态真差，把加法和乘法混淆了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);
    long[] sum = new long[m + 1];
    for (int i = 0; i < m; i++) {
        sum[i + 1] = sum[i] + b[i];
    }
    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int x = p - a[i];
        int lo = 0, hi = m - 1;
        while (lo <= hi) {
            int mid= lo + (hi - lo) / 2;
            if (b[mid] <= x) lo = mid + 1;
            else hi = mid - 1;
        }
        ans += ((long) lo * a[i] + sum[lo]) + (long) (m - lo) * p;
    }
    io.println(ans);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×