E – Putting Candies(思维,周期性)

发布于 2022-02-27  915 次阅读


题目链接:E - Putting Candies (atcoder.jp)

题目大意

给定一个长度为 N 的序列,X 从 0 开始,sum 一开始是0,进行 K 次操作,每次将 A[X] 加到 sum 中,并更新 X = sum % N。求最后的 sum

数据范围详见原题。

思路

K的范围较大,但是N的范围较小,所以考虑从N入手。K远大于N,所以大概率会出现重复的X,而且重复出现的X的状态和之前的一样,所以会有周期性,可以找出周期T,然后利用T和K之间的关系倍增,再加上剩下的 m 次操作

注意周期不一定从第一位开始,假设从第 P 位开始,到第P + T - 1位(共T个元素)是一个周期,从第P + T开始第二个周期,那么[1, P - 1]的元素就是“非周期内”元素,需要去除掉。

代码

/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long
//请使用%lld输出long long类型数据
using namespace std;
inline int re(){
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
/*-------全局变量------*/
const int maxn = 2e5 + 10;
int N, K, A[maxn], last[maxn], sum[maxn];
/*-----自定义函数------*/

signed main()
{
	//freopen("in.txt","r",stdin);
	N = re(), K = re();	
	for(int i = 0;i < N; ++ i)A[i] = re();
	//input finished
	int X = 0, ans = 0, m = 0;
	for(int i = 0;i < K; ++ i)
	{
		if(last[X])//这个点已经走过了 
		{
			int T = i - last[X];
			ans += (ans - sum[last[X] - 1]) * ((K - last[X]) / T - 1);//减去非周期内的一部分和,得到的就是一个周期的和,乘以周期数 
			m = (K - last[X]) % T;
			X = ans % N;
			break;
		}
		last[X] = i;
		X = (sum[i] = (ans += A[X])) % N;
	}
	//进行剩下的 m 次操作 (m < N)
	while(m --)X = (ans += A[X]) % N;
	pr("%lld\n",ans);
	return 0;
}
 
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09