Ligh0x74's Blog

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

Sorting with Twos

因为每次只能操作区间 $[1,2^{m}]$，所以 $[2^{m}+1,2^{m+1}]$ 内的所有数是同时进行操作的，它们需要满足非递减的性质，最后不要忘记结尾不能操作的数也需要满足条件。

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

    for (int i = 1; 1 << i <= n; i++) {
        int j = Math.min(1 << (i + 1), n);
        for (int k = (1 << i) + 1; k < j; k++) {
            if (a[k] > a[k + 1]) {
                io.println("NO");
                return;
            }
        }
    }
    io.println("YES");
}

Deja Vu

如果一个数能够被 $2^{i}$ 整除，那么操作之后，它只能被所有小于等于 $2^{i-1}$ 的二的幂整除。所以预处理所有修改，只保留满足递减顺序的修改，然后模拟即可。或者也可以直接修改，不用预处理，在修改之前判断一下是否比上次小就行。

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

    int mask = 0;
    for (int i = 0; i < q; i++) {
        int x = io.nextInt();
        if (mask == 0 || (1 << x) <= (mask & -mask)) {
            mask |= 1 << x;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 30; j >= 0; j--) {
            if ((mask >> j & 1) == 1 && a[i] % (1 << j) == 0) {
            	a[i] += 1 << (j - 1);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        io.print(a[i] + " ");
    }
    io.println();
}

Smilo and Monsters

比赛时我是排序 + 相向双指针模拟的，先干前面的怪物，如果计数和最后一个的怪物群数量相等，则使用终极攻击，比较麻烦的是双指针到达同一个位置时，需要特判一些情况。然后下面的解法，很简洁啊。似乎总是可以使用普通攻击干掉怪物总数的一半向上取整，并且使用终极攻击干掉总数的一半向下取整。然后排序数组并倒序遍历，使得一次终极攻击干掉尽可能多的怪物，这样就得到最少攻击次数。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    long sum = 0L;
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        sum += a[i];
    }
    Arrays.sort(a);
    long ans = (sum + 1) / 2;
    sum /= 2;
    for (int i = n - 1; i >= 0 && sum > 0; i--) {
        sum -= a[i];
        ans++;
    }
    io.println(ans);
}

$f(x)$ 表示 $x$ 的二进制表示中最高位的 $1$ 所在的位数 $y$，而 $g(x)$ 表示满足 $y^{z}<= x$ 条件的最大的 $z$。可以发现如果 $y=2,x=10^{18}$，则 $z=59$。我们可以枚举所有 $y\in[2,59]$，对于特定的 $y$，枚举不同的 $z$ 覆盖的区间范围。得到各个区间范围内所有数的 $z$ 值，我们就可以在 $O(\log{(r-l+1)})$ 的时间复杂度内执行查询。为了避免乘法溢出，在进行比较时需要使用除法。其他人代码有直接使用 $\log$ 的，也比较简单啊，我还以为很麻烦，结果溢出没想到换除法。当然也可以维护前缀和，然后二分区间位置来进行查询。

private static final int MOD = (int) 1e9 + 7;
private static final List<long[]>[] list = new List[60];

static {
    Arrays.setAll(list, k -> new ArrayList<>());

    for (int f = 2; f < 60; f++) {
        long l = 1L << f, r = (1L << f + 1) - 1;

        long k = f, g = 1;
        while (k <= l / f) {
            k *= f;
            g++;
        }

        for (; l <= r; l = k + 1, g++) {
            k = k <= r / f ? k * f - 1 : r;
            list[f].add(new long[]{l, k, g});
        }
    }
}

public static void solve() {
    long ans = 0L;
    long l = io.nextLong(), r = io.nextLong();
    int i = 63 - Long.numberOfLeadingZeros(l);
    int j = 63 - Long.numberOfLeadingZeros(r);
    for (; i <= j; i++) {
        for (long[] t : list[i]) {
            ans = (ans + (Math.max(0, Math.min(t[1], r) - Math.max(t[0], l) + 1)) * t[2]) % MOD;
        }
    }
    io.println(ans);
}

A Growing Tree

每个节点的编号是添加该节点时树的大小，因为修改操作不会影响还未添加到树上的节点，所以我们对每个修改操作添加一个编号（时间），表示修改所影响的范围。我们可以使用单点修改、区间查询的树状数组维护修改操作的编号，然后按照 DFS 序遍历树，每当遍历到一个节点，使用树状数组进行单点修改，因为遍历是 DFS 序，所以当前节点的祖先节点已经进行过修改操作，那么当前节点的答案就是所有大于等于该节点编号的修改操作之和。

那么有没有可能该答案会包含其他满足编号大于当前节点的非祖先节点的修改操作呢，不会包含，因为遍历是 DFS 序，DFS 返回时会取消对节点的修改操作，所以每当遍历到一个节点，修改操作只会包含其祖先节点的修改操作。特别注意，数组开 $q+2$ 的大小，因为初始时有一个根节点，所以节点数量最多为 $q+1$，然后编号从 $1$ 开始。

public static void solve() {
    int q = io.nextInt(), sz = 1;
    List<int[]>[] queries = new List[q + 2];
    Arrays.setAll(queries, k -> new ArrayList<>());
    List<Integer>[] g = new List[q + 2];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < q; i++) {
        int t = io.nextInt();
        if (t == 1) {
            int v = io.nextInt();
            g[v].add(++sz);
        } else {
            int v = io.nextInt(), x = io.nextInt();
            queries[v].add(new int[]{sz, x});
        }
    }
    var bit = new BIT(sz);
    long[] ans = new long[sz + 1];
    dfs(1, sz, g, queries, bit, ans);
    for (int i = 1; i <= sz; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static void dfs(int x, int sz, List<Integer>[] g, List<int[]>[] queries, BIT bit, long[] ans) {
    for (int[] q : queries[x]) {
        bit.add(q[0], q[1]);
    }
    ans[x] = bit.get(x, sz);
    for (int y : g[x]) {
        dfs(y, sz, g, queries, bit, ans);
    }
    for (int[] q : queries[x]) {
        bit.add(q[0], -q[1]);
    }
}

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

第 369 场力扣周赛

找出数组中的 K-or 值

模拟。

class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < 31; i++) {
            int cnt = 0;
            for (int x : nums) {
                cnt += x >> i & 1;
            }
            if (cnt >= k) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

数组的最小相等和

分类讨论。所有 $0$ 都必须被替换为正整数，那么首先将所有 $0$ 替换为 $1$。如果两个数组中都有 $0$，则此时得到的最大的数组和就应该是答案，因为较小的一方总是可以使用更大的正整数替换 $0$，使得两个数组的元素和相等。如果某个数组的和不等于最大和，并且数组中不包含 $0$，那么就无法使两个数组的元素和相等。

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        int cnt1 = 0, cnt2 = 0;
        long sum1 = 0L, sum2 = 0L;
        for (int x : nums1) {
            if (x == 0) cnt1++;
            sum1 += x;
        }
        for (int x : nums2) {
            if (x == 0) cnt2++;
            sum2 += x;
        }
        long max = Math.max(sum1 + cnt1, sum2 + cnt2);
        if (sum1 != max && cnt1 == 0) return -1;
        if (sum2 != max && cnt2 == 0) return -1;
        return max;
    }
}

使数组变美的最小增量运算数

按照灵神的题解，每个位置的状态就是它右边有多少个数小于 $k$，加上这个维度就可以做记忆化搜索，然后转递推真的很妙。题解区还有其他的状态定义方式，可以看看。代码就贴灵神的。（这题感觉很不错，没有见过的类型）

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        long f0 = 0, f1 = 0, f2 = 0;
        for (int x : nums) {
            long inc = f0 + Math.max(k - x, 0);
            f0 = Math.min(inc, f1);
            f1 = Math.min(inc, f2);
            f2 = inc;
        }
        return f0;
    }
}

收集所有金币可获得的最大积分

当我们遍历到某个节点时，它的状态就是需要除以多少次 $2$，由数据范围可知每个节点最多有 $15$ 个状态。我们可以从子问题的最优解推出原问题的最优解，并且子问题可以独立求解，符合最优子结构；如果当前节点处于某个状态，它可能是由不同的路径转移得到的，即存在重叠子问题。所以我们可以使用树型 DP 求解该问题，列出如下状态转移方程：

$$ dp[x][i]=\max(\sum_{y}{dp[y][i]}+(coins[x]>>i)-k,\sum_{y}{dp[y][i + 1]}+(coins[x]>>(i+1))) $$

其中 $dp[i][j]$ 表示到达节点 $i$，需要除以 $2^{j}$，该状态下以节点 $i$ 为根的子树能够得到的最大积分。

class Solution {
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, t -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        return dfs(0, -1, g, coins, k)[0];
    }
    
    private int[] dfs(int x, int fa, List<Integer>[] g, int[] coins, int k) {
        int[] sum1 = new int[15];
        int[] sum2 = new int[15];

        for (int y : g[x]) {
            if (y == fa) continue;
            int[] t = dfs(y, x, g, coins, k);
            for (int i = 0; i < 14; i++) {
                sum1[i] += t[i];
                sum2[i] += t[i + 1];
            }
        }

        for (int i = 0; i < 14; i++) {
            sum1[i] = Math.max(sum1[i] + (coins[x] >> i) - k, sum2[i] + (coins[x] >> (i + 1)));
        }
        return sum1;
    }
}

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

第 116 场力扣夜喵双周赛

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

同下。

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

长度为偶数的字符串要满足条件，那么将数组分为长度为 $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;
    }
}