斯巴达

用户名：AcmeGaga

访问量：1972

签　名：

等　　级
排　　名	5405
经　　验	1544
参赛次数	0
文章发表	22
年　　龄	0
在职情况	学生
学　　校	河南大学
专　　业

　　自我简介：

TA的其他文章

1729: 还是畅通工程(Kruskal) java写法
浏览：97

1510: 蓝桥杯算法提高VIP-士兵排队问题(狗币java + 拓扑)
浏览：237

1450: 蓝桥杯2014年第五届真题-矩阵翻硬币 (java, 简单搬运)
浏览：147

你可能喜欢

A+B for Input-Output Practice (V) （C语言代码）

1443: 蓝桥杯历届试题-数字游戏 java

　　作者: 斯巴达　　　　发表时间：2022-02-27 23:22:42 浏览：112　|　评论：0　

原题链接：蓝桥杯历届试题-数字游戏

- 思路一
    
    ![](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/3e4e9c34-530b-411b-9876-69c3659d4639/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=AKIAT73L2G45EIPT3X45%2F20220227%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20220227T152140Z&X-Amz-Expires=86400&X-Amz-Signature=6ee34931351c0f28e46432a6814b871c45fea5d854ce0acdae434ffb04a8462f&X-Amz-SignedHeaders=host&response-content-disposition=filename%20%3D%22Untitled.png%22&x-id=GetObject)
    
    - 前面那个人报last,
    - 现在则报now, 有now = {i- [(k-1) - last]}%k,  now- -;
    - 当i%n == 0; 这时为dd报数
    - 总共报数次数为(T-1)*n
    
    复杂度为O(3*n^2)
    
    于是有代码如下
    
    - 代码1
        
        ```java
        import java.util.Scanner;
        
        public class Main {
        	public static void main(String[] args) {
        		Scanner scan = new Scanner(System.in);
        		long res =1, now=1, last=0;
        		int n = scan.nextInt();
        		int k = scan.nextInt();
        		//直接把总报号次数计算出来
        		long T = (scan.nextInt() -1) * n;
        		for(int i=1; i<=T; i++) {
        			last = now;
        			if(i+last>k-1) {
        				now = (i-k+1+last)%k;
        				now--;
        			}else 
        				now = last+i;
        			
        			//说明本次报号是主角
        			if(i%n==0) res+=now;
        		}
        		System.out.println(res);
        	}
        }
        ```
        
    
    我们提交发现会运行超时
    
- 思路二
    
    ![Untitled](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/88bc9a05-6b0f-4009-8a8c-51dd481a2559/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=AKIAT73L2G45EIPT3X45%2F20220227%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20220227T152453Z&X-Amz-Expires=86400&X-Amz-Signature=188cd45076a4df03d39c99666b05de98c59f627d3291d17d3849413efb8fb9f8&X-Amz-SignedHeaders=host&response-content-disposition=filename%20%3D%22Untitled.png%22&x-id=GetObject)
    
    若我们只关注dd, 即粉红色, 并且先不考虑从零开始. 结合i的递增数列规律我们有可能进一步优化代码
    
    - 第一次dd值为1, 第二次dd = dd + sum.  [S = 1+ 2 +3]
    - 第三次dd = dd + sum. [S= 4 + 5 +6]
    - ....
    
    蓝色为计算结果
    
    发现规律: 每个新的dd 等于上次加中间的差值, 而这个差值是等差数列的部分和, 而这个长度每次都是n
    
    所以只需要有本次计算的首项start, 以及本次数列的末位值last即可
    
    所以有 $sum = \frac{(last+nlast)*n}{2}$;  start=start+n;  last = start+n-1;
    
    这样计算而来的是每个人应该报的数, 对这个数直接求余, 发现dd%K就是栋栋应该报的数
    
    所以有代码:
    
    - 代码二
        
        ```java
        import java.util.Scanner;
        
        public class Main {
        	public static void main(String[] args) {
        		Scanner scan = new Scanner(System.in);
        		int n = scan.nextInt();
        		int k = scan.nextInt();
        		int T = scan.nextInt();
        		long  res=1L;
        		long dd = 1L, start = 1L, S , last;
        		for(int i=0; i<T-1; i++) {
        			last = n + start - 1L;
        			dd = (dd + (last + start)*n / 2)%k;
        			start = start+n;
        			res += dd%k;
        		}
        		System.out.println(res);
        	}
        }
        ```
        
        有时间复杂度O(n)

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

斯巴达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

母牛的故事（C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

1443: 蓝桥杯历届试题-数字游戏 java

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

三进制小数（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C二级辅导-计负均正（C语言代码）

斯巴达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

母牛的故事 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

1443: 蓝桥杯历届试题-数字游戏 java

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

三进制小数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C二级辅导-计负均正 （C语言代码）

母牛的故事（C语言代码）

　　评论区

三进制小数（C语言代码）

C二级辅导-计负均正（C语言代码）