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

第 369 场力扣周赛

找出数组中的 K-or 值

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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\)，那么就无法使两个数组的元素和相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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\)，加上这个维度就可以做记忆化搜索，然后转递推真的很妙。题解区还有其他的状态定义方式，可以看看。代码就贴灵神的。（这题感觉很不错，没有见过的类型）

1
2
3
4
5
6
7
8
9
10
11
12
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\) 为根的子树能够得到的最大积分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
    }
}
发表更新算法 / LeetCode5 分钟读完 (大约813个字)

第 116 场力扣夜喵双周赛

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

同下。

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

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

1
2
3
4
5
6
7
8
9
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\)，并在转移时判断有效性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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]\) 范围内的子数组的不同计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
}
发表更新算法 / AtCoder3 分钟读完 (大约461个字)

AtCoder Beginner Contest 326

2UP3DOWN

1
2
3
4
5
6
7
8
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

1
2
3
4
5
6
7
8
9
public static void solve() {
    int n = io.nextInt();
    for (; ; n++) {
        if (n / 100 * (n / 10 % 10) == n % 10) {
            io.println(n);
            return;
        }
    }
}

Peak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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}\)。（这么简单，真没想到）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×