我們可以證明,對於前 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 我們只需維護前綴中的最小值和最大值,從而:
- 若 Pmin>0P_{\min}>0Pmin>0(也就是說前綴中沒有出現 0),那麼整個集合不包含從 000 到 Pmin−1P_{\min}-1Pmin−1 的數,此時最小的非負整數就是 000。
- 否則(也即 Pmin=0P_{\min}=0Pmin=0),那麼由全區間 [0,Pmax][0,P_{\max}][0,Pmax] 可知所有從 000 到 PmaxP_{\max}Pmax 都被覆蓋,答案就是 Pmax+1P_{\max}+1Pmax+1。
下面給出 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 組成的三角形或矩形的最大面積值。
示例 1#
輸入#
00110
輸出#
6
我們可以證明,由於構造表的方式非常特殊,每一行都是原始二進制串的右循環移位,表中任意一個形狀(嚴格說是其 “數字凸包”,也就是該形狀中所有單元格對應 j−ij-ij−i(取模 nnn)組成的區間)的狀態只依賴於原串中某個在環上連續的零段。經過簡單分析可以證明:
- 若我們選取一個 “矩形”(即連續 hhh 行、連續 www 列)的子區域,其所有單元格對應的 j−ij-ij−i 值集合為
{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 表示原串(視為環状)中零的最長連續段長度。
- 同理,設我們只允許 “直角三角形” 形狀(例如以左上角為直角,每往下一行比上一行多 1 個單元,面積為 1+2+⋯+h=h(h+1)21+2+\cdots+h=\frac{h(h+1)}21+2+⋯+h=2h (h+1)),那麼設三角形高為 hhh,它 “用到” 的j−ij-ij−i 值正好組成一個長度為 hhh 的區間,因此需要 h≤Lh\le Lh≤L;這樣最大的三角形面積為
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);接下來判斷:
- 若 L=nL=nL=n(全零串),答案為 n2n^2n2;
- 否則答案為 L(L+1)2\dfrac{L(L+1)}22L (L+1)(即構成某個 “零三角形” 的面積最大值)。
下面給出 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)。 -
判斷答案
- 若 L=0L=0L=0(沒有 0),答案為 0。
- 若 L=nL=nL=n(全 0 串),整表全為 0,答案為 n×nn \times nn×n;
- 否則答案為 L(L+1)2\frac{L(L+1)}{2}2L (L+1)(這正是構成某個 “零三角形” 時所能達到的最大面積)。
這樣我們就實現了在 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),
始終大於同樣受限制的矩形面積。因此最終答案為
- 如果 sss 全 0:答案為 n2n^2n2;
- 否則:答案為 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,代表一次詢問。
- 1≤n,q≤1051 \leq n, q \leq 10^51≤n,q≤105
- 1≤ai,x≤1061 \leq a_i, x \leq 10^61≤ai,x≤106
輸出描述#
對於每次詢問,如果無法找到兩數乘積等於 xxx,輸出 -1 -1
。
否則輸出 iii 和 jjj(i<ji < ji<j),用空格隔開,代表 ai×aj=xa_i \times a_j = xai×aj=x。有多解時輸出任意即可。
示例 1#
輸入#
5
1 2 3 2 4
2
4
5
輸出#
2 4
-1 -1
說明#
- 第一組詢問,輸出
1 5
也是可以的。 - 第二組詢問,顯然無法找到兩個元素相乘等於 5。
下面給出 Java 實現。思路是:預處理數組中每個數字在數組中第一次出現和第二次出現的位置,下標記為 1-indexed。這樣,對於兩個數字 aaa 和 bbb 來說:
- 若 a≠ba \neq ba=b 只需檢查數組中是否均出現過;
- 若 a=ba=ba=b,則需要出現兩次以上。
對於每次詢問 xxx,我們枚舉 ddd 從 1 到 x\sqrt{x}x(即所有可能的因子),若 ddd 能整除 xxx,則候選另一因子為 d2=x/dd_2=x/dd2=x/d。對候選對:
- 若 d==d2d==d_2d==d2,必須保證數組中該數字出現次數至少為 2。
- 否則只要數組中同時出現了 ddd 和 x/dx/dx/d 是否均在數組中出現。
輸出時注意需滿足 i<ji<ji<j 的順序,輸出時將兩個下標排序後輸出。
時間複雜度:每次詢問最多枚舉 x\sqrt{x}x 個因子,由於 x≤1×106x\le1\times10^6x≤1×106 所以每次最多約 1000 次循環,整體時間複雜度為 O(qxO(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:- 若 ddd 不是 xxx 的因數,跳過;
- 當 ddd 正好為平方根(即 d=x/dd = x / dd=x/d)時判斷是否出現至少兩次;
- 否則判斷數字 ddd 與 x/dx/dx/d 是否均在數組中出現。
-
輸出
如果找到滿足條件的因子對,則輸出它們在數組中的下標(確保 i<ji<ji<j);如果所有候選中均沒有滿足,則輸出-1 -1
。
該算法總體時間複雜度為 O(qxO(q\sqrt{x})O (qx),足以應對 q≤105q\le 10^5q≤105 的情形。