Ligh0x74's Blog

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

Same

public static void solve() {
    int n = io.nextInt();
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < n; i++) {
        set.add(io.nextInt());
    }
    io.println(set.size() == 1 ? "Yes" : "No");
}

3-smooth Numbers

public static void solve() {
    long n = io.nextLong();
    while (n % 2 == 0) n /= 2;
    while (n % 3 == 0) n /= 3;
    io.println(n == 1 ? "Yes" : "No");
}

Error Correction

额，很简单的题，赛时花费很长时间，代码写得很乱。

public static void solve() {
    int n = io.nextInt();
    String t = io.next();
    List<Integer> ans = new ArrayList<>();
    for (int k = 0; k < n; k++) {
        String s = io.next();

        int i = 0;
        for (; i < s.length() && i < t.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                break;
            }
        }

        int j = 0;
        for (; j < s.length() && j < t.length(); j++) {
            if (s.charAt(s.length() - 1 - j) != t.charAt(t.length() - 1 - j)) {
                break;
            }
        }

        boolean ok = s.length() == t.length() && i + j >= t.length() - 1;
        ok |= s.length() == t.length() + 1 && i + j >= t.length();
        ok |= s.length() == t.length() - 1 && i + j >= t.length() - 1;
        if (ok) {
            ans.add(k + 1);
        }
    }

    io.println(ans.size());
    ans.forEach(i -> io.print(i + " "));
    io.println();
}

Square Permutation

还是直接使用字符串更简单，要不然还要拆位。

public static void solve() {
    int n = io.nextInt();
    char[] s = io.next().toCharArray();
    Arrays.sort(s);
    long max = (long) Math.pow(10, n);

    int ans = 0;
    for (long i = 0; i * i < max; i++) {
        StringBuilder sb = new StringBuilder(String.valueOf(i * i));
        while (sb.length() < n) {
            sb.append("0");
        }
        char[] t = sb.toString().toCharArray();
        Arrays.sort(t);
        if (Arrays.equals(s, t)) {
            ans++;
        }
    }
    io.println(ans);
}

Joint Two Strings

记录每个字符串的子序列匹配目标字符串的最大前后缀的长度，因为答案和下标无关，所以使用排序 + 二分计算答案。

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

    int[] prefix = new int[n];
    int[] suffix = new int[n];
    for (int k = 0; k < n; k++) {
        String s = io.next();

        for (int i = 0; i < s.length() && prefix[k] < t.length(); i++) {
            if (s.charAt(i) == t.charAt(prefix[k])) {
                prefix[k]++;
            }
        }

        for (int i = 0; i < s.length() && suffix[k] < t.length(); i++) {
            if (s.charAt(s.length() - 1 - i) == t.charAt(t.length() - 1 - suffix[k])) {
                suffix[k]++;
            }
        }
    }

    Arrays.sort(suffix);

    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefix[i] + suffix[mid] >= t.length()) hi = mid - 1;
            else lo = mid + 1;
        }
        ans += n - lo;
    }
    io.println(ans);
}

Beautiful Path

二分答案，将除法转化为乘法，因为顶点的边限制 $u<v$，所以从 $1$ 到 $n$ 处理顶点就是拓扑序，并且一定没有环，拓扑序动态规划求最长路径即可。（额，昨天刚做拓扑序动态规划求最长路径，竟然还没做出这题。）

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    int[] in = new int[n];
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1, b = io.nextInt(), c = io.nextInt();
        g[u].add(new int[]{v, b, c});
        in[v]++;
    }

    double lo = 0, hi = 1e4;
    while (hi - lo >= 1e-10) {
        double mid = lo + (hi - lo) / 2;
        if (check(g, in.clone(), mid)) lo = mid;
        else hi = mid;
    }
    io.println(lo);
}

private static boolean check(List<int[]>[] g, int[] in, double x) {
    int n = g.length;
    double[] dist = new double[n];
    Arrays.fill(dist, Long.MIN_VALUE);

    dist[0] = 0;
    for (int u = 0; u < n; u++) {
        for (int[] t : g[u]) {
            int v = t[0], b = t[1], c = t[2];
            if (dist[v] < dist[u] + b - c * x) {
                dist[v] = dist[u] + b - c * x;
            }
        }
    }

    return dist[n - 1] >= 0;
}

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

第 367 场力扣周赛

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

滑动窗口。

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