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

AtCoder Beginner Contest 330

Counting Passes

模拟。

1
2
3
4
5
6
7
8
9
10
public static void solve() {
    int n = io.nextInt(), l = io.nextInt();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (io.nextInt() >= l) {
            ans++;
        }
    }
    io.println(ans);
}

Minimize Abs 1

等价于求 \(y=|x-a_{i}|\) 在区间 \([L,R]\) 内的最小值对应的 \(x\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), l = io.nextInt(), r = io.nextInt();
    for (int i = 0; i < n; i++) {
        int a = io.nextInt();
        if (l <= a && a <= r) {
            io.print(a + " ");
        } else if (a < l) {
            io.print(l + " ");
        } else {
            io.print(r + " ");
        }
    }
    io.println();
}

Minimize Abs 2

对于每个固定的 \(x\)，可以在 \(O(1)\) 时间内求出 \(|y^{2}+(x^{2}-D)|\) 的最小值（也可以二分），我们枚举 \([0,\lceil\sqrt{D}\rceil]\) 范围内的所有 \(x\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    long d = io.nextLong();
    long ans = Long.MAX_VALUE;
    long up = (long) Math.sqrt(d) + 1;
    for (long x = 0; x <= up; x++) {
        long t = x * x - d;
        if (t >= 0) {
            ans = Math.min(ans, t);
        } else {
            long y = (long) Math.sqrt(-t);
            ans = Math.min(ans, Math.abs(y * y + x * x - d));
            ans = Math.min(ans, Math.abs((y + 1) * (y + 1) + x * x - d));
        }
    }
    io.println(ans);
}

Counting Ls

对行列计数，然后枚举交叉点。

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();
    char[][] s = new char[n][];
    for (int i = 0; i < n; i++) {
        s[i] = io.next().toCharArray();
    }

    int[] row = new int[n];
    int[] col = new int[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == 'o') {
                row[i]++;
                col[j]++;
            }
        }
    }

    long ans = 0L;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == 'o' && col[j] > 1) {
                ans += (long) (col[j] - 1) * (row[i] - 1);
            }
        }
    }
    io.println(ans);
}

Mex and Update

因为只有 \(n\) 个数，所以只需要考虑 \([0,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
public static void solve() {
    int n = io.nextInt(), q = io.nextInt();
    int[] a = new int[n];
    int[] cnt = new int[n + 1];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        if (a[i] <= n) {
            cnt[a[i]]++;
        }
    }

    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i <= n; i++) {
        if (cnt[i] == 0) {
            set.add(i);
        }
    }

    while (q-- != 0) {
        int i = io.nextInt() - 1, x = io.nextInt();
        if (a[i] <= n && --cnt[a[i]] == 0) {
            set.add(a[i]);
        }
        a[i] = x;
        if (a[i] <= n && cnt[a[i]]++ == 0) {
            set.remove(a[i]);
        }
        io.println(set.first());
    }
}
发表更新算法 / AtCoder3 分钟读完 (大约461个字)

AtCoder Beginner Contest 326

2UP3DOWN

1
2
3
4
5
6
7
8
public static void solve() {
    int x = io.nextInt(), y = io.nextInt();
    if (y - x >= -3 && y - x <= 2) {
        io.println("Yes");
    } else {
        io.println("No");
    }
}

326-like Numbers

1
2
3
4
5
6
7
8
9
public static void solve() {
    int n = io.nextInt();
    for (; ; n++) {
        if (n / 100 * (n / 10 % 10) == n % 10) {
            io.println(n);
            return;
        }
    }
}

Peak

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

    int ans = 0;
    for (int i = 0, j = 0; j < n; j++) {
        while (a[j] - a[i] >= m) {
            i++;
        }
        ans = Math.max(ans, j - i + 1);
    }
    io.println(ans);
}

ABC Puzzle

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
public static void solve() {
    int n = io.nextInt();
    char[] r = io.next().toCharArray();
    char[] c = io.next().toCharArray();

    int[] row = new int[n];
    int[] col = new int[n];
    char[][] ans = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(ans[i], '.');
    }
    boolean ok = dfs(0, 0, r, c, ans, row, col, 0);

    if (!ok) {
        io.println("No");
        return;
    }
    io.println("Yes");
    for (int i = 0; i < n; i++) {
        io.println(new String(ans[i]));
    }
}

private static boolean dfs(int x, int y, char[] r, char[] c, char[][] ans, int[] row, int[] col, int cnt) {
    int n = r.length;
    if (x == n) {
        return cnt == 3 * n;
    }
    if (n - 1 - y >= 3 - Integer.bitCount(row[x])) {
        if (dfs(x + (y + 1) / n, (y + 1) % n, r, c, ans, row, col, cnt)) {
            return true;
        }
    }
    for (int i = 0; i < 3; i++) {
        if ((row[x] >> i & 1) == 1 || (col[y] >> i & 1) == 1) {
            continue;
        }
        if (row[x] == 0 && r[x] != 'A' + i) {
            continue;
        }
        if (col[y] == 0 && c[y] != 'A' + i) {
            continue;
        }
        row[x] |= 1 << i;
        col[y] |= 1 << i;
        ans[x][y] = (char) ('A' + i);
        if (dfs(x + (y + 1) / n, (y + 1) % n, r, c, ans, row, col, cnt + 1)) {
            return true;
        }
        row[x] ^= 1 << i;
        col[y] ^= 1 << i;
        ans[x][y] = '.';
    }
    return false;
}

Revenge of “The Salary of AtCoder Inc.”

概率 DP，答案为 \(\sum_{i=1}^{n}{A_{i}P_{i}}\)，而 \(P_{i}=\frac{1}{N}\sum_{j=0}^{i-1}{P_{j}}=P_{i-1}+\frac{1}{N}P_{i-1}\)。（这么简单，真没想到）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    long invn = pow(n, MOD - 2);
    long ans = 0L, p = invn;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt();
        ans = (ans + p * a) % MOD;
        p = (p + invn * p) % MOD;
    }
    io.println(ans);
}

private static long pow(long x, long n) {
    long res = 1L;
    for (; n != 0; x = x * x % MOD, n >>= 1) {
        if ((n & 1) == 1) {
            res = res * x % MOD;
        }
    }
    return res;
}
发表更新算法 / AtCoder3 分钟读完 (大约379个字)

AtCoder Beginner Contest 325

Takahashi san

1
2
3
4
5
public static void solve() {
    String s = io.next();
    io.next();
    io.println(s + " san");
}

World Meeting

比赛时用滑窗没有做出来，原来要滑两倍的数组长度啊。

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[] cnt = new int[24];
    for (int i = 0; i < n; i++) {
        int w = io.nextInt(), x = io.nextInt();
        cnt[x] += w;
    }

    int ans = 0;
    for (int i = 0; i < 24; i++) {
        int sum = 0;
        for (int j = 0; j < 9; j++) {
            sum += cnt[(i + j) % 24];
        }
        ans = Math.max(ans, sum);
    }
    io.println(ans);
}

Sensors

直接 DFS 或者并查集都行。

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
public static void solve() {
    int h = io.nextInt(), w = io.nextInt();
    boolean[][] g = new boolean[h][w];
    for (int i = 0; i < h; i++) {
        String s = io.next();
        for (int j = 0; j < w; j++) {
            if (s.charAt(j) == '#') {
                g[i][j] = true;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (g[i][j]) {
                ans++;
                dfs(i, j, g);
            }
        }
    }
    io.println(ans);
}

private static void dfs(int x, int y, boolean[][] g) {
    if (x < 0 || x >= g.length || y < 0 || y >= g[0].length || !g[x][y]) return;
    g[x][y] = false;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            dfs(x + i, y + j, g);
        }
    }
}

Printing Machine

贪心，对于每个时刻，我们选择已经进入传送带的，右端点最小的产品。

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 n = io.nextInt();
    long[][] aux = new long[n][];
    for (int i = 0; i < n; i++) {
        long t = io.nextLong(), d = io.nextLong();
        aux[i] = new long[]{t, t + d};
    }
    Arrays.sort(aux, (a, b) -> Long.compare(a[0], b[0]));

    int i = 0, ans = 0;
    Queue<Long> q = new PriorityQueue<>();
    for (long t = 0; ; t++) {
        if (q.isEmpty()) {
            if (i == n) break;
            t = aux[i][0];
        }
        while (i < n && aux[i][0] == t) {
            q.offer(aux[i++][1]);
        }
        while (!q.isEmpty() && q.peek() < t) {
            q.poll();
        }
        if (!q.isEmpty()) {
            ans++;
            q.poll();
        }
    }
    io.println(ans);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×