Ligh0x74's Blog

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

最短且字典序最小的美丽子字符串

滑动窗口。

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n = s.length();

        int lo = s.indexOf('1');
        if (lo < 0) {
            return "";
        }

        String ans = "";
        int hi = lo, cnt = 0;
        while (hi < n) {
            cnt += s.charAt(hi++) - '0';
            while (cnt > k || s.charAt(lo) == '0') {
                cnt -= s.charAt(lo++) - '0';
            }
            if (cnt == k) {
                String t = s.substring(lo, hi);
                if (ans.isEmpty() || t.length() < ans.length() || t.length() == ans.length() && t.compareTo(ans) < 0) {
                    ans = t;
                }
            }
        }
        return ans;
    }
}

找出满足差值条件的下标 II

维护最大值和最小值就行。

class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        int minIndex = 0, maxIndex = 0;
        for (int j = indexDifference; j < n; j++) {
            int i = j - indexDifference;
            
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            } else if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }

            if (nums[maxIndex] - nums[j] >= valueDifference) {
                return new int[]{maxIndex, j};
            }
            if (nums[j] - nums[minIndex] >= valueDifference) {
                return new int[]{minIndex, j};
            }
        }
        return new int[]{-1, -1};
    }
}

构造乘积矩阵

前后缀分解，将二维数组看作一维数组。

class Solution {
    private static final int MOD = 12345;

    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] p = new int[n][m];

        long suf = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                p[i][j] = (int) suf;
                suf = suf * grid[i][j] % MOD;
            }
        }

        long pre = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j] = (int) (p[i][j] * pre % MOD);
                pre = pre * grid[i][j] % MOD;
            }
        }

        return p;
    }
}

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

第 115 场力扣夜喵双周赛

上一个遍历的整数

模拟。

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

找出满足差值条件的下标 I