Ligh0x74's Blog

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

使二进制字符串变美丽的最少修改次数

长度为偶数的字符串要满足条件，那么将数组分为长度为 $2$ 的各个小段，使各个子数组满足条件一定是最优的。

class Solution {
    public int minChanges(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i += 2) {
            ans += (s.charAt(i) ^ s.charAt(i + 1)) & 1;
        }
        return ans;
    }
}

和为目标值的最长子序列的长度

0-1 背包，转移方程为 $dp[i][j]=\max(dp[i-1][j],dp[i-1][j-nums[i]]+1)$，注意初始化为 $-1$，并在转移时判断有效性。

class Solution {
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        int n = nums.size();
        int[] dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int x : nums) {
            for (int j = target; j >= x; j--) {
                if (dp[j - x] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - x] + 1);
                }
            }
        }
        return dp[target];
    }
}

子数组不同元素数目的平方和 II

动态规划 + 线段树，刚学的线段树就用上了，但是不太熟练，忘记我的线段树板子是从下标一开始操作，并且没有特判，如果操作的右端点比左端点小，那么就会导致数组越界，之后得修改一下板子。假设以 $i$ 为右端点的所有子数组的不同计数的平方和为 $dp[i]$，考虑如何转移到 $dp[i+1]$。

如果在 $[0,i]$ 中和 $nums[i+1]$ 相等的数为 $nums[j]$，则添加 $nums[i+1]$ 会使左端点在 $[j+1,i]$ 范围内的子数组的不同计数加 $1$，而左端点在 $[0,j]$ 范围内子数组的不同计数不变，最后不要忘记加上左端点在 $i+1$ 的子数组的不同计数的平方。我们可以得到如下转移方程，其中 $x_{i,j}$ 表示子数组 $nums[i,j]$ 的不同计数。

$$ \begin{align} dp[i] &=x_{0,i}^{2}+x_{1,i}^{2}+\cdots+x_{i,i}^{2} \\ dp[i+1] &=x_{0,i}^{2}+\cdots+x_{j,i}^{2}+(x_{j+1,i}+1)^{2}+\cdots+(x_{i,i}+1)^{2}+x_{i+1,i+1}^{2} \end{align} $$

然后我们将 $dp[i]$ 代入到 $dp[i+1]$ 中，得到：

$$ dp[i+1]=dp[i]+2\sum_{k=j+1}^{i}x_{k,i}+(i-j)+x_{i+1,i+1}^{2} $$

首先我们需要得到每个数，它左边第一个相同的数的位置，这可以在遍历的过程中使用哈希表得到。然后我们需要维护以当前位置为右端点，所有左端点表示的子数组的不同计数（区间修改），并且需要快速的求区间和，那么就可以使用线段树，这样我们只需要花费 $O(\log{n})$ 的时间进行转移。转移之后，不要忘记更新左端点在 $[j+1,i+1]$ 范围内的子数组的不同计数。

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

    public int sumCounts(int[] nums) {
        int n = nums.length;
        long ans = 0L, sum = 0L;
        var st = new SegmentTree(n);
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            int j = map.getOrDefault(nums[i - 1], 0);
            map.put(nums[i - 1], i);
            sum = (sum + 2 * st.get(j + 1, i) + i - j) % MOD;
            ans = (ans + sum) % MOD;
            st.add(j + 1, i, 1);
        }
        return (int) ans;
    }
}

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

AtCoder Beginner Contest 326

2UP3DOWN

public static void solve() {
    int x = io.nextInt(), y = io.nextInt();
    if (y - x >= -3 && y - x <= 2) {
        io.println("Yes");
    } else {
        io.println("No");
    }
}

326-like Numbers

public static void solve() {
    int n = io.nextInt();
    for (; ; n++) {
        if (n / 100 * (n / 10 % 10) == n % 10) {
            io.println(n);
            return;
        }
    }
}

Peak

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

    int ans = 0;
    for (int i = 0, j = 0; j < n; j++) {
        while (a[j] - a[i] >= m) {
            i++;
        }
        ans = Math.max(ans, j - i + 1);
    }
    io.println(ans);
}

ABC Puzzle

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

    int[] row = new int[n];
    int[] col = new int[n];
    char[][] ans = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(ans[i], '.');
    }
    boolean ok = dfs(0, 0, r, c, ans, row, col, 0);

    if (!ok) {
        io.println("No");
        return;
    }
    io.println("Yes");
    for (int i = 0; i < n; i++) {
        io.println(new String(ans[i]));
    }
}

private static boolean dfs(int x, int y, char[] r, char[] c, char[][] ans, int[] row, int[] col, int cnt) {
    int n = r.length;
    if (x == n) {
        return cnt == 3 * n;
    }
    if (n - 1 - y >= 3 - Integer.bitCount(row[x])) {
        if (dfs(x + (y + 1) / n, (y + 1) % n, r, c, ans, row, col, cnt)) {
            return true;
        }
    }
    for (int i = 0; i < 3; i++) {
        if ((row[x] >> i & 1) == 1 || (col[y] >> i & 1) == 1) {
            continue;
        }
        if (row[x] == 0 && r[x] != 'A' + i) {
            continue;
        }
        if (col[y] == 0 && c[y] != 'A' + i) {
            continue;
        }
        row[x] |= 1 << i;
        col[y] |= 1 << i;
        ans[x][y] = (char) ('A' + i);
        if (dfs(x + (y + 1) / n, (y + 1) % n, r, c, ans, row, col, cnt + 1)) {
            return true;
        }
        row[x] ^= 1 << i;
        col[y] ^= 1 << i;
        ans[x][y] = '.';
    }
    return false;
}

Revenge of “The Salary of AtCoder Inc.”

概率 DP，答案为 $\sum_{i=1}^{n}{A_{i}P_{i}}$，而 $P_{i}=\frac{1}{N}\sum_{j=0}^{i-1}{P_{j}}=P_{i-1}+\frac{1}{N}P_{i-1}$。（这么简单，真没想到）

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    long invn = pow(n, MOD - 2);
    long ans = 0L, p = invn;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt();
        ans = (ans + p * a) % MOD;
        p = (p + invn * p) % MOD;
    }
    io.println(ans);
}

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

2023-10-26发表2024-09-02更新基础 / 模板6 分钟读完 (大约826个字)

数据结构

本文内容参考 OI Wiki。

并查集

例题

P3367 【模板】并查集。

实现

class UnionFind {
    private final int[] f, s;
    private int c;

    public UnionFind(int n) {
        c = n;
        f = new int[n];
        s = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
            s[i] = 1;
        }
    }

    public int find(int x) {
        if (x != f[x]) f[x] = find(f[x]);
        return f[x];
    }

    public void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        f[ry] = rx;
        s[rx] += s[ry];
        c--;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int size(int x) {
        return s[find(x)];
    }

    public int count() {
        return c;
    }
}

树状数组

例题

实现

单点修改，区间查询

class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    public void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public long sum(int x) {
        long res = 0;
        for (; x > 0; x &= x - 1) {
            res += t[x];
        }
        return res;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

区间修改，单点查询

class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    private void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long res = 0L;
        for (int i = x; i > 0; i &= i - 1) {
            res += t[i];
        }
        return res;
    }

    public long get(int x) {
        return sum(x);
    }
}

区间修改，区间查询

class BIT {
    private final int n;
    private final long[] t1, t2;

    public BIT(int n) {
        this.n = n;
        t1 = new long[n + 1];
        t2 = new long[n + 1];
    }

    private void add(int i, int k) {
        long p = (long) k * i;
        for (; i <= n; i += i & -i) {
            t1[i] += k;
            t2[i] += p;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long s1 = 0, s2 = 0;
        for (int i = x; i > 0; i &= i - 1) {
            s1 += t1[i];
            s2 += t2[i];
        }
        return s1 * (x + 1) - s2;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

线段树

例题

实现

class SegmentTree {
    private final int n;
    private final long[] t, z;

    public SegmentTree(int[] a) {
        n = a.length;
        t = new long[4 * n];
        z = new long[4 * n];
        build(a, 1, 1, n);
    }

    private void build(int[] a, int i, int l, int r) {
        if (l == r) {
            t[i] = a[l - 1];
            return;
        }
        int mid = l + (r - l) / 2;
        build(a, 2 * i, l, mid);
        build(a, 2 * i + 1, mid + 1, r);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    private void lazy(int i, int lo, int hi, long k) {
        t[i] += k * (hi - lo + 1);
        z[i] += k;
    }

    private void down(int i, int lo, int hi) {
        if (z[i] == 0) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        lazy(2 * i, lo, mid, z[i]);
        lazy(2 * i + 1, mid + 1, hi, z[i]);
        z[i] = 0;
    }

    public void add(int l, int r, int k) {
        if (l > r) return;
        add(1, 1, n, l, r, k);
    }

    private void add(int i, int lo, int hi, int l, int r, int k) {
        if (lo >= l && hi <= r) {
            lazy(i, lo, hi, k);
            return;
        }
        down(i, lo, hi);
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) add(2 * i, lo, mid, l, r, k);
        if (r > mid) add(2 * i + 1, mid + 1, hi, l, r, k);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    public long get(int l, int r) {
        if (l > r) return 0L;
        return get(1, 1, n, l, r);
    }

    private long get(int i, int lo, int hi, int l, int r) {
        if (lo >= l && hi <= r) {
            return t[i];
        }
        down(i, lo, hi);
        long res = 0L;
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) res += get(2 * i, lo, mid, l, r);
        if (r > mid) res += get(2 * i + 1, mid + 1, hi, l, r);
        return res;
    }
}

稀疏表（Sparse Table）

例题

P3865 【模板】ST 表。

实现

1	System.out.println("TODO");

子数组不同元素数目的平方和 I