[Agc036D]Do Not Duplicate_链表_贪心_数论
Do Not Duplicate
题目链接:https://atcoder.jp/contests/agc036/tasks/agc036_b
题解:
首先最后肯定至多只有$n$个数。
我们想处理出来每个点下一个一样的数的下一个数。
有点绕口....
处理出来了之后,暴力找环然后暴力跳就好。
代码:
#include <bits/stdc++.h> #define N 200010 using namespace std; typedef long long ll; int a[N], pre[N], nxt[N], val[N]; char *p1, *p2, buf[100000]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ ) int rd() { int x = 0; char c = nc(); while (c < 48) { c = nc(); } while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48), c = nc(); } return x; } ll rd2() { ll x = 0; char c = nc(); while (c < 48) { c = nc(); } while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48), c = nc(); } return x; } int First[N]; int main() { int n = rd(); ll k = rd2(); for (int i = 1; i <= n; i ++ ) { a[i] = rd(); } if (n == 1) { if (k & 1) { printf("%d\n", a[1]); } return 0; } for (int i = n; i; i -- ) { First[a[i]] = i; } for (int i = 1; i <= n; i ++ ) { if (pre[a[i]]) { nxt[pre[a[i]]] = (i + 1) % n; if (!nxt[pre[a[i]]]) { nxt[pre[a[i]]] = n; } } pre[a[i]] = i; } for (int i = 1; i <= n; i ++ ) { if (!nxt[i]) { if (First[a[i]] != i) { nxt[i] = First[a[i]] + 1; } else { if (i == n) { nxt[i] = 1; } else { nxt[i] = i + 1; } } } } for (int i = 1; i <= n; i ++ ) { if (nxt[i] >= i + 2) { val[i] = nxt[i] - i; } else { val[i] = nxt[i] + n - i; } } if (nxt[n] == 1) { val[n] = n + 1; } ll mdl = 0; int now = 1; while (1) { mdl += val[now]; now = nxt[now]; if (now == 1) { break; } } ll pre = mdl / n; // cout << pre << endl ; k %= pre; if (!k) { return 0; } // puts("***"); int id = 1; now = 1; while (1) { if (nxt[now] >= now + 2) { now = nxt[now]; continue; } if (id == k) { if (nxt[now] == 1 && now != n) { return 0; } printf("%d ", a[now]); if (now == n) { return 0; } now ++ ; } else { id ++ ; now = nxt[now]; } } return 0; }
小结:想题的时候,多想一些特殊情况。比如边界值啊,极值啊这种。