Ligh0x74's Blog

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

3.14

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

Roulette

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

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

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

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

2 年前发表2 年前更新算法 / Codeforces7 分钟读完 (大约1014个字)

Codeforces Round 891 (Div. 3)

Array Coloring

要将数组分为奇偶性相同的两部分，那么奇数的个数一定要是偶数。

public static void solve() {
    int n = io.nextInt(), sum = 0;
    for (int i = 0; i < n; i++) {
        sum += io.nextInt();
    }
    io.println(sum % 2 == 0 ? "YES" : "NO");
}

Maximum Rounding

题目有点难读，其实就是大于等于 $5$ 的数可以向前进位，并且包括自己在内的所有低位全部置为 $0$ 。

public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length, c = 0, p = n;
    for (int i = n - 1; i > 0; i--) {
        if (s[i] >= '5') {
            s[i - 1]++;
            p = i;
        }
    }
    if (s[0] >= '5') io.println("1" + "0".repeat(n));
    else io.println(new String(s, 0, p) + "0".repeat(n - p));
}

Assembly via Minimums

对数组排序，最小值会出现 $n - 1$ 次，次小值会出现 $n - 2$ 次，以此类推，次大值出现 $1$ 次，最大值出现 $0$ 次，所以最后需要补一个最大值。

public static void solve() {
    int n = io.nextInt(), m = n * (n - 1) / 2;
    int[] b = new int[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);
    for (int i = 0; i < m; i += --n) {
        io.print(b[i] + " ");
    }
    io.println(b[m - 1]);
}

Strong Vertices

将公式变形，易知 $a_{u} - b_{u}$ 的值最大的元素是强壮的。

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 max = Integer.MIN_VALUE, cnt = 0;
    for (int i = 0; i < n; i++) {
        a[i] -= io.nextInt();
        if (a[i] > max) {
            max = a[i];
            cnt = 1;
        } else if (a[i] == max) {
            cnt++;
        }
    }
    io.println(cnt);
    for (int i = 0; i < n; i++) {
        if (a[i] == max) {
            io.print(i + 1 + " ");
        }
    }
    io.println();
}

Power of Points

对于每个 $x_{i}$ 构成的区间， $\sum_{p=1}^{10^9}f_{p}$ 表示所有区间包含的元素的个数的和。暴力计算的时间复杂度是 $O(n^{2})$ ，但是我们可以考虑 $x$ 从从小到大转移时，元素个数的变化量，从而使用 $O(n\log n)$ 的时间复杂度计算出所有答案。（也可以像官解一样推公式）

public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    int[] x = new int[n];
    Integer[] aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        sum += x[i];
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> x[i] - x[j]);
    long[] ans = new long[n];
    ans[aux[0]] = sum -= (long) n * (x[aux[0]] - 1);
    for (int k = 1; k < n; k++) {
        sum += (long) (k - (n - k)) * (x[aux[k]] - x[aux[k - 1]]);
        ans[aux[k]] = sum;
    }
    for (long s : ans) io.print(s + " ");
    io.println();
}

Sum and Product

解方程。。因为要求是整数解，所以根号下必须是完全平方数。还有要注意 $\Delta$ 小于零的情况，不过 Java 的开根函数在小于零的情况下会返回 NaN，转成整数就是零，在该题目的判断中不会引发问题，但还是最好特判一下。

public static void solve() {
    int n = io.nextInt();
    Map<Long, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.merge((long) io.nextInt(), 1, Integer::sum);
    }
    int q = io.nextInt();
    for (int i = 0; i < q; i++) {
        long x = io.nextInt(), y = io.nextLong();
        long d = x * x - 4 * y, s = (long) Math.sqrt(d);
        if (d < 0 || s * s != d) {
            io.print(0 + " ");
            continue;
        }
        long c1 = map.getOrDefault((x + s) / 2, 0);
        long c2 = map.getOrDefault((x - s) / 2, 0);
        if (s != 0) io.print(c1 * c2 + " ");
        else io.print(c1 * (c1 - 1) / 2 + " ");
    }
    io.println();
}

Counting Graphs

如果要在 $u$ 和 $v$ 之间添加一条边，那么首先要求 $u$ 和 $v$ 之间没有直接相连的边，并且新添加的边的权重要大于 $w$ 小于 $S$ ，这样才能保证最小生成树是给定的树。暴力求解的时间复杂度是 $O(n^{2})$ ，我们可以利用 Kruskal 算法优化，对边按权重从小到大排序，然后在连接两个顶点时计算两棵树之间顶点连接的方案数，将所有计算结果相乘就是答案。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt(), S = io.nextInt();
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < n - 1; i++) {
        int u = io.nextInt(), v = io.nextInt(), w = io.nextInt();
        edges.add(new int[]{u, v, w});
    }
    edges.sort((a, b) -> a[2] - b[2]);
    long ans = 1L;
    UnionFind uf = new UnionFind(n + 1);
    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        ans = (ans * fastPower(S - w + 1, (long) uf.size(u) * uf.size(v) - 1)) % MOD;
        uf.union(u, v);
    }
    io.println(ans);
}

2 年前发表2 年前更新语言 / C++几秒读完 (大约66个字)

禁用编译器扩展以确保程序符合 C++ 标准

g++ 编译器可以通过添加 -pedantic-errors 选项来禁用扩展：

g++ main.cpp -pedantic-errors

程序示例：

int main() {
    int n = 1024;
    int a[n];
    return 0;
}

运行结果：

// 禁用前正常运行
error: ISO C++ forbids variable length array 'a' // 禁用后报错