题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

yyycj · 2025-03-01 22:14:44 · 题解

题目传送门

题目简述

给你一个数列 A，求这个序列中长度最小的连续的一段子序列，且这个子序列至少包含一个重复元素；如果没有这样的子序列，输出 -1。

主要思路

要求长度最小，那么只需要将重复元素放在子序列的两端，求出每个这种序列的长度，取最小值即为长度最小。

所以可以创建一个长度为 10^{6} 的一维数组 idx，表示在 A_{1} \sim A_{i} 中，对于每个 j \in [1,n]，第一次出现 A_{j} 的下标。当 idx_{A_{i}} 已经记录过了下标，就说明此时满足了重复元素为子序列两端的条件，答案与 A_{i} - idx_{A_{i}} + 1 取最小值。

一开始可以将答案设定为一个大于 10^{6} 的值，就可以保证不会与真实答案混淆。最后输出答案时，如果答案还为这个值，则输出 -1。

AC Code

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

namespace IO {
    #ifdef ONLINE_JUDGE
    #define getchar getchar_unlocked
    #endif
    #define pc putchar
    #define gc getchar
    template<typename T> void read(T &x) { int f = 1; x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }x *= f; }
    template<typename T, typename ...Args> void read(T &x, Args &...args) { read(x); read(args...); }
    template<typename T> void print(T x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
    template<typename T, typename ...Args> void print(T &x, Args &...args) { print(x); pc(' '); print(args...); }
    inline void readstr(string& x) { x.clear(); char ch = gc(); while (isspace(ch)) ch = gc(); while (!isspace(ch) && ch != EOF) { x.push_back(ch); ch = gc(); } }
    inline void printstr(char* x) { for (int i = 0; i < (int)strlen(x); i++) pc(x[i]); }
    inline void printstr(string& x) { for (auto i = x.begin(); i != x.end(); i++) pc(*i); }
};
using namespace IO;

#define OUT 0
#define MAMBA return
typedef long long ll;
typedef long double db;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int man();int main(){MAMBA man();}
inline int _abs(int a) { if (a < 0) return -a; return a; }
inline int _pow(int a, int b) { int x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------

// ----------------------------
int nums[N];
// ----------------------------

int man() {
    int n, a, ans = INF;
    read(n);
    // ----------------------------
    for (int i = 1; i <= n; i++) {
        read(a);
        if (nums[a] == 0) nums[a] = i;
        else ans = min(ans, i - nums[a] + 1);
    }
    // ----------------------------
    if (ans == INF) print(-1);
    else print(ans);
    MAMBA OUT;
}
/*
                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
             __.'              ~.   .~              `.__
           .'//   A    C    之   \./  之    真    理  \`.
         .'//                     |                     \`.
       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \`.
     .'//.-"                 `-.  |  .-'                 "-.\`.
   .'//______.============-..   \ | /   ..-============.______\`.
 .'______________________________\|/______________________________`.
*/