题解：P13510 [KOI 2025 #1] 远方的卡片

ryf2011 · 2025-07-29 18:05:08 · 题解

1.简化题意

给定数组 X，其中的数都恰好出现 2 次。求相等的两数所在位置之间所包含的数的个数的最大值。

2.题目思路

2-1.绝对朴素的暴力

对于每个数，遍历一遍数组，找到与之相等的另一个数，并遍历它们之间的所有数，并计数，计算最大值。

2-2.相对朴素的暴力

上述方法代码相对复杂，且有许多优化的空间。

我们知道，设一个数所在的位置为 l，另一个数所在的位置为 r（这里，我们规定 l < r），那么显然从 l 到 r（包括 l 和 r）共有 r - l + 1 个数，l 和 r 之间（不包括 l 和 r）有 r - l + 1 - 2 = r - l - 1 个数。

那么，我们可以把计数的复杂度由 \mathcal O(n) 变为 \mathcal O(1)，即找到两个相等的数之后，直接套用上述公式计算，并取最大值。

时间复杂度为 \mathcal O(n^2)，由于此题的 N \le 2000，可以通过此题。

:::info[暴力代码]

#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=2002;
int n,x[max_n<<1],ans;
bool vis[max_n<<1];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=(n<<1);i++){
        scanf("%d",&x[i]);
    }
    for(int i=1;i<=(n<<1);i++){
        if(vis[i]){ //如果这个点已经被用过，那么跳过，避免重复计算
            continue;
        }
        vis[i]=true; //标记
        for(int j=1;j<=(n<<1);j++){
            if(vis[j]){
                continue;
            }
            if(x[j]==x[i]){ //如果两数相等，说明找到了相等的数
                vis[j]=true; //标记
                ans=max(ans,j-i-1); //计算最大值
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

:::

3.别急，还没结束

我们发现，上述暴力代码仍然有优化的空间。

也许有同学看到这里便不打算继续了，认为这里没什么用处，然而，这种类型的题目的 N 可以来到 10^6 左右，此时，题目依旧是可做的！

我们发现，上述代码的瓶颈在于：每次查找相等的数都需要重新遍历一遍数组。考虑如何优化这步操作。

我们可以用一个数组来记录每个数第一次出现的位置，~~众所周知~~当这个数第二次出现时，其位置一定在第一次出现位置的后面（废话），所以我们此时可以直接从数组中提取出位置并计算，更新答案。这样做就只需要遍历一次数组了！

时间复杂度为 \mathcal O(n)。

:::warning[本题作者用到的卡常小技巧] ~~快读不再重复……~~

在本题中，数组 X 的长度为 2N，在输入时，不知道大家是否这样写？

for(int i=1;i<=n*2;i++)

注意代码中的 \texttt{n*2}，实际上，它可以转化为 \texttt{n<<1}（其中 \texttt{<<1} 表示“二进制左移 1 位”），它可以省去一些时间。

虽然在本题中，这种写法并没有显著提高代码运行时间，但在算法竞赛中，这是常见的一种优化技巧。

:::

4.代码-O(n)

注：代码仅供参考。

#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=2002;
int n,x[max_n<<1],fl[max_n],ans; //fl[i]:数字   i 第一次出现的位置
bool aper[max_n];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=(n<<1);i++){ //n<<1 相当于 n*2，但 n<<1 的速度更快，所以经常用于竞赛中以减少程序用时
        scanf("%d",&x[i]);
        if(!aper[x[i]]){ //x[i] 从未出现过，标记，并记录当前位置
            aper[x[i]]=true;
            fl[x[i]]=i;
        }
        else{ //已经出现过一次，说明这是第二次出现，计算答案并取最大值
            ans=max(ans,i-fl[x[i]]-1);
        }
    }
    printf("%d\n",ans); //输出
    return 0;
}