banner
kanes

kanes

米哈游筆試-Java後端

我們可以證明,對於前 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 到 Pmin1P_{\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());
    }
}

代碼說明#

  1. 輸入處理
    使用 BufferedReaderStringTokenizer 提高大數據量時的讀入效率。

  2. 維護前綴最值
    循環中持續維護前 iii 個數的最小值 (prefixMin) 和最大值 (prefixMax)。

  3. 判斷與輸出

    • prefixMin > 0 時,說明前綴中沒有 0(也就沒有比 0 更小的非負數),答案輸出 0。
    • prefixMin == 0 時,根據區間覆蓋情況(由整段子區間 [0,prefixMax][0, prefixMax][0,prefixMax] 可知),答案輸出 prefixMax + 1

這種做法只對每個 iii 進行常數時間操作,總體時間複雜度為 O(n)O(n)O (n),能夠滿足 n2×105n \le 2 \times 10^5n≤2×105 的要求。


題目描述#

給定一個長度為 nnn 的二進制字符串 sss,由 0 和 1 組成。我們需要構建一個行數為 nnn,列數為 nnn 的方表,由 0 和 1 組成。第一行為原始字符串 sss,第二行為字符串 sss 向右循環移動一個位置,第三行為字符串 sss 向右循環移動兩個位置,以此類推。

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

輸入描述#

輸入一個長度為 nnn 的二進制字符串 sss,僅包含 0 和 1 字符,其中 1n50001 \leq n \leq 50001≤n≤5000。

輸出描述#

輸出表中所有由 0 組成的三角形或矩形的最大面積值。

示例 1#

輸入#

00110

輸出#

6

我們可以證明,由於構造表的方式非常特殊,每一行都是原始二進制串的右循環移位,表中任意一個形狀(嚴格說是其 “數字凸包”,也就是該形狀中所有單元格對應 jij-ij−i(取模 nnn)組成的區間)的狀態只依賴於原串中某個在環上連續的零段。經過簡單分析可以證明:

  • 若我們選取一個 “矩形”(即連續 hhh 行、連續 www 列)的子區域,其所有單元格對應的 jij-ij−i 值集合為

{D(h1),Dh+2,,D+w1}\{\, D - (h-1),\, D-h+2,\dots,\,D+w-1\,\}{D−(h−1),D−h+2,…,D+w−1}

(其中 DDD 為某個偏移量),這實際上是一個長度為 w+h1w+h-1w+h−1 的整數區間(注意區間中相鄰兩行之間會有重疊)。顯然要使區域內全為 0,必須原串中存在一個(環上連續的)零段長度至少為 w+h1w+h-1w+h−1;而在非全零(即 w+h1<nw+h-1<nw+h−1<n)的情形中,經過取最優選擇可以證明最大矩形面積為

R(L)=L+12L+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,它 “用到” 的jij-ij−i 值正好組成一個長度為 hhh 的區間,因此需要 hLh\le Lh≤L;這樣最大的三角形面積為

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

很容易驗證,當 L2L\ge2L≥2 時

T(L)=L(L+1)2>L+12L+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);
    }
}

代碼說明#

  1. 求最長連續 0 段(環狀)
    先正向掃描統計連續 0 數;此外注意如果串首和串尾都是 0,則它們在環狀上可以連在一起,故額外計算首部和尾部 0 的個數,並更新最長連續數 LLL(但 LLL 最大不超過 nnn)。

  2. 判斷答案

    • 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[(ji)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,代表一次詢問。

  • 1n,q1051 \leq n, q \leq 10^51≤n,q≤105
  • 1ai,x1061 \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 來說:

  • aba \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​ 個因子,由於 x1×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());
    }
}

代碼說明#

  1. 預處理
    對於給定的數組,我們利用兩個數組 firstIndexsecondIndex 分別記錄每個數字第一次和第二次出現的位置,方便後續判斷同一個數字能否作為一對兩相乘相等於 xxx 的候選。

  2. 查詢處理
    對每個查詢 xxx,枚舉 1dx1 \leq d \leq \sqrt{x}1≤d≤x​:

    • ddd 不是 xxx 的因數,跳過;
    • ddd 正好為平方根(即 d=x/dd = x / dd=x/d)時判斷是否出現至少兩次;
    • 否則判斷數字 ddd 與 x/dx/dx/d 是否均在數組中出現。
  3. 輸出
    如果找到滿足條件的因子對,則輸出它們在數組中的下標(確保 i<ji<ji<j);如果所有候選中均沒有滿足,則輸出 -1 -1

該算法總體時間複雜度為 O(qxO(q\sqrt{x})O (qx​),足以應對 q105q\le 10^5q≤105 的情形。

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。