米哈游笔试-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\left(n\right)$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());
    }
}

---

代码说明

1. 输入处理
   使用 BufferedReader 和 StringTokenizer 提高大数据量时的读入效率。

2. 维护前缀最值
   循环中持续维护前 $i$i 个数的最小值 (prefixMin) 和最大值 (prefixMax)。

3. 判断与输出

   • 当 prefixMin > 0 时，说明前缀中没有0（也就没有比0更小的非负数），答案输出 0。
   • 当 prefixMin == 0 时，根据区间覆盖情况（由整段子区间 $[0,prefixMax]$[0,prefixMax] 可知），答案输出 prefixMax + 1。

这种做法只对每个 $i$i 进行常数时间操作，总体时间复杂度为 $O\left(n\right)$O(n)，能够满足 $n\le 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\le n\le 5000$1≤n≤5000。

输出描述

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

示例 1

输入

00110

输出

6

---

我们可以证明，由于构造表的方式非常特殊，每一行都是原始二进制串的右循环移位，表中任意一个形状（严格说是其“数字凸包”，也就是该形状中所有单元格对应 $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）的情形中，经过取最优选择可以证明最大矩形面积为

$R\left(L\right)=\lfloor \frac{L+1}{2}\rfloor \cdot \lceil \frac{L+1}{2}\rceil ,$R(L)=⌊2L+1​⌋⋅⌈2L+1​⌉,

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

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

$T\left(L\right)=\frac{L(L+1)}{2}.$T(L)=2L(L+1)​.

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

$T\left(L\right)=\frac{L(L+1)}{2}>\lfloor \frac{L+1}{2}\rfloor \cdot \lceil \frac{L+1}{2}\rceil =R\left(L\right),$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\left(n\right)$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);
    }
}

---

代码说明

1. 求最长连续 0 段（环状）
   先正向扫描统计连续 0 数；此外注意如果串首和串尾都是 0，则它们在环状上可以连在一起，故额外计算首部和尾部 0 的个数，并更新最长连续数 $L$L（但 $L$L 最大不超过 $n$n）。

2. 判断答案

   • 若 $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\left(n\right)$O(n) 内求解表中所有由 0 组成的（三角形或矩形）区域的最大面积值。

---

小结

由于表中每个单元的值仅取决于 $s\left[\right(j-i)<mrow><mi>m</mi><mi>o</mi><mi>d</mi></mrow>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\left(n\right)$O(n)），同时也利用了构造矩阵时的“循环移位”这一特殊性质。

---

题目描述

米小游拿到了一个数组，她有若干次询问，每次询问输入一个 $x$x，她希望你判断 $x$x 是否能由数组中的两个元素相乘得出。用数学语言描述，你需要寻找到两个下标 $i$i 和 $j$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\le n,q\le {10}^5$1≤n,q≤105
• $1\le a_i,x\le {10}^6$1≤ai​,x≤106

输出描述

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

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

示例 1

输入

basic

复制

5
1 2 3 2 4
2
4
5

输出

basic

复制

2 4
-1 -1

说明

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

---

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

• 若 $a\ne 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 的顺序，输出时将两个下标排序后输出。

时间复杂度：每次询问最多枚举 $\sqrt{x}$x​ 个因子，由于 $x\le 1\times {10}^6$x≤1×106 所以每次最多约 1000 次循环，整体时间复杂度为 $O\left(q\sqrt{x}\right)$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());
    }
}

---

代码说明

1. 预处理
   对于给定的数组，我们利用两个数组 firstIndex 和 secondIndex 分别记录每个数字第一次和第二次出现的位置，方便后续判断同一个数字能否作为一对两个相乘相等于 $x$x 的候选。

2. 查询处理
   对每个查询 $x$x，枚举 $1\le d\le \sqrt{x}$1≤d≤x​：

   • 若 $d$d 不是 $x$x 的因数，跳过；
   • 当 $d$d 正好为平方根（即 $d=x/d$d=x/d）时判断是否出现至少两次；
   • 否则判断数字 $d$d 与 $x/d$x/d 是否均在数组中出现。

3. 输出
   如果找到满足条件的因子对，则输出它们在数组中的下标（确保 i<j）；如果所有候选中均没有满足，则输出 -1 -1 。

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