Ligh0x74's Blog

2023-09-04发表2023-09-04更新算法 / LeetCode3 分钟读完 (大约447个字)

判断通过操作能否让字符串相等 I

同下。

判断通过操作能否让字符串相等 II

模拟。也可以手动比较，就是适用性不好。（PS：想出一个写法，结果被自己 Hack 掉了~）

class Solution {
    public boolean checkStrings(String s1, String s2) {
        int n = s1.length();
        int[][] c1 = new int[2][26], c2 = new int[2][26];
        for (int i = 0; i < n; i++) {
            c1[i & 1][s1.charAt(i) - 'a']++;
            c2[i & 1][s2.charAt(i) - 'a']++;
        }
        return Arrays.deepEquals(c1, c2);
    }
}

几乎唯一子数组的最大和

滑动窗口。

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        int n = nums.size();
        long sum = 0L, ans = 0L;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.merge(nums.get(i), 1, Integer::sum);
            sum += nums.get(i);
            if (i >= k - 1) {
                if (map.size() >= m) ans = Math.max(ans, sum);
                if (map.merge(nums.get(i - k + 1), -1, Integer::sum) == 0) {
                    map.remove(nums.get(i - k + 1));
                }
                sum -= nums.get(i - k + 1);
            }
        }
        return ans;
    }
}

统计一个字符串的 k 子序列美丽值最大的数目

因为和选择的顺序没有关系，所以贪心的选择出现次数最大的字母就行。

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

    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        char[] ss = s.toCharArray();
        int[] cnt = new int[26];
        for (char c : ss) {
            cnt[c - 'a']++;
        }
        TreeMap<Integer, Integer> map = new TreeMap<>((a, b) -> b - a);
        for (int i = 0; i < 26; i++) {
            map.merge(cnt[i], 1, Integer::sum);
        }
        long ans = 1L;
        for (var e : map.entrySet()) {
            int key = e.getKey(), val = e.getValue();
            if (val >= k) {
                return (int) (ans * comb(val, k) % MOD * pow(key, k) % MOD);
            }
            k -= val;
            ans = (ans * pow(key, val)) % MOD;
        }
        return 0;
    }
    
    private long pow(long x, int n) {
        long res = 1L;
        while (n != 0) {
            if ((n & 1) == 1) res = (res * x) % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    private long comb(long n, int k) {
        long res = n;
        for (int i = 2; i <= k; i++) {
            res = res * --n / i;
        }
        return res % MOD;
    }
}

2023-09-04发表2023-09-04更新算法 / AtCoder5 分钟读完 (大约810个字)

AtCoder Beginner Contest 318

Full Moon

模拟。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    io.println(n < m ? 0 : (n - m) / p + 1);
}

Overlapping sheets

比赛时没什么思路，想到扫描线，就用扫描线 + 区间合并来做了。结果一看题解，暴力标记每个点，没想到。

public static void solve() {
    int n = io.nextInt(), ans = 0;
    int[][] g = new int[100][100];
    for (int i = 0; i < n; i++) {
        int a = io.nextInt(), b = io.nextInt();
        int c = io.nextInt(), d = io.nextInt();
        for (int x = a; x < b; x++) {
            for (int y = c; y < d; y++) {
                if (g[x][y]++ == 0) ans++;
            }
        }
    }
    io.println(ans);
}

Blue Spring

看到大佬的解法后，感觉我模拟的方式好蠢啊。当时我是枚举是否要买 \(d\) 张票，有点麻烦，原来枚举买当日的票更简单。

public static void solve() {
    int n = io.nextInt(), d = io.nextInt(), p = io.nextInt();
    int[] f = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        f[i] = io.nextInt();
    }
    Arrays.sort(f);
    long ans = Long.MAX_VALUE, sum = 0L;
    for (int i = 0; i <= n; i++) {
        sum += f[i];
        ans = Math.min(ans, sum + (long) (n - i + d - 1) / d * p);
    }
    io.println(ans);
}

General Weighted Max Matching

动态规划有点不太会，赛时瞎搞 AC 的。记忆化搜索会很好写，然后 DP 的话，我是用三层循环解决的，下面的解法优化掉一层循环。

public static void solve() {
    int n = io.nextInt();
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[i][j] = io.nextInt();
        }
    }
    long[] dp = new long[1 << n];
    for (int k = 2; k < 1 << n; k++) {
        int i = Integer.numberOfTrailingZeros(k & -k);
        dp[k] = dp[k ^ (1 << i)];
        for (int j = i + 1; j < n; j++) {
            if ((k >> j & 1) == 1) {
                dp[k] = Math.max(dp[k], dp[k ^ (1 << i) ^ (1 << j)] + d[i][j]);
            }
        }
    }
    io.println(dp[(1 << n) - 1]);
}

Sandwiches

比较显然的做法是把相同的数分为一组，然后组内枚举中间的数。对于每个中间的数，让答案加上 \(L\times R\)，其中 \(L\) 和 \(R\) 分别是左右两边相等的数的个数，枚举时可以一次性枚举间隔内所有数。

第二个解法是参考大佬的代码得到的，相当于枚举右端点吧。对于每个右端点，它的贡献可以根据下面代码中的公式得出，感觉比较巧妙。

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

Octopus

有点抽象，不是很懂。大概是枚举了 \(N^{2}\) 个极限位置，然后分别对每个位置判断可行性。

public static void solve() {
    int N = io.nextInt();
    long[] X = new long[N];
    long[] L = new long[N];
    for (int i = 0; i < N; i++) {
        X[i] = io.nextLong();
    }
    for (int i = 0; i < N; i++) {
        L[i] = io.nextLong();
    }

    List<Long> pos = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            pos.add(X[i] - L[j]);
            pos.add(X[i] + L[j] + 1);
        }
    }
    Collections.sort(pos);

    long ans = 0L;
    for (int i = 0; i < pos.size() - 1; i++) {
        long[] dis = new long[N];
        for (int j = 0; j < N; j++) {
            dis[j] = Math.abs(pos.get(i) - X[j]);
        }
        Arrays.sort(dis);
        boolean ok = true;
        for (int j = 0; j < N; j++) {
            if (dis[j] > L[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans += pos.get(i + 1) - pos.get(i);
        }
    }
    io.println(ans);
}

2023-09-04发表2023-09-04更新算法 / Codeforces4 分钟读完 (大约547个字)

Educational Codeforces Round 154 (Rated for Div. 2)

Prime Deletion

从 \(1\) 到 \(9\) 的序列中删除一些数（至少保留两位），使得结果为质数。可以发现 \(13\) 和 \(31\) 都是质数，所以判断 \(1\) 和 \(3\) 的先后顺序，然后输出即可。

public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            io.println(13);
            return;
        } else if(s[i] == '3') {
            io.println(31);
            return;
        }
    }
}

Two Binary Strings

比赛时我是从左往右遍历记录不相等的数量，如果有不相等的，那么就需要一个 \(0\)，否则遇到 \(1\) 就输出 YES。和正解的思路是一样的，就是麻烦一点。正解是有相同的 \(01\) 出现时就输出 YES。

public static void solve() {
    char[] a = io.next().toCharArray();
    char[] b = io.next().toCharArray();
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') {
            io.println("YES");
            return;
        }
    }
    io.println("NO");
}

Queries for the Array

比较简单的写法就是用一个标记数组做记录，递增会向左传递，递减会向右传递，然后判断是否冲突即可。更进一步观察，可以发现只需要记录最大的递增位置，和最小的递减位置。

public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    boolean ok = true;
    int pos = -1, neg = n, cur = -1;
    for (char c : s) {
        if (c == '+') {
            cur++;
        } else if (c == '-') {
            if (cur-- == neg) {
                neg = n;
            }
            pos = Math.min(pos, cur);
        } else if (c == '0') {
            if (cur == pos || cur <= 0) {
                ok = false;
                break;
            }
            neg = Math.min(neg, cur);
        } else {
            if (neg <= cur) {
                ok = false;
                break;
            }
            pos = cur;
        }
    }
    io.println(ok ? "YES" : "NO");
}

Sorting By Multiplication

没想到啊。枚举负数前缀的长度：在负数前缀中，如果 \(a[i]<=a[i+1]\)，就需要操作一次；在正数后缀中，如果 \(a[i]>=a[i+1]\) 就需要操作一次。（下面的代码很妙啊，不需要加额外的判断语句。）

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] >= a[i + 1]) {
            cnt++;
        }
    }
    int ans = cnt;
    for (int i = 1; i < n; i++) {
        if (a[i - 1] >= a[i]) cnt--;
        ans = Math.min(ans, cnt + 1);
        if (a[i - 1] <= a[i]) cnt++;
    }
    io.println(ans);
}