[Agc036D]Do Not Duplicate_链表_贪心_数论
2024-09-05 04:27:06
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("Fuck");
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;
}
小结:想题的时候,多想一些特殊情况。比如边界值啊,极值啊这种。
最新文章
- 自定义 Azure Table storage 查询过滤条件
- 【C语言入门教程】5.4 递归
- log4net按等级多种方式记录日志
- org.apache.hadoop.conf-Configured
- 纯CSS制作二级导航
- cocos2d-x Animation
- 运维知识体系v0.5
- node.js操作mongoDB数据库
- cf B. Permutation
- JavaScripts学习日记——ECMAscript
- HDU 4081 Qin Shi Huang&#39;s National Road System 次小生成树变种
- H5本地储存Web Storage
- Flink 1.3.2 Standalone模式安装
- APP闪退问题
- Python——模块——配置模块(ConfigParser)
- [Oracle][DATAGUARD] 关于确认LOGICAL STANDBY的同期状况的方法
- MATLAB——sigmoid传递函数
- (转) HighCharts 非规律日期 多条曲线的 绘画
- [javase学习笔记]-6.4 成员变量与局部变量
- 【转载】关于Java String, StringBuilder, StringBuffer, Hashtable, HashMap的面试题