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

AtCoder Beginner Contest 318

Full Moon

模拟。

1
2
3
4
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    io.println(n < m ? 0 : (n - m) / p + 1);
}

Overlapping sheets

比赛时没什么思路，想到扫描线，就用扫描线 + 区间合并来做了。结果一看题解，暴力标记每个点，没想到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), ans = 0;
    int[][] g = new int[100][100];
    for (int i = 0; i < n; i++) {
        int a = io.nextInt(), b = io.nextInt();
        int c = io.nextInt(), d = io.nextInt();
        for (int x = a; x < b; x++) {
            for (int y = c; y < d; y++) {
                if (g[x][y]++ == 0) ans++;
            }
        }
    }
    io.println(ans);
}

Blue Spring

看到大佬的解法后，感觉我模拟的方式好蠢啊。当时我是枚举是否要买 \(d\) 张票，有点麻烦，原来枚举买当日的票更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), d = io.nextInt(), p = io.nextInt();
    int[] f = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        f[i] = io.nextInt();
    }
    Arrays.sort(f);
    long ans = Long.MAX_VALUE, sum = 0L;
    for (int i = 0; i <= n; i++) {
        sum += f[i];
        ans = Math.min(ans, sum + (long) (n - i + d - 1) / d * p);
    }
    io.println(ans);
}

General Weighted Max Matching

动态规划有点不太会，赛时瞎搞 AC 的。记忆化搜索会很好写，然后 DP 的话，我是用三层循环解决的，下面的解法优化掉一层循环。

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();
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[i][j] = io.nextInt();
        }
    }
    long[] dp = new long[1 << n];
    for (int k = 2; k < 1 << n; k++) {
        int i = Integer.numberOfTrailingZeros(k & -k);
        dp[k] = dp[k ^ (1 << i)];
        for (int j = i + 1; j < n; j++) {
            if ((k >> j & 1) == 1) {
                dp[k] = Math.max(dp[k], dp[k ^ (1 << i) ^ (1 << j)] + d[i][j]);
            }
        }
    }
    io.println(dp[(1 << n) - 1]);
}

Sandwiches

比较显然的做法是把相同的数分为一组，然后组内枚举中间的数。对于每个中间的数，让答案加上 \(L\times R\)，其中 \(L\) 和 \(R\) 分别是左右两边相等的数的个数，枚举时可以一次性枚举间隔内所有数。

第二个解法是参考大佬的代码得到的，相当于枚举右端点吧。对于每个右端点，它的贡献可以根据下面代码中的公式得出，感觉比较巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    int n = io.nextInt();
    int[] cnt = new int[n];
    long[] sum = new long[n];
    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt() - 1;
        ans += (long) i * cnt[a] - sum[a] - (long) (1 + cnt[a]) * cnt[a] / 2;
        cnt[a]++;
        sum[a] += i;
    }
    io.println(ans);
}

Octopus

有点抽象，不是很懂。大概是枚举了 \(N^{2}\) 个极限位置，然后分别对每个位置判断可行性。

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
public static void solve() {
    int N = io.nextInt();
    long[] X = new long[N];
    long[] L = new long[N];
    for (int i = 0; i < N; i++) {
        X[i] = io.nextLong();
    }
    for (int i = 0; i < N; i++) {
        L[i] = io.nextLong();
    }

    List<Long> pos = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            pos.add(X[i] - L[j]);
            pos.add(X[i] + L[j] + 1);
        }
    }
    Collections.sort(pos);

    long ans = 0L;
    for (int i = 0; i < pos.size() - 1; i++) {
        long[] dis = new long[N];
        for (int j = 0; j < N; j++) {
            dis[j] = Math.abs(pos.get(i) - X[j]);
        }
        Arrays.sort(dis);
        boolean ok = true;
        for (int j = 0; j < N; j++) {
            if (dis[j] > L[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans += pos.get(i + 1) - pos.get(i);
        }
    }
    io.println(ans);
}
发表更新算法 / Codeforces4 分钟读完 (大约547个字)

Educational Codeforces Round 154 (Rated for Div. 2)

Prime Deletion

从 \(1\) 到 \(9\) 的序列中删除一些数（至少保留两位），使得结果为质数。可以发现 \(13\) 和 \(31\) 都是质数，所以判断 \(1\) 和 \(3\) 的先后顺序，然后输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            io.println(13);
            return;
        } else if(s[i] == '3') {
            io.println(31);
            return;
        }
    }
}

Two Binary Strings

比赛时我是从左往右遍历记录不相等的数量，如果有不相等的，那么就需要一个 \(0\)，否则遇到 \(1\) 就输出 YES。和正解的思路是一样的，就是麻烦一点。正解是有相同的 \(01\) 出现时就输出 YES。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    char[] a = io.next().toCharArray();
    char[] b = io.next().toCharArray();
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') {
            io.println("YES");
            return;
        }
    }
    io.println("NO");
}

Queries for the Array

比较简单的写法就是用一个标记数组做记录，递增会向左传递，递减会向右传递，然后判断是否冲突即可。更进一步观察，可以发现只需要记录最大的递增位置，和最小的递减位置。

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
public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    boolean ok = true;
    int pos = -1, neg = n, cur = -1;
    for (char c : s) {
        if (c == '+') {
            cur++;
        } else if (c == '-') {
            if (cur-- == neg) {
                neg = n;
            }
            pos = Math.min(pos, cur);
        } else if (c == '0') {
            if (cur == pos || cur <= 0) {
                ok = false;
                break;
            }
            neg = Math.min(neg, cur);
        } else {
            if (neg <= cur) {
                ok = false;
                break;
            }
            pos = cur;
        }
    }
    io.println(ok ? "YES" : "NO");
}

Sorting By Multiplication

没想到啊。枚举负数前缀的长度：在负数前缀中，如果 \(a[i]<=a[i+1]\)，就需要操作一次；在正数后缀中，如果 \(a[i]>=a[i+1]\) 就需要操作一次。（下面的代码很妙啊，不需要加额外的判断语句。）

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();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] >= a[i + 1]) {
            cnt++;
        }
    }
    int ans = cnt;
    for (int i = 1; i < n; i++) {
        if (a[i - 1] >= a[i]) cnt--;
        ans = Math.min(ans, cnt + 1);
        if (a[i - 1] <= a[i]) cnt++;
    }
    io.println(ans);
}
发表更新算法 / Codeforces3 分钟读完 (大约424个字)

Pinely Round 2 (Div. 1 + Div. 2)

Channel

如果同时在线人数到达 \(n\)，就表示所有人都阅读过；否则，如果总上线人数大于等于 \(n\)，则有可能所有人阅读过；否则，不可能所有人阅读过。

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(), a = io.nextInt(), q = io.nextInt();
    String s = io.next();
    int cur = a, tot = a;
    for (int i = 0; i < q && cur < n; i++) {
        if (s.charAt(i) == '+') {
            cur++;
            tot++;
        } else {
            cur--;
        }
    }
    if (cur == n) {
        io.println("YES");
    } else if (tot >= n) {
        io.println("MAYBE");
    } else {
        io.println("NO");
    }
}

Split Sort

对于每个 \(p_{i}=k+1\) 和 \(p_{j}=k\) 并且 \(i<j\)，那么就一定要选一次 \(x=k+1\)。

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

MEX Repetition

每执行一次操作，就会去除最后一个数，并将 \(MEX\) 添加到序列头部。所以可以通过在数组末尾加上原始数组的 \(MEX\)，将操作看成是向左移动循环数组的起始索引。求原始数组的 \(MEX\) 可以使用求和公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    long sum = 0L;
    int[] a = new int[n + 1];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        sum += a[i];
    }
    a[n] = (int) ((long) (1 + n) * n / 2 - sum);
    k = k % (n + 1);
    for (int i = 0; i < n; i++) {
        io.print(a[(-k + n + 1 + i) % (n + 1)] + " ");
    }
    io.println();
}

Two-Colored Dominoes

横放的牌只会对列有影响，竖放的牌只会对行有影响，所以分别处理。按行遍历竖放的牌，每当遇到 \(U\) 就染上和上次相反的颜色，如果该行只包含奇数个 \(U\)，就返回 \(-1\)。横放的牌同理。

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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    char[][] s = new char[n][];
    for (int i = 0; i < n; i++) {
        s[i] = io.next().toCharArray();
    }
    final char[] aux = {'B', 'W'};
    for (int i = 0; i < n - 1; i++) {
        int xor = 0;
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'U') {
                s[i][j] = aux[xor];
                s[i + 1][j] = aux[xor ^ 1];
                xor ^= 1;
            }
        }
        if (xor != 0) {
            io.println(-1);
            return;
        }
    }
    for (int j = 0; j < m - 1; j++) {
        int xor = 0;
        for (int i = 0; i < n; i++) {
            if (s[i][j] == 'L') {
                s[i][j] = aux[xor];
                s[i][j + 1] = aux[xor ^ 1];
                xor ^= 1;
            }
        }
        if (xor != 0) {
            io.println(-1);
            return;
        }
    }
    for (int i = 0; i < n; i++) {
        io.println(new String(s[i]));
    }
}

Speedrun

其实思路是知道的，就是不知道怎么写。这个解法看着有点懵，可能其他解法会更好理解一点。注意题目给定 \(a_{i}<b_{i}\)。

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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
    int[] h = new int[n];
    for (int i = 0; i < n; i++) {
        h[i] = io.nextInt();
    }
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, idx -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int a = io.nextInt() - 1, b = io.nextInt() - 1;
        g[a].add(b);
    }
    // dp[i] 表示完成所有依赖第 i 个任务的任务需要的时间（从 h[i] 开始）
    long[] dp = new long[n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j : g[i]) {
            dp[i] = Math.max(dp[i], dp[j] + (h[j] - h[i] + k) % k);
        }
    }
    // dp[i] 表示完成所有依赖第 i 个任务的任务需要的时间（从零开始）
    long max = 0L;
    for (int i = 0; i < n; i++) {
        dp[i] += h[i];
        max = Math.max(max, dp[i]);
    }
    // 按照 h[i] 的大小，从小到大枚举起点
    Integer[] aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> h[i] - h[j]);
    long ans = Long.MAX_VALUE;
    for (int i : aux) {
        ans = Math.min(ans, max - h[i]);
        // 如果起点大于 h[i]，那么任务 i 的完成时间需要加 k，从而导致 dp[i] + k
        // 其实只要枚举入度为 0 的任务就行，但是即使任务 i 不是入度为 0 任务也没有关系，因为对答案没有影响
        max = Math.max(max, dp[i] + k);
    }
    io.println(ans);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×