Ligh0x74's Blog

2023-10-24发表2023-10-24更新算法 / Codeforces7 分钟读完 (大约1081个字)

Simple Design

public static void solve() {
    int x = io.nextInt(), k = io.nextInt();
    while (sum(x) % k != 0) {
        x++;
    }
    io.println(x);
}

private static int sum(int x) {
    int res = 0;
    while (x != 0) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

好难啊，做得很慢。对于每个 $i$，如果它是满足条件的，那么 $[n-i,n-1]$ 需要全为 $0$，它的最少操作次数为 $[n-i,n-1]$ 中所有值为 $1$ 的下标和，减去 $[0,n-i-1]$ 中最近的值为 $0$ 的对应个数的下标和。我们可以使用双指针 $O(n)$ 的计算所有 $i$，具体见代码。指针 $j$ 枚举每个下标，同时求出后缀的下标和，指针 $i$ 指向指针 $j$ 需要的最远的 $0$ 的下标位置，同时求出后缀值为 $0$ 的下标和，它们的差值就是 $j$ 的最少操作次数。

public static void solve() {
    int n = io.nextInt();
    String s = io.next();

    long sum = 0L;
    int i, j, cnt = 0;
    for (i = n - 1, j = n - 1; i >= 0; j--) {
        cnt++;
        sum += j;
        for (; i >= 0 && cnt > 0; i--) {
            if (s.charAt(i) == '0') {
                cnt--;
                sum -= i;
            }
        }
        io.print(cnt > 0 ? "-1 " : sum + " ");
    }
    io.println("-1 ".repeat(j + 1));
}

发现一个超级简单的写法，基本思路就是从低到高放置 $0$，操作次数即为 $0$ 的移动次数，废话不多说，代码很好懂。

public static void solve() {
    int n = io.nextInt();
    char[] s = io.next().toCharArray();

    long ans = 0L;
    int l = n - 1, r = n - 1;
    for (; l >= 0; l--) {
        if (s[l] == '0') {
            ans += r - l;
            r--;
            io.print(ans + " ");
        }
    }
    io.println("-1 ".repeat(r + 1));
}

Medium Design

最小值一定在位置 $1$ 或位置 $m$，我们可以考虑处理区间不包含 $1$ 和不包含 $m$ 两种情况下，能够得到的最大值，根据简单的推导可以知道问题是等价的。如何计算最大值，根据题解所说似乎是扫描线算法，使用 $(l,1)$ 表示进入某个区间，$(r,-1)$ 表示离开某个区间，注意初始时我们将每个左端点减 $1$，表示从区间 $0$ 开始算，$(l,r)$ 是左闭右开区间，所以 $r$ 表示离开某个区间，然后每当处理完某个端点就更新答案。（其实也可以使用差分哈希表进行区间求和）

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] l = new int[n];
    int[] r = new int[n];
    for (int i = 0; i < n; i++) {
        l[i] = io.nextInt() - 1;
        r[i] = io.nextInt();
    }
    // 第一次扫描，不包含第一个位置
    List<int[]> list = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (l[i] != 0) {
            list.add(new int[]{l[i], 1});
            list.add(new int[]{r[i], -1});
        }
    }
    list.sort((a, b) -> a[0] - b[0]);
    int ans = sweep(list);
	// 第二次扫描，不包含最后一个位置
    list.clear();
    for (int i = 0; i < n; i++) {
        if (r[i] != m) {
            list.add(new int[]{l[i], 1});
            list.add(new int[]{r[i], -1});
        }
    }
    list.sort((a, b) -> a[0] - b[0]);
    ans = Math.max(ans, sweep(list));
    io.println(ans);
}

private static int sweep(List<int[]> list) {
    // cnt 表示在多少个区间内
    // lst 表示上次处理的端点
    int res = 0, cnt = 0, lst = 0;
    for (int[] t : list) {
        if (t[0] > lst) {
            res = Math.max(res, cnt);
        }
        cnt += t[1];
        lst = t[0];
    }
    return res;
}

Counting Rhyme

一对数 $x,y$ 不能同时被数组中的数整除，即 $\gcd(x,y)$ 不能被数组中的数整除。我们首先可以计算出数组中有多少对数它们的 $\gcd=1,2,3\dots,n$，然后排除掉能够被数组中的数整除的 $\gcd$，剩下的 $\gcd$ 对应的对数之和就是答案。第一步可以使用动态规划求解，转移方程如下：

$$ sum = cnt[i]+cnt[2\times i]+\cdots+cnt[k\times i] \\ dp[i]= \frac{sum\times (sum-1)}{2}-(dp[2\times i]+dp[3\times i]+\cdots+dp[k\times i]) $$

第二步切记不能枚举数组中的数来排除，这样在所有值都为 $1$ 的样例下时间复杂度会达到 $O(n^{2})$，除非将数组去重，或者像下面代码一样枚举。最后计算答案即可。本题的另一种解法是 GCD 卷积，暂时不学。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    int[] cnt = new int[n + 1];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        cnt[a[i]]++;
    }

    long[] dp = new long[n + 1];
    for (int i = n; i > 0; i--) {
        long tot = 0L;
        for (int j = i; j <= n; j += i) {
            tot += cnt[j];
            dp[i] -= dp[j];
        }
        dp[i] += tot * (tot - 1) / 2;
    }

    for (int i = 1; i <= n; i++) {
        if (cnt[i] != 0) {
            for (int j = i; j <= n; j += i) {
                dp[j] = 0;
            }
        }
    }

    long ans = 0L;
    for (int i = 1; i <= n; i++) {
        ans += dp[i];
    }
    io.println(ans);
}

2023-10-10发表2023-10-10更新算法 / Codeforces7 分钟读完 (大约1080个字)

Educational Codeforces Round 156 (Rated for Div. 2)

Sum of Three

当 n <= 6 || n == 9 时，不能凑出三个不同的不能被 $3$ 整除的正整数，其他情况均可以通过以下方式凑出。

public static void solve() {
    int n = io.nextInt();
    if (n <= 6 || n == 9) {
        io.println("NO");
        return;
    }
    int a = 1, b = 2, c = n - 3;
    if (c % 3 == 0) {
        c -= 2;
        b += 2;
    }
    io.println("YES");
    io.println(a + " " + b + " " + c);
}

Fear of the Dark

可以分为四种情况：点 $O$ 和点 $P$ 在圆 $A$ 内/上；点 $O$ 和点 $P$ 在圆 $B$ 内/上；点 $O$ 和点 $P$ 分别在圆 $A$ 和圆 $B$ 内/上，并且圆 $A$ 和圆 $B$ 相切/相交；点 $O$ 和点 $P$ 分别在圆 $B$ 和圆 $A$ 内/上，并且圆 $A$ 和圆 $B$ 相切/相交。

方法一：浮点二分

public static void solve() {
    double px = io.nextInt(), py = io.nextInt();
    double ax = io.nextInt(), ay = io.nextInt();
    double bx = io.nextInt(), by = io.nextInt();

    double lo = 0, hi = 1e4;
    while (hi - lo > 1e-9) {
        double mid = lo + (hi - lo) / 2;
        boolean oToA = dist(0, 0, ax, ay) <= mid;
        boolean aToP = dist(ax, ay, px, py) <= mid;
        boolean oToB = dist(0, 0, bx, by) <= mid;
        boolean bToP = dist(bx, by, px, py) <= mid;
        boolean aToB = dist(ax, ay, bx, by) <= 2 * mid;
        if ((oToA && aToP) || (oToB && bToP) || (oToA && aToB && bToP) || (oToB && aToB && aToP)) hi = mid;
        else lo = mid;
    }
    io.println(hi);
}

private static double dist(double x1, double y1, double x2, double y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

方法二：直接计算

public static void solve() {
    double px = io.nextInt(), py = io.nextInt();
    double ax = io.nextInt(), ay = io.nextInt();
    double bx = io.nextInt(), by = io.nextInt();

    double oToA = dist(0, 0, ax, ay);
    double aToP = dist(ax, ay, px, py);
    double oToB = dist(0, 0, bx, by);
    double bToP = dist(bx, by, px, py);
    double aToB = dist(ax, ay, bx, by);

    double ans = Math.max(oToA, aToP);
    ans = Math.min(ans, Math.max(oToB, bToP));
    ans = Math.min(ans, Math.max(oToA, Math.max(aToB / 2, bToP)));
    ans = Math.min(ans, Math.max(oToB, Math.max(aToB / 2, aToP)));
    io.println(ans);
}

private static double dist(double x1, double y1, double x2, double y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

Decreasing String

二分删除的字符数 $p$，可以通过计算得到 $q=pos-\frac{(n+(n-p+1))\cdot p}{2}$，则答案为 $s_{1+p}[q]$，可以使用单调栈删除字符，然后获取答案即可。

public static void solve() {
    String s = io.next();
    long pos = io.nextLong();

    int n = s.length();
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if ((long) (n + n - mid + 1) * mid / 2 < pos) lo = mid + 1;
        else hi = mid - 1;
    }
    int p = hi, q = (int) (pos - (long) (n + n - hi + 1) * hi / 2);

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        while (p > 0 && !sb.isEmpty() && sb.charAt(sb.length() - 1) > s.charAt(i)) {
            sb.deleteCharAt(sb.length() - 1);
            p--;
        }
        sb.append(s.charAt(i));
    }
    io.print(sb.charAt(q - 1));
}

Monocarp and the Set

很容易想到当 s[0] == '?' 时，方案数为 $0$，并且 > 和 < 符号的位置放什么数都是确定的，也就是说只有 ? 位置对答案有贡献。分别考虑每个 ? 位置（从位置 $1$ 开始，因为位置 $0$ 不能是 ?），假设该位置的下标为 $i$，那么它是第 $i+2$ 个的数（因为添加第 $1$ 个数时，不会记录字符到 $s$ 中，并且下标从 $0$ 开始，所以加 $2$），第 $i+2$ 个数必须要大于前 $i+1$ 个数的最小值，小于前 $i+1$ 个数的最大值。我们可以将前 $i+1$ 个数排成有序的序列，然后根据大小将第 $i+2$ 个数插入到序列中，总共有 $i+2$ 个插入位置，但在限制条件下，我们只能选择 $i$ 个位置进行插入，对所有 ? 位置累乘 $i$ 即可得到当前字符串的插入方案数。

看半天才懂，很多题解只提到插入法，根本没提到有序序列，只要知道是根据大小插入就很简单了。也就是说，插入时根本不关心当前是什么数，只关心当前数在前面数的最大值和最小值之间。在将所有的数插入完成后，所有 ? 位置是什么数就随之确定，也就确定了一种方案。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    char[] s = io.next().toCharArray();

    long ans = 1L;
    for (int i = 1; i < n - 1; i++) {
        if (s[i] == '?') ans = ans * i % MOD;
    }

    query(s, ans);
    while (m-- != 0) {
        int i = io.nextInt() - 1;
        char c = io.next().charAt(0);
        if (i != 0 && s[i] == '?') {
            ans = ans * pow(i, MOD - 2) % MOD;
        }
        s[i] = c;
        if (i != 0 && s[i] == '?') {
            ans = ans * i % MOD;
        }
        query(s, ans);
    }
}

private static void query(char[] s, long ans) {
    if (s[0] == '?') io.println(0);
    else io.println(ans);
}

private static int pow(int a, int n) {
    long res = 1L, x = a;
    while (n != 0) {
        if ((n & 1) == 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return (int) res;
}

2023-10-09发表2023-10-09更新算法 / Codeforces7 分钟读完 (大约1115个字)

Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)

Goals of Victory

所有效率之和等于零。

public static void solve() {
    int n = io.nextInt(), sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += io.nextInt();
    }
    io.println(-sum);
}

Helmets in Night Light

贪心选择最小花费的通知，注意维护已经被通知的下标，根据该下标判断是否需要加 $p$，并且如果某个人通知其他人的成本大于 $p$，则他不会通知其他人。发现大佬的解法好简单，取一个最小值，维护一个剩余人数即可。

public static void solve() {
    int n = io.nextInt(), p = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }

    var aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> b[i] - b[j]);

    long ans = p;
    int r = n - 1;
    for (int i : aux) {
        int x = Math.min(r, a[i]);
        ans += (long) x * Math.min(p, b[i]);
        r -= x;
    }
    io.println(ans);
}

Joyboard

分类讨论，注意被 $n$ 整除的数。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
    if (k == 3) io.println(Math.max(0, m - n - m / n + 1));
    else if (k == 2) io.println(m / n + Math.min(n - 1, m));
    else if (k == 1) io.println(1);
    else io.println(0);
}

Effects of Anti Pimples

很容易的想到计算选择每个索引位置，能够得到的最大分数，时间复杂度为 $O(n\log{n})$。然后计算每个位置有多少种方案，比赛时我以为选择一个索引位置，默认就选择了它的所有倍数位置，导致不会做。其实只要排序，然后每个位置的方案数就是它左边的数选或不选的方案数，这样可以保证不会重复计算，所以~~快速幂~~计算方案数（可以在遍历的时候计算方案数），再乘以得分累加到答案即可。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = io.nextInt();
    }

    dp[0] = Integer.MAX_VALUE;
    for (int i = 1; i <= n; i++) {
        for (int j = 2 * i; j <= n; j += i) {
            dp[i] = Math.max(dp[i], dp[j]);
        }
    }

    Arrays.sort(dp);
    long ans = 0L, pow = 1L;
    for (int i = 0; i < n; i++) {
        ans = (ans + dp[i] * pow) % MOD;
        pow = pow * 2 % MOD;
    }
    io.println(ans);
}

Autosynthesis

方法一：内向基环树

对于每个 $i$，建立一条从 $i$ 指向 $a_{i}$ 的边，最终会得到多个内向基环树。规则一：入度为零的节点不会被选择；规则二：如果一个节点的所有入度节点都被选择，那么它不会被选择；规则三：如果一个节点不被选择，那么它指向的节点会被选择。（以上规则可以使用拓扑序 + 染色法实现）

如图，数组为 $[2,3,4,5,6,3,3,4]$，剩余索引 $[1,5,7,8]$，剩余元素 $[2,6,3,4]$，选择索引 $[2,6,3,4]$。应用规则一，得出索引 $[1,7,8]$ 不被选择；应用规则三，得出索引 $[2,3,4]$ 被选择；应用规则二，得出索引 $[5]$ 不被选择；应用规则三，得出索引 $[6]$ 被选择。

特殊情况，如果内向基环树没有环外节点，无法应用上述规则，那么需要单独对环交替染色，若此时环的长度为奇数，则没有解，其他情况均有解。也就是说，当且仅当内向基环树没有环外节点，且环的长度为奇数时，无解。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt() - 1;
    }

    int[] in = new int[n];
    for (int i = 0; i < n; i++) {
        in[a[i]]++;
    }

    // 拓扑序染色（-1 表示不选择，1 表示选择）
    int[] col = new int[n];
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.offer(i);
            col[i] = -1;
        }
    }
    while (!q.isEmpty()) {
        int x = q.poll(), y = a[x];
        if (col[y] != 0) continue;
        if (--in[y] == 0 || col[x] == -1) {
            q.offer(y);
            col[y] = -col[x];
        }
    }

    // 单独处理没有环外节点的基环树
    for (int i = 0; i < n; i++) {
        if (col[i] != 0) continue;
        int j = i, pre = -1;
        while (col[j] == 0) {
            col[j] = -pre;
            pre = col[j];
            j = a[j];
        }
        if (col[j] == pre) {
            io.println(-1);
            return;
        }
    }

    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (col[i] == -1) ans.add(a[i] + 1);
    }
    io.println(ans.size());
    for (int x : ans) {
        io.print(x + " ");
    }
    io.println();
}

方法二：外向基环树

好像有建立外向基环树的解法，没时间看，在此。