【题解】[ABC378C] Repeating

WA2025 · 2024-11-04 18:08:34 · 题解

题目传送门

Luogu | AtCoder

题意

给定长度为 n 的数组 A，求出对于每个 i(1\le i\le n)，最后一个满足条件 A_i=A_j 的 j(1\le j\le n)。

思路

用数组统计每一个数最后出现的位置，但是注意到题意 1\le A_i\le 10^9，也就是说，不能开大小为 10^9 的数组，所以我们可以用 map 代替。

代码

#include <bits/stdc++.h>
using namespace std;

#define Fast         ios::sync_with_stdio(false)
#define Made         return
#define By           0
#define TheSoundOfWA ;

unordered_map<int, int> mp;

int main() {
    Fast;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        if (mp[x] == 0) cout << -1 << ' ';
        else cout << mp[x] << ' ';
        mp[x] = i;
    }

    Made By TheSoundOfWA
}