AtCoder Beginner Contest 324

Same

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

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

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

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

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

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

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

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\) 处理顶点就是拓扑序，并且一定没有环，拓扑序动态规划求最长路径即可。（额，昨天刚做拓扑序动态规划求最长路径，竟然还没做出这题。）

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