【蓝桥杯】 历届试题 数字游戏(数列)

2024-03-30 13:08

本文主要是介绍【蓝桥杯】 历届试题 数字游戏(数列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

历届试题 数字游戏

问题描述
栋栋正在和同学们玩一个数字游戏。
游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来,坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来,也就是说4。下一个同学要往下数三个数,说7。依次类推。
为了使数字不至于太大,栋栋和同学们约定,当在心中数到 k-1 时,下一个数字从0开始数。例如,当k=13时,栋栋和同学们报出的前几个数依次为:
1, 2, 4, 7, 11, 3, 9, 3, 11, 7。
游戏进行了一会儿,栋栋想知道,到目前为止,他所有说出的数字的总和是多少。

输入格式
  输入的第一行包含三个整数 n,k,T,其中 n 和 k 的意义如上面所述,T 表示到目前为止栋栋一共说出的数字个数。
输出格式
 输出一行,包含一个整数,表示栋栋说出所有数的和。

样例输入:3 13 3 样例输出:17

样例说明:栋栋说出的数依次为1, 7, 9,和为17。
数据规模和约定:1 < n,k,T < 1,000,000;



---分割线---


分析:
我们看一下报数时会出现的数字(不做取余处理,上面是报数,下面是差值):

1  	2  	4  	7  	11	 16	  22    29	  37	46	……			1	  2	  3	  4	   5    6	  7	    8	 9	 ……

我们单独看一下栋栋的报数: 1 7 22 46……
不难发现这些数据服从以下规律:

 1 1 + ( 1 + 2 + 3 ) = 71 + ( 1 + 2 + 3 ) + ( 4 +5 + 6 )  =  22

由此可以得到栋栋报数的一个通项公式:num = 1 + n (n+1) / 2 (其中n表示栋栋报数时对应的序号-1,显然n取值是:0,3,6,9,……)

知道了通项公式,以及总的循环次数,直接循环求和就是
但是,这样的下场是:拿不到满分
为什么?
仔细看题,T和k的取值最大会接近100 0000,这时候如果仅仅只是利用上面的这个公式来求每次的报数num并求和然后再取余,则num总会在某个值时发生溢出现象(num的数量级极限会取到100 0000^4,显然溢出了long long),这时后面所有的num都将错误。所以这个方案是不可行的

为了避免这个溢出问题,我们应该想到利用前一次num的数值与下一次num的数值之间的差值来完成对num的变化,即利用这个差值来实现数据的更新(因为这之间的差值不会超过long long)
于是我们需要来推算一下(或者说来求出)这个差值量与序数n的关系,即求出这个函数。我们假设,有N个同学参与数字游戏,那么对于一个周期(N)而言
栋栋两次报数的差值是一个关于n的函数:
△x=1+(n+N) [(n+N)+1] / 2 - [ 1+n(n+1) / 2 ] = N(N+2*n+1)/2
这样就可以利用上面的公式,通过上一次num的值,用加法来把下一次的num计算出来,然后取余,叠加到sum中(这样显然是不会产生数据溢出的现象的)

下面给出本题的完整代码:


---分割线---

#include<iostream>
using namespace std;
int main()
{int n,k,T;cin>>n>>k>>T;long long sum=0,i=0,x=1;//sum是最后的总和,i是东东报数时的序号(从0开始),x是第i-1次东东报数后取余再加上第i-1到第i次之间的差值的值 (即第i次的值)while(T--){ sum+=x;x+=(n+2*i+1)*n/2;  x%=k;i+=n;}cout<<sum<<endl; return 0;
}

这篇关于【蓝桥杯】 历届试题 数字游戏(数列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/861569

相关文章

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

国产游戏崛起:技术革新与文化自信的双重推动

近年来,国产游戏行业发展迅猛,技术水平和作品质量均得到了显著提升。特别是以《黑神话:悟空》为代表的一系列优秀作品,成功打破了过去中国游戏市场以手游和网游为主的局限,向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展,国产游戏正逐步赢得国际市场的认可。然而,面对全球游戏行业的激烈竞争,国产游戏技术依然面临诸多挑战,未来的

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

火柴游戏java版

代码 /*** 火柴游戏* <p>* <li>有24根火柴</li>* <li>组成 A + B = C 等式</li>* <li>总共有多少种适合方式?</li>* <br>* <h>分析:</h>* <li>除去"+"、"="四根,最多可用火柴根数20根。</li>* <li>全部用两根组合成"1",最大数值为1111。使用枚举法,A和B范围在0~1111,C为A+B。判断</li>** @

国产游戏行业的崛起与挑战:技术创新引领未来

国产游戏行业的崛起与挑战:技术创新引领未来 近年来,国产游戏行业蓬勃发展,技术水平不断提升,许多优秀作品在国际市场上崭露头角。从画面渲染到物理引擎,从AI技术到服务器架构,国产游戏已实现质的飞跃。然而,面对全球游戏市场的激烈竞争,国产游戏技术仍然面临诸多挑战。本文将探讨这些挑战,并展望未来的机遇,深入分析IT技术的创新将如何推动行业发展。 国产游戏技术现状 国产游戏在画面渲染、物理引擎、AI

AIGC6: 走进腾讯数字盛会

图中是一个程序员,去参加一个技术盛会。AI大潮下,五颜六色,各种不确定。 背景 AI对各行各业的冲击越来越大,身处职场的我也能清晰的感受到。 我所在的行业为全球客服外包行业。 业务模式为: 为国际跨境公司提供不同地区不同语言的客服外包解决方案,除了人力,还有软件系统。 软件系统主要是提供了客服跟客人的渠道沟通和工单管理,内部管理跟甲方的合同对接,绩效评估,BI数据透视。 客服跟客人

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

第四次北漂----挣个独立游戏的素材钱

第四次北漂,在智联招聘上,有个小公司主动和我联系。面试了下,决定入职了,osg/osgearth的。月薪两万一。 大跌眼镜的是,我入职后,第一天的工作内容就是接手他的工作,三天后他就离职了。 我之所以考虑入职,是因为 1,该公司有恒歌科技的freex平台源码,可以学学,对以前不懂的解解惑。 2,挣点素材钱,看看张亮002的视频,他用了6000多,在虚幻商城买的吸血鬼游戏相关的素材,可以玩两年。我