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

AtCoder Beginner Contest 315

tcdr

模拟。

Java

1
2
3
4
5
6
7
8
9
public static void solve() {
    String s = io.next();
    var sb = new StringBuilder();
    Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
    for (char c : s.toCharArray()) {
        if (!set.contains(c)) sb.append(c);
    }
    io.println(sb.toString());
}

C++

1
2
3
4
5
6
7
8
void solve() {
    string s;
    cin >> s;
    s.erase(remove_if(s.begin(), s.end(), [&](char c) {
        return set{'a', 'e', 'i', 'o', 'u'}.count(c);
    }), s.end());
    cout << s << "\n";
}

The Middle Day

模拟。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void solve() {
    int m = io.nextInt();
    int[] d = new int[m];
    int tot = 0;
    for (int i = 0; i < m; i++) {
        d[i] = io.nextInt();
        tot += d[i];
    }
    int mid = (tot + 1) / 2;
    for (int i = 0; i < m; i++) {
        if (mid <= d[i]) {
            io.println(i + 1 + " " + mid);
            return;
        }
        mid -= d[i];
    }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int m;
    cin >> m;
    int tot = 0;
    vector<int> d(m);
    for (int i = 0; i < m; i++) {
        cin >> d[i];
        tot += d[i];
    }
    int mid = (tot + 1) / 2;
    for (int i = 0; i < m; i++) {
        if (mid <= d[i]) {
            cout << i + 1 << " " << mid << "\n";
            return;
        }
        mid -= d[i];
    }
}

Flavors

模拟。

Java

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
public static void solve() {
    int n = io.nextInt();
    List<Integer>[] buckets = new List[n + 1];
    Arrays.setAll(buckets, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        int f = io.nextInt(), s = io.nextInt();
        buckets[f].add(s);
    }
    int ans = 0, max1 = 0, max2 = 0;
    for (var bucket : buckets) {
        if (bucket.isEmpty()) continue;
        Collections.sort(bucket, (a, b) -> b - a);
        int a = bucket.get(0);
        if (a > max1) {
            max2 = max1;
            max1 = a;
        } else if (a > max2) {
            max2 = a;
        }
        if (bucket.size() < 2) continue;
        int b = bucket.get(1);
        ans = Math.max(ans, a + b / 2);
    }
    ans = Math.max(ans, max1 + max2);
    io.println(ans);
}

C++

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
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> buckets(n + 1);
    for (int i = 0; i < n; i++) {
        int f, s;
        cin >> f >> s;
        buckets[f].push_back(s);
    }
    int ans = 0, max1 = 0, max2 = 0;
    for (auto &bucket : buckets) {
        if (bucket.empty()) continue;
        nth_element(bucket.begin(), bucket.begin() + 1, bucket.end(), greater());
        if (bucket[0] > max1) {
            max2 = max1;
            max1 = bucket[0];
        } else if (bucket[0] > max2) {
            max2 = bucket[0];
        }
        if (bucket.size() < 2) continue;
        ans = max(ans, bucket[0] + bucket[1] / 2);
    }
    ans = max(ans, max1 + max2);
    cout << ans << "\n";
}

Magical Cookies

算是暴力吧。首先最多执行 \(m+n\) 次操作，然后每次操作将所有行和列遍历，判断是否可以标记。如果不优化，那么遍历的复杂度是 \(O(mn)\)，总时间复杂度就是 \(O(mn(m+n))\)，会超时。可以维护剩余的行数 \(r\) 和剩余的列数 \(c\)，那么如果某行的某颜色的数量等于列数，那么就说明可以标记该行，列同理。这样我们就可以只维护行列中的每个颜色有多少饼干，而不需要维护位置关系，从而将遍历的时间复杂度降为 \(O(26(m+n))\)。

Java

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
public static void solve() {
    int m = io.nextInt(), n = io.nextInt();
    String[] arr = new String[m];
    for (int i = 0; i < m; i++) {
        arr[i] = io.next();
    }
    int[][] row = new int[m][26];
    int[][] col = new int[n][26];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            row[i][arr[i].charAt(j) - 'a']++;
            col[j][arr[i].charAt(j) - 'a']++;
        }
    }
    int r = m, c = n;
    boolean[] vr = new boolean[m];
    boolean[] vc = new boolean[n];
    for (int k = 0; k < m + n; k++) {
        List<int[]> mr = new ArrayList<>();
        List<int[]> mc = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if (vr[i]) continue;
            for (int j = 0; j < 26; j++) {
                if (row[i][j] == c && c >= 2) {
                    mr.add(new int[]{i, j});
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (vc[i]) continue;
            for (int j = 0; j < 26; j++) {
                if (col[i][j] == r && r >= 2) {
                    mc.add(new int[]{i, j});
                }
            }
        }
        for (int[] p : mr) {
            r--;
            vr[p[0]] = true;
            for (int i = 0; i < n; i++) {
                col[i][p[1]]--;
            }
        }
        for (int[] p : mc) {
            c--;
            vc[p[0]] = true;
            for (int i = 0; i < m; i++) {
                row[i][p[1]]--;
            }
        }
    }
    io.println(r * c);
}

Prerequisites

首先找到第 \(1\) 本书的所有前置书，然后对所有书进行拓扑排序，将之前找到的前置书按拓扑排序的倒序打印即可。或者直接 DFS。。

Java

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
public static void solve() {
    int n = io.nextInt();
    int[] indegree = new int[n];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        int c = io.nextInt();
        for (int j = 0; j < c; j++) {
            int q = io.nextInt() - 1;
            g[i].add(q);
            indegree[q]++;
        }
    }

    boolean[] mark = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    q.offer(0);
    while (!q.isEmpty()) {
        int x = q.poll();
        for (int y : g[x]) {
            if (mark[y]) continue;
            mark[y] = true;
            q.offer(y);
        }
    }

    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.offer(i);
        }
    }
    Deque<Integer> ans = new ArrayDeque<>();
    while (!q.isEmpty()) {
        int x = q.poll();
        if (mark[x]) ans.push(x);
        for (int y : g[x]) {
            if (--indegree[y] == 0) {
                q.offer(y);
            }
        }
    }
    while (!ans.isEmpty()) io.print(ans.pop() + 1 + " ");
    io.println();
}

C++

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
void solve() {
    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            int q;
            cin >> q;
            q--;
            adj[i].push_back(q);
        }
    }

    vector<bool> mark(n);
    auto dfs = [&](auto self, int x) {
        if (mark[x]) {
            return;
        }
        for (auto y : adj[x]) {
            self(self, y);
        }
        mark[x] = true;
        if (x != 0) {
            std::cout << x + 1 << " ";
        }
    };
    dfs(dfs, 0);
    cout << "\n";
}

Shortcuts

动态规划，调试好久。。如果所有点都选，那么答案最多为 \(10^{9}\)，所以可以确定不选的点不会超过 \(30\)。然后定义状态 \(dp[i][j]\) 表示到达第 \(i\) 个点并且总共跳过 \(j\) 个点的最短距离。如何想到定义该状态呢，因为答案和具体选哪几个点无关，只和最短距离以及跳过多少个点有关，大概是这样吧。

Java

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() {
    int c = 30;
    int n = io.nextInt();
    int[] x = new int[n];
    int[] y = new int[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        y[i] = io.nextInt();
    }
    double[][] dp = new double[n][c];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    dp[0][0] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < c; j++) {
            for (int k = i + 1; k < n && k - i - 1 + j < c; k++) {
                int nj = j + k - i - 1;
                dp[k][nj] = Math.min(dp[k][nj], dp[i][j] + Math.sqrt((x[i] - x[k]) * (x[i] - x[k]) + (y[i] - y[k]) * (y[i] - y[k])));
            }
        }
    }
    double ans = Integer.MAX_VALUE;
    for (int i = 0; i < c; i++) {
        ans = Math.min(ans, dp[n - 1][i] + (i == 0 ? 0 : 1 << (i - 1)));
    }
    io.println(ans);
}

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

AtCoder Beginner Contest 314

3.14

1
2
3
4
5
public static void solve() {
    String s = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
    int n = io.nextInt();
    io.println(s.substring(0, n + 2));
}

Roulette

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void solve() {
    int n = io.nextInt();
    List<Integer>[] arr = new List[37];
    Arrays.setAll(arr, k -> new ArrayList<>());
    int[] cnt = new int[n];
    for (int i = 0; i < n; i++) {
        cnt[i] = io.nextInt();
        for (int j = 0; j < cnt[i]; j++) {
            arr[io.nextInt()].add(i);
        }
    }
    int x = io.nextInt(), min = 37;
    for (int i : arr[x]) min = Math.min(min, cnt[i]);
    List<Integer> ans = new ArrayList<>();
    for (int i : arr[x]) if (cnt[i] == min) ans.add(i);
    io.println(ans.size());
    for (int t : ans) io.print(t + 1 + " ");
    io.println();
}

Rotate Colored Subsequence

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();
    char[] s = io.next().toCharArray();
    List<Integer>[] arr = new List[m];
    Arrays.setAll(arr, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        arr[io.nextInt() - 1].add(i);
    }
    for (var v : arr) {
        if (v.size() == 0) continue;
        char c = s[v.get(v.size() - 1)];
        for (int i = v.size() - 2; i >= 0; i--) {
            s[v.get(i + 1)] = s[v.get(i)];
        }
        s[v.get(0)] = c;
    }
    io.println(new String(s));
}

LOWER

记录时间，每次进行全局操作时将当前时间加一，并记录操作的编号，每次进行局部操作时将对应位置的操作时间更新为当前时间。如果最后某个位置的时间小于当前时间，则需要变换大小写；否则，不需要变换大小写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void solve() {
    int n = io.nextInt();
    char[] s = io.next().toCharArray();
    int[] time = new int[n];
    int q = io.nextInt(), curTime = 0, flag = 0;
    while (q-- != 0) {
        int t = io.nextInt(), x = io.nextInt() - 1;
        char c = io.next().charAt(0);
        if (t == 1) {
            s[x] = c;
            time[x] = curTime;
        } else {
            flag = t;
            curTime++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (time[i] < curTime) {
            if (flag == 2) s[i] = Character.toLowerCase(s[i]);
            else s[i] = Character.toUpperCase(s[i]);
        }
    }
    io.println(new String(s));
}
发表更新算法 / AtCoder5 分钟读完 (大约797个字)

AtCoder Beginner Contest 313

To Be Saikyo

简单模拟。

1
2
3
4
5
6
7
public static void solve() {
    int n = io.nextInt(), x = io.nextInt(), max = 0;
    for (int i = 1; i < n; i++) {
        max = Math.max(max, io.nextInt());
    }
    io.println(Math.max(max - x + 1, 0));
}

Who is Saikyo?

如果 \(A\) 比 \(B\) 强，则让 \(B\) 的入度加一，最后入度为零的程序员就是最强的，如果多于一个那么返回 \(-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(), m = io.nextInt();
    int[] in = new int[n + 1];
    for (int i = 0; i < m; i++) {
        int u = io.nextInt(), v = io.nextInt();
        in[v]++;
    }
    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            ans = i;
            cnt++;
        }
    }
    io.println(cnt == 1 ? ans : -1);
}

Approximate Equalization 2

假设我们将数组 \(A\) 执行最少操作后得到数组 \(B\) ，那么 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 就是最小操作次数，因为必定有 \(\sum_{i=1}^{N}A_{i}=\sum_{i=1}^{N}B_{i}\) ，所以上述公式一定可以被二整除。题目要求 \(B\) 的最大值和最小值的差最多为一，那么 \(B\) 一定由 \(N-r\) 个 \(p\) ，以及 \(r\) 个 \(p+1\) 组成，其中 \(p=\frac{\sum_{i=1}^{N}B_{i}}{N},r=\sum_{i=1}^{N}B_{i}\bmod N\) 。然后问题就变为如何组织 \(A_{i}\) 和 \(B_{i}\) 的对应关系，使得 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 最小。显然对数组 \(A\) 进行升序排序，那么数组 \(B\) 的 \(N-r\) 个 \(p\) 对应 \(A\) 的前 \(N-r\) 个元素，数组 \(B\) 的 \(r\) 个 \(p+1\) 对应 \(A\) 的后 \(r\) 个元素，这样排列会使得操作次数最小。

PS：比赛时没什么思路，猜了个平均数，然后没有排序通过遍历比较大小来计算操作次数，结果和正解殊途同归了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = io.nextInt();
        sum += arr[i];
    }
    // 可以替换为快速选择
    Arrays.sort(arr);
    long ans = 0L, p = sum / n, r = sum % n;
    for (int i = 0; i < n; i++) {
        ans += Math.abs(arr[i] - (p + (i >= n - r ? 1 : 0)));
    }
    io.println(ans / 2);
}

Odd or Even

每次查询的返回值可以看作 \(A_{x_{1}}\oplus A_{x_{2}}\oplus \cdots \oplus A_{x_{k}}\) ，所以我们可以首先对前 \(k+1\) 个数进行 \(k+1\) 次查询，然后把所有查询结果异或，可以得到前 \(k+1\) 个数的异或值（因为在 \(k+1\) 次查询中，每个数出现 \(k\) 次，并且 \(k\) 是奇数），将该异或值分别与之前的查询结果异或，可以得到前 \(k+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
public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), xor = 0;
    List<Integer> aux;
    int[] ans = new int[n];
    for (int i = 0; i <= k; i++) {
        aux = new ArrayList<>();
        for (int j = 0; j <= k; j++) {
            if (i != j) aux.add(j);
        }
        ans[i] = query(aux);
        xor ^= ans[i];
    }
    for (int i = 0; i <= k; i++) ans[i] ^= xor;
    xor ^= ans[k] ^ ans[k - 1];
    aux = new ArrayList<>();
    for (int i = 0; i < k; i++) aux.add(i);
    for (int i = k + 1; i < n; i++) {
        aux.set(k - 1, i);
        ans[i] = query(aux) ^ xor;
    }
    io.print("! ");
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static int query(List<Integer> aux) {
    io.print("? ");
    for (int x : aux) {
        io.print(x + 1 + " ");
    }
    io.println();
    io.flush();
    return io.nextInt();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×