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;
}

小结:想题的时候,多想一些特殊情况。比如边界值啊,极值啊这种。

最新文章

  1. 自定义 Azure Table storage 查询过滤条件
  2. 【C语言入门教程】5.4 递归
  3. log4net按等级多种方式记录日志
  4. org.apache.hadoop.conf-Configured
  5. 纯CSS制作二级导航
  6. cocos2d-x Animation
  7. 运维知识体系v0.5
  8. node.js操作mongoDB数据库
  9. cf B. Permutation
  10. JavaScripts学习日记——ECMAscript
  11. HDU 4081 Qin Shi Huang&#39;s National Road System 次小生成树变种
  12. H5本地储存Web Storage
  13. Flink 1.3.2 Standalone模式安装
  14. APP闪退问题
  15. Python——模块——配置模块(ConfigParser)
  16. [Oracle][DATAGUARD] 关于确认LOGICAL STANDBY的同期状况的方法
  17. MATLAB——sigmoid传递函数
  18. (转) HighCharts 非规律日期 多条曲线的 绘画
  19. [javase学习笔记]-6.4 成员变量与局部变量
  20. 【转载】关于Java String, StringBuilder, StringBuffer, Hashtable, HashMap的面试题

热门文章

  1. PHP mysqli_next_result() 函数
  2. PC打开AS400 folder
  3. noi 2011
  4. 灰度变换,gama变换,对数,反对数变换
  5. Tomcat怎么关闭日志输出
  6. 泛目录/泛目录程序/泛目录解析/莲花泛目录解析/寄生虫程序/黑帽SEO
  7. CISCO实验记录四:备份路由器的IOS
  8. 带你体验Android自定义圆形刻度罗盘 仪表盘 实现指针动态改变
  9. [Feature] Compare the effect of different scalers
  10. php上传文件夹