Ligh0x74's Blog

2023-11-20发表2023-11-20更新算法 / LeetCode3 分钟读完 (大约429个字)

使三个字符串相等

等价于求字符串的最长公共前缀。

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int n = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
        int i = 0;
        while (i < n && s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i)) {
            i++;
        }
        return i == 0 ? -1 : s1.length() + s2.length() + s3.length() - 3 * i;
    }
}

区分黑球与白球

将每个 \(1\) 右边 \(0\) 的个数累加就是需要交换的次数，或者累加每个 \(0\) 左边 \(1\) 的个数也行。

class Solution {
    public long minimumSteps(String s) {
        long ans = 0L;
        int n = s.length(), cnt = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') cnt++;
            else ans += cnt;
        }
        return ans;
    }
}

要求 \(\max((a\oplus x)\times(b\oplus x))\)，可以得出异或只会在两者都为 \(0\) 的位上补 \(1\)，或者交换两者某位上的 \(0\) 和 \(1\)。此时 \((a\oplus x)+(b\oplus x)=c\)，\(c\) 为某个定值，从而问题可以转化为求函数 \(y=x(c-x)\) 的最大值，可以知道当 \(x=\frac{c}{2}\) 时取到最大值，即我们需要让 \((a\oplus x)\) 和 \((b\oplus x)\) 尽可能相等。

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    
    public int maximumXorProduct(long a, long b, int n) {
        long p = a >> n << n, q = b >> n << n;
        for (int i = n - 1; i >= 0; i--) {
            if ((a >> i & 1) == (b >> i & 1)) {
                p |= 1L << i;
                q |= 1L << i;
            } else if (p < q) {
                p |= 1L << i;
            } else {
                q |= 1L << i;
            }
        }
        return (int) (p % MOD * (q % MOD) % MOD);
    }
}

找到 Alice 和 Bob 可以相遇的建筑

离线查询，可以预处理查询序列，然后使用单调栈 + 二分，或者使用最小堆；在线查询，可以使用线段树（暂时不学）。

2023-11-14发表2023-11-14更新算法 / LeetCode1 分钟读完 (大约219个字)

第 371 场力扣周赛

找出强数对的最大异或值 I

暴力。

高访问员工

模拟。

最大化数组末位元素的最少操作次数

两种情况，分类讨论。

找出强数对的最大异或值 II

要找满足 \(\mid x-y\mid\leq\min(x,y)\) 的数对，可以排序化简公式，得到 \(x\leq y\leq2x\)。然后我们可以使用双指针，枚举 \(y\) 或者 \(x\) 都行，基本上就是把满足条件的数添加到 0-1 trie 树中，把不满足条件的从树中删除，一边枚举一边计算最大异或值。还可以使用哈希表做，参考灵茶山艾府的题解。

2023-11-08发表2023-11-08更新算法 / Codeforces4 分钟读完 (大约579个字)

Codeforces Round 908 (Div. 2)

Secret Sport

因为题目保证存在合法的 \(X\) 和 \(Y\)，那么获胜者总是最后一个下棋者，因为如果不是最后一个，那么对局就不会结束。

public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    io.println(s.charAt(n - 1));
}

Two Out of Three

对于一组相同元素，它只能满足一个条件，如果满足两个条件，那么它必定会满足三个条件。所以至少要有两组出现次数大于等于 \(2\) 的元素，然后分别让其满足一个条件即可。

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 k = 2;
    int[] b = new int[n];
    Arrays.fill(b, 1);
    int[] cnt = new int[101];
    for (int i = 0; i < n && k <= 3; i++) {
        if (++cnt[a[i]] == 2) {
            b[i] = k++;
        }
    }

    if (k <= 3) {
        io.println(-1);
        return;
    }
    for (int i = 0; i < n; i++) {
        io.print(b[i] + " ");
    }
    io.println();
}

Anonymous Informant

如果当前数组是通过移动得到，那么它的最后一个元素必定是由定点元素转移过来，所以我们只需要判断最后一个元素是否在 \([1,n]\) 范围内，然后不断地回滚左移操作，即不断地找到移动之前的最后一个元素位置，并进行判断即可。

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

    int i = n - 1;
    while (b[i] != -1 && b[i] < n && --k > 0) {
        int j = (i - (b[i] + 1) + n) % n;
        b[i] = -1;
        i = j;
    }
    io.println(k == 0 || b[i] == -1 ? "Yes" : "No");
}

Neutral Tonality

我们总是可以构造一个数组 \(c\)，使得 \(\operatorname{LIS}(c)=\operatorname{LIS}(a)\)，方法为将数组 \(b\) 中的元素 \(b_{i}\)，插入到数组 \(a\) 中第一个满足 \(a_{j}\leq b_{i}\) 的元素 \(a_{j}\) 之前，操作方式类似归并排序。

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();
    }
    var b = new Integer[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b, ((e1, e2) -> e2 - e1));

    int i = 0, j = 0, k = 0;
    int[] ans = new int[n + m];
    while (i < n || j < m) {
        if (i >= n) {
            ans[k++] = b[j++];
        } else if (j >= m) {
            ans[k++] = a[i++];
        } else if (a[i] <= b[j]) {
            ans[k++] = b[j++];
        } else {
            ans[k++] = a[i++];
        }
    }

    for (int x : ans) {
        io.print(x + " ");
    }
    io.println();
}