发表更新算法 / 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]);
}
发表更新算法 / Codeforces3 分钟读完 (大约483个字)

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

MEXanized Array

分类讨论，一开始以为不能有重复，花了很多时间。（菜）

1
2
3
4
5
public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), x = io.nextInt();
    if (n < k || x < k - 1) io.println(-1);
    else io.println((k - 1) * k / 2 + (n - k) * (x == k ? k - 1 : x));
}

Friendly Arrays

又看错题了，其实是道很简单的题。

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(), m = io.nextInt();
    int a = 0;
    for (int i = 0; i < n; i++) {
        a ^= io.nextInt();
    }
    int b = 0;
    for (int i = 0; i < m; i++) {
        b |= io.nextInt();
    }
    int min = a, max = a;
    if (n % 2 == 0) {
        min = a ^ (a & b);
    } else {
        max = a | b;
    }
    io.println(min + " " + max);
}

Colorful Table

一个数可以向外扩展到大于等于它的的数的位置，我们可以按 \(k\) 的大小记录左右端点，然后按照从大到小遍历，来扩展边界，最后计算答案。注意，排除不在数组中的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    boolean[] mark = new boolean[k];
    int[] l = new int[k], r = new int[k];
    Arrays.fill(l, n);
    Arrays.fill(r, -1);
    for (int i = 0; i < n; i++) {
        int a = io.nextInt() - 1;
        mark[a] = true;
        l[a] = Math.min(l[a], i);
        r[a] = i;
    }
    for (int i = k - 2; i >= 0; i--) {
        l[i] = Math.min(l[i], l[i + 1]);
        r[i] = Math.max(r[i], r[i + 1]);
    }
    for (int i = 0; i < k; i++) {
        if (!mark[i]) io.print(0 + " ");
        else io.print(2 * (r[i] - l[i] + 1) + " ");
    }
    io.println();
}

Prefix Purchase

又又犯蠢了，题目都没读明白。如果右边有更小的数，那么肯定选更小的数是更优的，可以从右向左遍历，将右边的最小值传递到当前位置。然后就是依次处理每个位置，细节见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    int k;
    cin >> k;
    for (int i = n - 2; i >= 0; i--) {
        c[i] = min(c[i], c[i + 1]);
    }
    int m = k;
    for (int i = 0; i < n; i++) {
        int x = i == 0 ? c[i] : c[i] - c[i - 1];
        if (x != 0) m = min(m, k / x);
        k -= x * m;
        cout << m << " \n"[i == n - 1];
    }
}
发表更新算法 / Codeforces5 分钟读完 (大约745个字)

Codeforces Round 900 (Div. 3)

How Much Does Daytona Cost?

所有长度为 \(1\) 的子数组，包含的元素必定是众数，所以只需判断 \(k\) 是否存在于数组中。

1
2
3
4
5
6
7
8
9
10
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    boolean ok = false;
    for (int i = 0; i < n; i++) {
        if (k == io.nextInt()) {
            ok = true;
        }
    }
    io.println(ok ? "YES" : "NO");
}

Aleksa and Stack

两个奇数相加得到偶数，两个奇数相乘得到奇数，奇数不会被偶数整除，所以构造一个全是奇数的序列即可。

1
2
3
4
5
6
7
public static void solve() {
    int n = io.nextInt();
    for (int i = 0; i < n; i++) {
        io.print(i * 2 + 1 + " ");
    }
    io.println();
}

Vasilije in Cacak

只要 \(x\) 在最小值和最大值之间，就总是可以被表示出来。

1
2
3
4
5
6
7
8
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    long x = io.nextLong();
    long a = (long) (1 + k) * k / 2;
    long b = (long) (n - k + 1 + n) * k / 2;
    if (x >= a && x <= b) io.println("YES");
    else io.println("NO");
}

Reverse Madness

数组被 \(l\) 和 \(r\) 分段，每一段都是相互独立的，可以单独考虑段内的反转情况。可以发现段内反转总是中心对称的，每个元素是否反转，取决于该元素位置被反转次数的奇偶性，可以用两边向中间求累加和的方式统计，也可以用差分数组。（比赛时我没有统计奇偶性，而是抵消相邻的反转的相同部分）

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
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    char[] s = io.next().toCharArray();
    int[] l = new int[k];
    for (int i = 0; i < k; i++) {
        l[i] = io.nextInt() - 1;
    }
    int[] r = new int[k];
    for (int i = 0; i < k; i++) {
        r[i] = io.nextInt() - 1;
    }
    int q = io.nextInt();
    int[] cnt = new int[n];
    for (int i = 0; i < q; i++) {
        cnt[io.nextInt() - 1]++;
    }
    for (int i = 0; i < k; i++) {
        int sum = 0;
        for (int a = l[i]; a <= (l[i] + r[i]) / 2; a++) {
            int b = r[i] + l[i] - a;
            sum += cnt[a] + cnt[b];
            if (sum % 2 == 1) {
                char c = s[a];
                s[a] = s[b];
                s[b] = c;
            }
        }
    }
    io.println(new String(s));
}

Iva & Pav

比较简单的做法是，计算每个比特位的前缀和，然后对每个查询二分答案的位置，将二分位置的值和 \(k\) 比较来判断二分的走向。比赛时我是用下面的方法做的，就是没想到二分，其实也可以不用二分，但是没看明白为什么，代码在此。

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

    // next[i][j] 表示 a[i] 的第 j 位等于 0 的下一个位置
    int[][] next = new int[n + 1][32];
    Arrays.fill(next[n], n);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 32; j++) {
            next[i][j] = next[i + 1][j];
            if ((a[i] >> j & 1) == 0) {
                next[i][j] = i;
            }
        }
    }

    int q = io.nextInt();
    while (q-- != 0) {
        int l = io.nextInt() - 1, k = io.nextInt();
        if (a[l] < k) {
            io.print("-1 ");
            continue;
        }

        int lo = l, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cur = 0;
            for (int i = 0; i < 32; i++) {
                if (next[mid][i] > mid && next[mid][i] == next[l][i]) {
                    cur |= 1 << i;
                }
            }
            if (cur >= k) lo = mid + 1;
            else hi = mid - 1;
        }
        io.print(hi + 1 + " ");
    }
    io.println();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×