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

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

全部评论

相关推荐

拒绝996的悲伤蛙:此贴终结|给路过的牛友分享一下心得👇 实习的时候不要光埋头干活,身边的大佬同事才是真·宝藏人脉!大胆请教他们工作以及职场上的问题以我的经历,我的带教有十几年工作经验,做过运维、后端开发、web测试,现在是高级软测,是行走的避坑指南 我之前纠结要不要学Web测试简历,被他一句话点醒:Web发展成熟,岗位需求在缩,AI对互联网的冲击可能以后架构+开发+测试一人包揽。现在用户更多用的是移动端APP/小程序,相比之下天天守着电脑刷网页的人基数小。 这里我的纠结得到反馈,于是我又把简历发给带教,获得了一对一的简历指导。 感兴趣的可以看看: 1.教育背景:本科→本科(全日制) 2.实习经历:总体问题不大,但第2点要稍作修改,可以写但做功课,如风机、水箱……可能会问用哪个供应商的?使用寿命、型号、电压电流、多少秒会触发逻辑? 3.项目经历(坑太多,大型翻车现场): - 项目名越直白越好,让人一眼就知道你干了啥。 -用的什么语言设计核心接口,异步执行做功课,涉及线程问题,被问可回答n个功能是如何错开异步执行的 - “验证任务消费……阻塞丢包”“高负载稳定性”这种词,没三五年开发功底不要写,不然面试时被问线程、数量级、CPU占用,内存带宽等影响性能的直接原地社死。 -做功课 -做功课,测了哪些模块,如何设计,接口流量抓包,token,变量…… -做功课,要熟悉网络协议…… 带教之前做互联网开发的时候面试过很多人,总的来说不要为了显得项目高大上过渡包装,写了就要做好拷打的准备
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
02-05 17:50
已编辑
武汉工程科技学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务