Ligh0x74's Blog

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

上一个遍历的整数

模拟。

class Solution {
    public List<Integer> lastVisitedIntegers(List<String> words) {
        int idx = -1;
        List<Integer> ans = new ArrayList<>();
        List<Integer> aux = new ArrayList<>();
        for (String word : words) {
            if (word.equals("prev")) {
                if (idx < 0) ans.add(-1);
                else ans.add(aux.get(idx--));
            } else {
                aux.add(Integer.valueOf(word));
                idx = aux.size() - 1;
            }
        }
        return ans;
    }
}

最长相邻不相等子序列 I

贪心。

class Solution {
    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i == n - 1 || groups[i] != groups[i + 1]) {
                ans.add(words[i]);
            }
        }
        return ans;
    }
}

最长相邻不相等子序列 II

和最长递增子序列有点像，处理的时候记录一下路径就好。

class Solution {
    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
        int pos = 0;
        int[] from = new int[n];
        int[] maxLen = new int[n];
        Arrays.fill(maxLen, 1);
        
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (maxLen[i] < maxLen[j] + 1 && groups[i] != groups[j] && words[i].length() == words[j].length()) {
                    int cnt = 0;
                    for (int k = 0; k < words[i].length(); k++) {
                        if (words[i].charAt(k) != words[j].charAt(k) && ++cnt > 1) {
                            break;
                        }
                    }
                    if (cnt == 1) {
                        maxLen[i] = maxLen[j] + 1;
                        from[i] = j;
                        if (maxLen[i] > maxLen[pos]) {
                            pos = i;
                        }
                    }
                }
            }
        }

        int m = maxLen[pos];
        LinkedList<String> ans = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            ans.addFirst(words[pos]);
            pos = from[pos];
        }
        return ans;
    }
}

和带限制的子多重集合的数目

明显是多重背包问题，求背包中物品重量在 $[l,r]$ 之间的方案数，朴素的转移方程为：

$$ dp[i][j]=\sum_{k=0}^{cnt[i]}{(dp[i-1][j-k\cdot w[i]])} $$

这样做的时间复杂度为 $O(rn)$，其中 $n$ 为 $nums$ 的长度。在题目的数据范围下，复杂度达到 $4\cdot 1e8$ 数量级，会导致超时。优化方式如下，当 $j\geq(cnt[i]+1)\cdot w[i]$ 且 $w[i]\neq 0$ 时，有：

$$ dp[i][j-w[i]]=dp[i-1][j-w[i]]+dp[i-1][j-2\cdot w[i]]+\cdots+dp[i-1][j-(cnt[i]+1)\cdot w[i]] $$

$$ dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]]+\cdots+dp[i-1][j-cnt[i]\cdot w[i]] $$

然后错位相减，得到：

$$ dp[i][j]=dp[i][j-w[i]]+(dp[i-1][j]-dp[i-1][j-(cnt[i]+1)\cdot w[i]]) $$

当 $j\geq(cnt[i]+1)\cdot w[i]$ 且 $w[i]=0$ 时，直接使用朴素转移方程，得到：

$$ dp[i][j]=\sum_{k=0}^{cnt[i]}{(dp[i-1][j])} $$

同理可得，当 $w[i]\leq j<(cnt[i]+1)\cdot w[i]$ 时，错位相减得到：

$$ dp[i][j]=dp[i][j-w[i]]+dp[i-1][j] $$

当 $j<w[i]$ 时，直接使用朴素转移方程，得到：

$$ dp[i][j]=dp[i-1][j] $$

这样做的时间复杂度为 $O(r\sqrt{S})$，其中 $S$ 表示 $nums$ 的元素和，$\sqrt{S}$ 表示 $nums$ 中不同元素的最大数量。不同元素的最大数量满足 $\frac{(0+(x-1))\cdot x}{2}\leq S$，解得 $x\leq \frac{1+\sqrt{1+8\cdot S}}{2}$。还有一些常数级别的优化，比如减少遍历的上界等。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countSubMultisets(List<Integer> nums, int l, int r) {
        int n = nums.size();

        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            map.merge(x, 1, Integer::sum);
        }

        int zero = map.getOrDefault(0, 0);
        map.remove(0);
        
        int m = map.size();
        int[] f = new int[r + 1];
        int[] g = new int[r + 1];
        f[0] = zero + 1;
        
        for (var e : map.entrySet()) {
            int w = e.getKey(), c = e.getValue();
            System.arraycopy(f, 0, g, 0, r + 1);
            for (int j = w; j <= r; j++) {
                f[j] = (f[j - w] + f[j]) % MOD;
                if (j - (c + 1) * w >= 0) {
                    f[j] = (f[j] - g[j - (c + 1) * w] + MOD) % MOD;
                }
            }
        }

        int ans = 0;
        for (int i = l; i <= r; i++) {
            ans = (ans + f[i]) % MOD;
        }
        return ans;
    }
}

分开处理，先做前缀和，再倒序减去某个前缀和，就可以不使用辅助数组 $g$：

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countSubMultisets(List<Integer> nums, int l, int r) {
        int n = nums.size();

        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            map.merge(x, 1, Integer::sum);
        }

        int zero = map.getOrDefault(0, 0);
        map.remove(0);

        int m = map.size();
        int[] f = new int[r + 1];
        f[0] = zero + 1;
        
        for (var e : map.entrySet()) {
            int w = e.getKey(), c = e.getValue();
            for (int j = w; j <= r; j++) {
                f[j] = (f[j - w] + f[j]) % MOD;
            }
            for (int j = r; j >= (c + 1) * w; j--) {
                f[j] = (f[j] - f[j - (c + 1) * w] + MOD) % MOD;
            }
        }

        int ans = 0;
        for (int i = l; i <= r; i++) {
            ans = (ans + f[i]) % MOD;
        }
        return 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();
}

方法二：外向基环树

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