ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年2月27日 759点热度 0人点赞 0条评论

题目链接: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;
}
 
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ 周期性 思维 算法
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号