我们可以证明,对于前 iii 个数构成的所有区间,其“数字凸包区间”的并恰好是一个连续区间 [Pmin,Pmax][P_{\min},P_{\max}][Pmin,Pmax](其中
Pmin=min{a1,…,ai},Pmax=max{a1,…,ai}P_{\min}=\min\{a_1,\ldots,a_i\},\quad P_{\max}=\max\{a_1,\ldots,a_i\}Pmin=min{a1,…,ai},Pmax=max{a1,…,ai}
)。这是因为整个区间 [1,i][1,i][1,i] 作为一个子区间,其数字凸包就是 [Pmin,Pmax][P_{\min},P_{\max}][Pmin,Pmax];而其他子区间给出的区间都是这个区间的子区间,不可能扩充出整段连续区间之外的数值。
因此,对每个 iii 我们只需维护前缀中的最小值和最大值,从而:
下面给出Java实现,时间复杂度 O(n)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
提高大数据量时的读入效率。
维护前缀最值
循环中持续维护前 iii 个数的最小值 (prefixMin
) 和最大值 (prefixMax
)。
判断与输出
prefixMin > 0
时,说明前缀中没有0(也就没有比0更小的非负数),答案输出 0。prefixMin == 0
时,根据区间覆盖情况(由整段子区间 [0,prefixMax][0, prefixMax][0,prefixMax] 可知),答案输出 prefixMax + 1
。这种做法只对每个 iii 进行常数时间操作,总体时间复杂度为 O(n)O(n)O(n),能够满足 n≤2×105n \le 2 \times 10^5n≤2×105 的要求。
给定一个长度为 nnn 的二进制字符串 sss,由 0 和 1 组成。我们需要构建一个行数为 nnn,列数为 nnn 的方表,由 0 和 1 组成。第一行为原始字符串 sss,第二行为字符串 sss 向右循环移动一个位置,第三行为字符串 sss 向右循环移动两个位置,以此类推。
求表中所有由 0 组成的三角形或矩形的最大面积值。
输入一个长度为 nnn 的二进制字符串 sss,仅包含 0 和 1 字符,其中 1≤n≤50001 \leq n \leq 50001≤n≤5000。
输出表中所有由 0 组成的三角形或矩形的最大面积值。
00110
6
我们可以证明,由于构造表的方式非常特殊,每一行都是原始二进制串的右循环移位,表中任意一个形状(严格说是其“数字凸包”,也就是该形状中所有单元格对应 j−ij-ij−i(取模 nnn)组成的区间)的状态只依赖于原串中某个在环上连续的零段。经过简单分析可以证明:
{D−(h−1),D−h+2,…,D+w−1}\{\, D - (h-1),\, D-h+2,\dots,\,D+w-1\,\}{D−(h−1),D−h+2,…,D+w−1}
(其中 DDD 为某个偏移量),这实际上是一个长度为 w+h−1w+h-1w+h−1 的整数区间(注意区间中相邻两行之间会有重叠)。显然要使区域内全为 0,必须原串中存在一个(环上连续的)零段长度至少为 w+h−1w+h-1w+h−1;而在非全零(即 w+h−1<nw+h-1<nw+h−1<n)的情形中,经过取最优选择可以证明最大矩形面积为
R(L)=⌊L+12⌋⋅⌈L+12⌉,R(L)=\lfloor\frac{L+1}{2}\rfloor\cdot\lceil\frac{L+1}{2}\rceil,R(L)=⌊2L+1⌋⋅⌈2L+1⌉,
其中 LLL 表示原串(视为环状)中零的最长连续段长度。
T(L)=L(L+1)2.T(L)=\frac{L(L+1)}2.T(L)=2L(L+1).
很容易验证,当 L≥2L\ge2L≥2 时
T(L)=L(L+1)2>⌊L+12⌋⋅⌈L+12⌉=R(L),T(L)=\frac{L(L+1)}2> \lfloor\frac{L+1}{2}\rfloor\cdot\lceil\frac{L+1}{2}\rceil=R(L),T(L)=2L(L+1)>⌊2L+1⌋⋅⌈2L+1⌉=R(L),
即非全零情况下最佳面积取决于“零三角形”形状。注意:若原串全为 0,则表中所有单元均为 0,这时当然最大面积为整个表面积 n×nn\times nn×n(因为 n2>n(n+1)2n^2>\frac{n(n+1)}2n2>2n(n+1) )。
综上,我们可以先扫描原串(按环状计)求出最长连续 0 的长度 LLL(如果不存在 0,则答案为 0);接下来判断:
下面给出 Java 代码实现,时间复杂度 O(n)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 的个数,并更新最长连续数 LLL(但 LLL 最大不超过 nnn)。
判断答案
这样我们就实现了在 O(n)O(n)O(n) 内求解表中所有由 0 组成的(三角形或矩形)区域的最大面积值。
由于表中每个单元的值仅取决于 s[(j−i)modn]s[(j-i) \bmod n]s[(j−i)modn],整个问题转化为求原串(环状)中最长的零段长度 LLL;并证明在非全零情况下,“零直角三角形”的面积为
L(L+1)2,\frac{L(L+1)}2,2L(L+1),
始终大于同样受限制的矩形面积。因此最终答案为
这种思路不仅降低了时间复杂度(仅 O(n)O(n)O(n)),同时也利用了构造矩阵时的“循环移位”这一特殊性质。
米小游拿到了一个数组,她有若干次询问,每次询问输入一个 xxx,她希望你判断 xxx 是否能由数组中的两个元素相乘得出。用数学语言描述,你需要寻找到两个下标 iii 和 jjj(i<ji < ji<j),满足 ai×aj=xa_i \times a_j = xai×aj=x。
第一行输入一个正整数 nnn,代表数组的大小。
第二行输入 nnn 个正整数 aia_iai,代表数组的元素。
第三行输入一个正整数 qqq,代表询问次数。
接下来的 qqq 行,每行输入一个正整数 xxx,代表一次询问。
对于每次询问,如果无法找到两数乘积等于 xxx,输出 -1 -1
。
否则输出 iii 和 jjj(i<ji < ji<j),用空格隔开,代表 ai×aj=xa_i \times a_j = xai×aj=x。有多解时输出任意即可。
basic
复制
5
1 2 3 2 4
2
4
5
basic
复制
2 4
-1 -1
1 5
也是可以的。下面给出 Java 实现。思路是:预处理数组中每个数字在数组中第一次出现和第二次出现的位置,下标记为 1-indexed。这样,对于两个数字 aaa 和 bbb 来说:
对于每次询问 xxx ,我们枚举 ddd 从 1 到 x\sqrt{x}x(即所有可能的因子),若 ddd 能整除 xxx 则候选另一因子为 d2=x/dd_2=x/dd2=x/d。对候选对:
输出时注意需满足 i<ji<ji<j 的顺序,输出时将两个下标排序后输出。
时间复杂度:每次询问最多枚举 x\sqrt{x}x 个因子,由于 x≤1×106x\le1\times10^6x≤1×106 所以每次最多约 1000 次循环,整体时间复杂度为 O(qx)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
分别记录每个数字第一次和第二次出现的位置,方便后续判断同一个数字能否作为一对两个相乘相等于 xxx 的候选。
查询处理
对每个查询 xxx,枚举 1≤d≤x1 \leq d \leq \sqrt{x}1≤d≤x:
输出
如果找到满足条件的因子对,则输出它们在数组中的下标(确保 i<ji<ji<j);如果所有候选中均没有满足,则输出 -1 -1
。
该算法总体时间复杂度为 O(qx)O(q\sqrt{x})O(qx),足以应对 q≤105q\le 10^5q≤105 的情形。
此文由 Mix Space 同步更新至 xLog
原始链接为 https://blog.kanes.top/posts/WrittenExamination/547345546732