xFeedBeta
xChar
·2 months ago

我们可以证明，对于前 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 到 Pmax⁡P_{\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. 输入处理
    使用 BufferedReader 和 StringTokenizer 提高大数据量时的读入效率。

  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)，能够满足 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);
    }
}

代码说明

  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[(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

输入

basic

复制

5
1 2 3 2 4
2
4
5

输出

basic

复制

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 和 d2d_2d2​。

输出时注意需满足 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());
    }
}

代码说明

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

  2. 查询处理
    对每个查询 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 是否均在数组中出现。

  3. 输出
    如果找到满足条件的因子对，则输出它们在数组中的下标（确保 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

Loading comments...
Crossbell Logo
Crossbell Chain
Ipfs Logo
IPFS
Source