米哈游笔试-Java后端 - 一些学习与部分故事

我们可以证明，对于前 $i$ i 个数构成的所有区间，其“数字凸包区间”的并恰好是一个连续区间 $[P_{\min}, P_{\max}]$ [Pmin,Pmax]（其中

P_{\min} = \min {a_{1}, \dots, a_{i}}, P_{\max} = \max {a_{1}, \dots, a_{i}}

Pmin\=min{a1,…,ai},Pmax\=max{a1,…,ai}

）。这是因为整个区间 $[1, i]$ [1,i] 作为一个子区间，其数字凸包就是 $[P_{\min}, P_{\max}]$ [Pmin,Pmax]；而其他子区间给出的区间都是这个区间的子区间，不可能扩充出整段连续区间之外的数值。

因此，对每个 $i$ i 我们只需维护前缀中的最小值和最大值，从而：

若 $P_{\min} 0$ Pmin>0（也就是说前缀中没有出现0），那么整个集合不包含从 $0$ 0 到 $P_{\min} - 1$ Pmin−1 的数，此时最小的非负整数就是 $0$ 0。
否则（也即 $P_{\min} = 0$ Pmin\=0），那么由全区间 $[0, P_{\max}]$ \[0,Pmax\] 可知所有从 $0$ 0 到 $P_{\max}$ Pmax 都被覆盖，答案就是 $P_{\max} + 1$ Pmax+1。

下面给出Java实现，时间复杂度 $O (n)$ O(n)：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        // 第一行可以只包含一个整数n
        int n = Integer.parseInt(line.trim());
        
        // 读取数组
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        // 前缀最小值和前缀最大值
        int prefixMin = Integer.MAX_VALUE;
        int prefixMax = Integer.MIN_VALUE;
        
        // 构造答案
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            prefixMin = Math.min(prefixMin, a[i]);
            prefixMax = Math.max(prefixMax, a[i]);
            
            // 若前缀没有0，则说明[1,i]的所有区间其并不含0，答案为0；
            // 否则答案就是前缀最大值加1
            if (prefixMin > 0) {
                sb.append("0");
            } else {
                sb.append(prefixMax + 1);
            }
            if (i < n - 1) {
                sb.append(" ");
            }
        }
        
        System.out.println(sb.toString());
    }
}

代码说明

输入处理
使用 BufferedReader 和 StringTokenizer 提高大数据量时的读入效率。
维护前缀最值
循环中持续维护前 $i$ i 个数的最小值 (prefixMin) 和最大值 (prefixMax)。
判断与输出
- 当 prefixMin > 0 时，说明前缀中没有0（也就没有比0更小的非负数），答案输出 0。
- 当 prefixMin == 0 时，根据区间覆盖情况（由整段子区间 $[0, p r e f i x M a x]$ \[0,prefixMax\] 可知），答案输出 `prefixMax + 1`。

这种做法只对每个 $i$ i 进行常数时间操作，总体时间复杂度为 $O (n)$ O(n)，能够满足 $n \leq 2 \times 10^{5}$ n≤2×105 的要求。

题目描述

给定一个长度为 $n$ n 的二进制字符串 $s$ s，由 0 和 1 组成。我们需要构建一个行数为 $n$ n，列数为 $n$ n 的方表，由 0 和 1 组成。第一行为原始字符串 $s$ s，第二行为字符串 $s$ s 向右循环移动一个位置，第三行为字符串 $s$ s 向右循环移动两个位置，以此类推。

求表中所有由 0 组成的三角形或矩形的最大面积值。

输入描述

输入一个长度为 $n$ n 的二进制字符串 $s$ s，仅包含 0 和 1 字符，其中 $1 \leq n \leq 5000$ 1≤n≤5000。

输出描述

输出表中所有由 0 组成的三角形或矩形的最大面积值。

示例 1

输入

输出

我们可以证明，由于构造表的方式非常特殊，每一行都是原始二进制串的右循环移位，表中任意一个形状（严格说是其“数字凸包”，也就是该形状中所有单元格对应 $j - i$ j−i（取模 $n$ n）组成的区间）的状态只依赖于原串中某个在环上连续的零段。经过简单分析可以证明：

若我们选取一个“矩形”（即连续 $h$ h 行、连续 $w$ w 列）的子区域，其所有单元格对应的 $j - i$ j−i值集合为

{D - (h - 1), D - h + 2, \dots, D + w - 1}

{D−(h−1),D−h+2,…,D+w−1}

（其中 $D$ D 为某个偏移量），这实际上是一个长度为 $w + h - 1$ w+h−1 的整数区间（注意区间中相邻两行之间会有重叠）。显然要使区域内全为 0，必须原串中存在一个（环上连续的）零段长度至少为 $w + h - 1$ w+h−1；而在非全零（即 $w + h - 1 < n$ w+h−1<n）的情形中，经过取最优选择可以证明最大矩形面积为

R (L) = ⌊ \frac{L + 1}{2} ⌋ \cdot ⌈ \frac{L + 1}{2} ⌉,

R(L)\=⌊2L+1⌋⋅⌈2L+1⌉,

其中 $L$ L 表示原串（视为环状）中零的最长连续段长度。

同理，设我们只允许“直角三角形”形状（例如以左上角为直角，每往下一行比上一行多 1 个单元，面积为 $1 + 2 + \dots + h = \frac{h (h + 1)}{2}$ 1+2+⋯+h\=2h(h+1)），那么设三角形高为 $h$ h，它“用到”的 $j - i$ j−i值正好组成一个长度为 $h$ h 的区间，因此需要 $h \leq L$ h≤L；这样最大的三角形面积为

T (L) = \frac{L (L + 1)}{2} .

T(L)\=2L(L+1).

很容易验证，当 $L \geq 2$ L≥2 时

T (L) = \frac{L (L + 1)}{2} ⌊ \frac{L + 1}{2} ⌋ \cdot ⌈ \frac{L + 1}{2} ⌉ = R (L),

T(L)\=2L(L+1)

⌊2L+1⌋⋅⌈2L+1⌉=R(L),

即非全零情况下最佳面积取决于“零三角形”形状。注意：若原串全为 0，则表中所有单元均为 0，这时当然最大面积为整个表面积 $n \times n$ n×n（因为 $n^{2} \frac{n (n + 1)}{2}$ n2>2n(n+1) ）。

综上，我们可以先扫描原串（按环状计）求出最长连续 0 的长度 $L$ L（如果不存在 0，则答案为 0）；接下来判断：

若 $L = n$ L\=n（全零串），答案为 $n^{2}$ n2；
否则答案为 $\frac{L (L + 1)}{2}$ 2L(L+1)（即构成某个“零三角形”的面积最大值）。

下面给出 Java 代码实现，时间复杂度 $O (n)$ O(n)：

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        // 读取输入的二进制字符串（原串s）
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int n = s.length();
        
        // 计算原串中（按环状）最长连续0的长度 L
        int L = 0;
        int curr = 0;
        // 扫描一遍（不考虑环首与环尾相连的情况）
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                curr++;
                if (curr > L) {
                    L = curr;
                }
            } else {
                curr = 0;
            }
        }
        // 若首尾均为 '0'，则尝试用环状连接更新 L
        if (n > 0 && s.charAt(0) == '0' && s.charAt(n - 1) == '0') {
            int prefix = 0, suffix = 0;
            for (int i = 0; i < n && s.charAt(i) == '0'; i++) {
                prefix++;
            }
            for (int i = n - 1; i >= 0 && s.charAt(i) == '0'; i--) {
                suffix++;
            }
            if (prefix + suffix > L) {
                L = prefix + suffix;
            }
            // 注意 L 最多为 n（原串长度）
            if (L > n) {
                L = n;
            }
        }
        
        long ans = 0;
        // 如果原串中没有0，答案为0
        if (L == 0) {
            ans = 0;
        }
        // 原串全为0，则表中的每个元素均为0，答案为 n*n
        else if (L == n) {
            ans = (long) n * n;
        }
        // 否则最佳面积来源于“零三角形”，面积为 L*(L+1)/2
        else {
            ans = (long) L * (L + 1) / 2;
        }
        
        System.out.println(ans);
    }
}

代码说明

求最长连续 0 段（环状）
先正向扫描统计连续 0 数；此外注意如果串首和串尾都是 0，则它们在环状上可以连在一起，故额外计算首部和尾部 0 的个数，并更新最长连续数 $L$ L（但 $L$ L 最大不超过 $n$ n）。
判断答案
- 若 $L = 0$ L\=0（没有 0），答案为 0。
- 若 $L = n$ L\=n（全 0 串），整表全为 0，答案为 $n \times n$ n×n；
- 否则答案为 $\frac{L (L + 1)}{2}$ 2L(L+1)（这正是构成某个“零三角形”时所能达到的最大面积）。

这样我们就实现了在 $O (n)$ O(n) 内求解表中所有由 0 组成的（三角形或矩形）区域的最大面积值。

小结

由于表中每个单元的值仅取决于 $s [(j - i) m o d n]$ s[(j−i)modn]，整个问题转化为求原串（环状）中最长的零段长度 $L$ L；并证明在非全零情况下，“零直角三角形”的面积为

\frac{L (L + 1)}{2},

2L(L+1),

始终大于同样受限制的矩形面积。因此最终答案为

如果 $s$ s 全 0：答案为 $n^{2}$ n2；
否则：答案为 $\frac{L (L + 1)}{2}$ 2L(L+1)。

这种思路不仅降低了时间复杂度（仅 $O (n)$ O(n)），同时也利用了构造矩阵时的“循环移位”这一特殊性质。

题目描述

米小游拿到了一个数组，她有若干次询问，每次询问输入一个 $x$ x，她希望你判断 $x$ x 是否能由数组中的两个元素相乘得出。用数学语言描述，你需要寻找到两个下标 $i$ i 和 $j$ j（ $i < j$ i<j），满足 $a_{i} \times a_{j} = x$ ai×aj=x。

输入描述

第一行输入一个正整数 $n$ n，代表数组的大小。

第二行输入 $n$ n 个正整数 $a_{i}$ ai，代表数组的元素。

第三行输入一个正整数 $q$ q，代表询问次数。

接下来的 $q$ q 行，每行输入一个正整数 $x$ x，代表一次询问。

$1 \leq n, q \leq 10^{5}$ 1≤n,q≤105
$1 \leq a_{i}, x \leq 10^{6}$ 1≤ai,x≤106

输出描述

对于每次询问，如果无法找到两数乘积等于 $x$ x，输出 -1 -1。

否则输出 $i$ i 和 $j$ j（ $i < j$ i<j），用空格隔开，代表 $a_{i} \times a_{j} = x$ ai×aj=x。有多解时输出任意即可。

示例 1

输入

basic

输出

basic

2 4
-1 -1

说明

第一组询问，输出 1 5 也是可以的。
第二组询问，显然无法找到两个元素相乘等于 5。

下面给出 Java 实现。思路是：预处理数组中每个数字在数组中第一次出现和第二次出现的位置，下标记为 1-indexed。这样，对于两个数字 $a$ a 和 $b$ b 来说：

若 $a \neq b$ a\\\=b 只需检查数组中是否均出现过；
若 $a = b$ a\=b 则需要出现两次以上。

对于每次询问 $x$ x ，我们枚举 $d$ d 从 1 到 $\sqrt{x}$ x（即所有可能的因子），若 $d$ d 能整除 $x$ x 则候选另一因子为 $d_{2} = x / d$ d2=x/d。对候选对：

若 $d = = d_{2}$ d\==d2，必须保证数组中该数字出现次数至少为 2。
否则只要数组中同时出现了 $d$ d 和 $d_{2}$ d2。

输出时注意需满足 $i < j$ i<j 的顺序，输出时将两个下标排序后输出。

时间复杂度：每次询问最多枚举 $\sqrt{x}$ x 个因子，由于 $x \leq 1 \times 10^{6}$ x≤1×106 所以每次最多约 1000 次循环，整体时间复杂度为 $O (q \sqrt{x})$ O(qx) 。

下面给出完整代码：

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 读取数组大小 n
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        // 因为数字范围 (1 <= a_i <= 1e6)，预分配大小为 1e6+1 的数组
        int MAX = 1000000;
        // firstIndex[v] 表示数字 v 在数组中第一次出现的位置（1-indexed），若未出现值为 0
        int[] firstIndex = new int[MAX + 1];
        // secondIndex[v] 表示数字 v 在数组中第二次出现的位置（1-indexed），若不足两次出现值为 0
        int[] secondIndex = new int[MAX + 1];

        // 读取数组元素
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (firstIndex[num] == 0) {
                firstIndex[num] = i;
            } else if (secondIndex[num] == 0) {
                secondIndex[num] = i;
            }
        }
        
        // 读取查询次数 q
        int q = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        
        // 对每个查询进行处理
        for (int qi = 0; qi < q; qi++) {
            // 每个查询给定 x
            int x = Integer.parseInt(br.readLine().trim());
            boolean found = false;
            
            // 枚举可能的因子 d，从 1 到 sqrt(x)
            int sqrtX = (int) Math.sqrt(x);
            for (int d = 1; d <= sqrtX; d++) {
                if (x % d != 0) {
                    continue;  // d 不是 x 的因子
                }
                
                int d2 = x / d;
                // 若 d 或 d2 超出数组中可能的数字范围，则直接跳过
                if (d > MAX || d2 > MAX) {
                    continue;
                }
                
                if (d == d2) {
                    // 两个因子相同，必须存在两次及以上出现
                    if (firstIndex[d] != 0 && secondIndex[d] != 0) {
                        sb.append(firstIndex[d]).append(" ").append(secondIndex[d]).append("\n");
                        found = true;
                        break;
                    }
                } else {
                    // 两个因子不同，只需两者均出现即可
                    if (firstIndex[d] != 0 && firstIndex[d2] != 0) {
                        int i1 = firstIndex[d];
                        int i2 = firstIndex[d2];
                        // 输出两个下标，保证 i1 < i2
                        if (i1 > i2) {
                            int temp = i1;
                            i1 = i2;
                            i2 = temp;
                        }
                        sb.append(i1).append(" ").append(i2).append("\n");
                        found = true;
                        break;
                    }
                }
            }
            
            if (!found) {
                sb.append("-1 -1\n");
            }
        }
        
        System.out.print(sb.toString());
    }
}

代码说明

预处理
对于给定的数组，我们利用两个数组 firstIndex 和 secondIndex 分别记录每个数字第一次和第二次出现的位置，方便后续判断同一个数字能否作为一对两个相乘相等于 $x$ x 的候选。
查询处理
对每个查询 $x$ x，枚举 $1 \leq d \leq \sqrt{x}$ 1≤d≤x：
- 若 $d$ d 不是 $x$ x 的因数，跳过；
- 当 $d$ d 正好为平方根（即 $d = x / d$ d\=x/d）时判断是否出现至少两次；
- 否则判断数字 $d$ d 与 $x / d$ x/d 是否均在数组中出现。
输出
如果找到满足条件的因子对，则输出它们在数组中的下标（确保 $i < j$ i<j）；如果所有候选中均没有满足，则输出 -1 -1 。

该算法总体时间复杂度为 $O (q \sqrt{x})$ O(qx)，足以应对 $q \leq 10^{5}$ q≤105 的情形。