当前位置: 首页 > news >正文

模拟算法.

一、引言:

模拟算法,简单来说,就是按照题目描述的步骤或规则,一步一步地用代码实现解决问题的过程。就像是你在玩一个游戏,游戏有它自己的规则,而你需要根据这些规则来做出相应的动作以完成特定的目标。

二、模拟算法的特点与技巧:

特点:

  • 代码量大(做好准备( •̀ ω •́ )✧迎接挑战)
  • 操作多
  • 思路复杂
  • 较为复杂的题,出错后难定位错误

技巧:

  • 动手前,尽量在电脑或演草纸列好思路
  • 代码中,尽量对代码模块化,写成函数,类(Java)/结构体(C++)
  • 对于一些会重复用到的概念,可以统一转化,方便处理
  • 调试代码时,可分块调试(对代码模块化的好处)
  • 写代码一定要思路清晰,不要想到啥写啥,按自己提前列好的思路书写

蓝桥常考题型:

基础模拟(字符串处理、日期处理),状态模拟,过程模拟等... 其中以基础模拟最常见。

笔者提醒:

模拟这个算法其实非常难,主要是逻辑上的麻烦,但正常刷题时我们都不把模拟的逻辑思维理清就直接做,如果这题没有太水的话,是非常容易错的。

模拟可以与任何算法同时出现,比如模拟与动归dp、模拟与搜索之类的。

而接下来的入门题型,就是“水题”!基础与进阶代码量会大一些。但这没啥好担心的,这毕竟是算法能力提升的基石-敲代码能力( ̄︶ ̄)↗ 。

三、练习:

模拟类型、是以编程题考察。

提示( •̀ ω •́ )✧

至少要独立思考10min,若20min后仍无思路在看解析,收获会更大!

入门

1、单身贵族游戏(解析)

2、简简单单的暴力题 (解析)

3、小浩的国际象棋(解析)

4、缩位求和(蓝桥真题)(解析)

5、Goshopping(解析)

基础

6、交换瓶子(蓝桥真题)

7、奇怪的数列(蓝桥真题)

8、长草(蓝桥真题)

基础-日期系列

9、跑步(蓝桥真题)

10、跑步计划(蓝桥真题)

11、定时任务(蓝桥真题)

进阶

12、赢球票 (蓝桥真题)

13、神奇闹钟(蓝桥真题)

【最后一题】拉马车 (蓝桥真题)

入门:

1、单身贵族游戏

问题描述

单身贵族游戏规则:游戏玩法似跳棋,但不能走步,只能跳;棋子只能跳过相邻的棋子(相邻位置上一定要有棋子)到空位上,并且把被跳过的棋子吃掉;棋子可以沿格线横、纵方向跳,但是不能斜跳。

在本题中,给定单身贵族游戏走若干步后的棋盘状态(不用判断是否合理),判断游戏是否已经结束了(即不能再走下去了)。

以下图(a)为单身贵族游戏的棋盘,图(b)演示了走棋的规则,图(c)所示的棋盘状态已经结束了,无法再走棋。

输入格式

输入数据占 77 行,描述了一个单身贵族游戏的棋盘状态。注意第 11、22、66、77 行的数据也是顶格的(在程序处理时,需要还原到棋盘中的位置)。每个位置上为 11 或 00,前者表示有棋子,后者表示没有。

输出格式

测试数据所表示的单身贵族游戏,如果游戏无法进行下去了,输出 yes,否则输出 no。

样例输入

000
001
0000001
0000000
0000101
000
000

 

样例输出

yes

Java版

import java.util.Scanner;public class Main {public static void main(String[] args) {// 定义一个 7x7 的二维数组,初始化为 0int[][] vec = new int[7][7];// 创建 Scanner 对象,用于读取输入Scanner scanner = new Scanner(System.in);// 读取 7 行字符串,并将其转换为数字存储到二维数组中for (int i = 0; i < 7; ++i) {String str = scanner.next();// 如果字符串长度为 3,将其存储到数组的第 2 到第 4 列if (str.length() == 3) {for (int j = 0; j < 3; ++j) {vec[i][j + 2] = str.charAt(j) - '0'; // 将字符转换为数字}} else {// 如果字符串长度为 7,将其存储到数组的第 0 到第 6 列for (int j = 0; j < 7; ++j) {vec[i][j] = str.charAt(j) - '0'; // 将字符转换为数字}}}// 定义一个布尔变量,用于判断游戏是否可以继续进行boolean flag = true;// 遍历数组的中间部分(第 1 到第 5 行和列)for (int i = 1; i < 6; ++i) {for (int j = 1; j < 6; ++j) {// 如果当前元素为 1,表示有一个棋子if (vec[i][j] == 1) {// 检查当前棋子的上下左右是否有其他棋子if (vec[i][j - 1] == 1 || vec[i][j + 1] == 1 || vec[i - 1][j] == 1 || vec[i + 1][j] == 1) {flag = false; // 如果有相邻的棋子,游戏可以继续进行}}}}// 如果 flag 为 true,表示游戏无法继续进行,输出 "yes"if (flag) {System.out.println("yes");} else {// 否则,输出 "no"System.out.println("no");}}
}----------------- scanner.next()方法的作用 ----------------------在 Java 中,String str = scanner.next(); 是用来从输入中读取一个字符串的。
具体来说,scanner.next() 方法会读取输入中的下一个单词(即由空格分隔的字符串),
并将其存储在变量 str 中。

C++版

#include <iostream>
#include <vector>
using namespace std;
int main()
{// 就是只是一个暴力问题vector<vector<int>> vec(7,vector<int>(7,0));for(int i=0; i<7; ++i){string str;cin>>str;// 将所有数字存入if(str.size()==3){for (int j = 0; j < 3; ++j) {vec[i][j+2] = str[j]-'0'; // 输入题目喽}}else{for (int j = 0; j < 7; ++j) {vec[i][j] = str[j]-'0';}}}// 改判断这个数字是否符合条件// 大致思路就是,只要所有棋,四周都没有其他棋,就算结束// 只要1附近没有1,就算结束bool flag = true;for(int i=1; i<6; ++i){for(int j=1; j<6; ++j){if(vec[i][j]==1){// 通过,对每一个棋子的四周进行判断,下、上、左、右if(vec[i][j-1]==1||vec[i][j+1]==1||vec[i-1][j]==1||vec[i+1][j]==1){flag = false;}}}}// 注意,是游戏无法进行下去!才是yesif(flag) cout<<"yes"<<endl;else cout<<"no"<<endl;return 0;
}

2、简简单单的暴力题

问题描述

有一个长为 nn 的序列 a1,a2.....ana1​,a2​.....an​ 与一个特殊的数 kk ,aiai​ 小于 kk 。

当一个序列(元素个数 size≥2size≥2 )中有一个数 xx 会等于其他数的总和 sumsum % kk ,即 sumsum % k==xk==x ,则说明此序列为好序列。例如 kk 为 55 ,一个序列为 [1,2,4][1,2,4] ,因为 (2+4)(2+4) % 5==15==1 所以他是一个好序列。

求在长度为 nn 的序列中有多少连续的子序列为好序列。

输入格式

输入共两行。

第一行包含两个数 nn , kk ,表示序列长和特殊的数。

第二行包含 nn 个小于k的非负整数 a1,a2,a3,…,ana1​,a2​,a3​,…,an​ 。

输出格式

输出一个数 sumsum 为好序列个数。

样例输入

3 3
2 2 1

 

样例输出

2

 

评测数据规模

对于 100100 %案例 1≤n≤10001≤n≤1000 , 1≤k≤101≤k≤10 。

样例说明

1≤l≤r≤31≤l≤r≤3 ,

l=1,r=1l=1,r=1 ,序列为: 22 不符合条件 不是好序列,

l=1,r=2l=1,r=2 ,序列为: 2,22,2 是好序列 2mod3==22mod3==2 ,

l=1,r=3l=1,r=3 ,序列为: 2,2,12,2,1 是好序列 (2+1)mod3==1(2+1)mod3==1 ,

l=2,r=2l=2,r=2 ,序列为: 22 不符合条件,不是好序列,

l=2,r=3l=2,r=3 ,序列为:2,12,1 不符合条件,不是好序列,

故好序列个数为 22 。

Java版

import java.util.Scanner;
// 本题的坑,真是大大的
// 注意!题目上说了,连续的子序列!切记是序列中衍生出来的子序列。
// 具体结合 ‘样例说明’,l代表起始位置,r代表结束位置
// 切记!本题for循环不宜过多套用,否则将会导致超时
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取序列长度 n 和特殊的数 kint n = scanner.nextInt();int k = scanner.nextInt();// 存储序列的数组int[] vec = new int[n];// 读取序列元素for (int i = 0; i < n; i++) {vec[i] = scanner.nextInt();}// 用于记录好序列的数量int num = 0;// 遍历所有可能的连续子序列for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 先计算当前子序列的总和int sum = 0;for (int z = i; z <= j; z++) {sum += vec[z];}// 遍历子序列中的每个元素,判断是否满足好序列的条件for (int z = i; z <= j; z++) {// 减去当前元素的值,得到除该元素外其他元素的总和sum -= vec[z];if (sum % k == vec[z]) {num++;break;}// 把减去的元素值加回去,恢复总和sum += vec[z];}}}// 输出好序列的数量System.out.println(num);}
}

C++版

#include <iostream>
#include <vector>
using namespace std;
// 本题的坑,真是大大的
// 注意!题目上说了,连续的子序列!切记是序列中衍生出来的子序列。
// 具体结合 ‘样例说明’,l代表起始位置,r代表结束位置
// 切记!本题最多能套3层for循环,更多则必会超时
int main()
{int n,k;cin>>n>>k;vector<int> vec(n,0);for(int i=0; i<n; ++i) cin>>vec[i];int num = 0;for(int i=0; i<n; ++i){for(int j=i+1; j<n; ++j){ // 不存在序列数为1的情况// 以上两行的作用是,遍历所有子序列int sum = 0;for(int z=i; z<=j; ++z) sum+=vec[z]; // 先计算,本数列总和for(int z=i; z<=j; ++z){sum -= vec[z]; // 从z到i,注意判断那个数if(sum%k==vec[z]){num++;break;}sum += vec[z]; // 前方减去了,这里加回去}}}cout<<num<<endl;return 0;
}

3、小浩的国际象棋

问题描述

小浩有一个大小为 N×NN×N 的国际象棋棋盘。

有 NN 个主教以之字形的形式放置在棋盘的矩阵上,坐标分别为 (1,1),(2,2),(1,3),(2,4),(1,5),…​(1,1),(2,2),(1,3),(2,4),(1,5),…​。

例如对于 N=4​N=4​,棋盘初始时为:

已知主教只能斜向移动且每次可以移动任意距离。

你的任务是找到最少的移动次数,满足对于所有 1≤i≤N1≤i≤N,棋盘矩阵上的格子 (i,i)​(i,i)​ 都被主教占领了。

对于 N=4​N=4​,最后的位置应该为:

输入格式

第一行输入一个正整数 TT 表示测试数据的组数。

接下来 TT 行每行输入一个正整数 NN 表示棋盘的大小。

输出格式

对于每组测试数据,输出一个整数表示满足题目要求所需要的最少的移动次数,并换行。

样例输入1

4
1
4
2
6

 

样例输出1

0
3
0
6

 

说明

样例 11:棋盘的主教一开始已经处于最终位置了。

样例 22: 我们最少需要 33 次移动:

  • 将主教从 (2,2)(2,2) 移动到 (4,4)(4,4)。
  • 将主教从 (1,3)(1,3) 移动到 (2,2)(2,2)。
  • 将主教从 (2,4)(2,4) 移动到 (3,3)(3,3)。

样例 3​3​:棋盘的主教一开始已经处于最终位置了。

评测数据规模

对于所有的评测数据,1≤T≤2×1051≤T≤2×105,1≤N≤1091≤N≤109。

Java版

import java.util.Scanner;
// 如果真要说,这其实就是一道观察题,首先分析 “说明”
// 然后在纸上画出,4个方格的、5个方格的、6个方格的,最终找出规律。
// 一般 思维题,就是找规律题
public class Main {public static void main(String[] args) {// 创建一个 Scanner 对象,用于从标准输入读取数据Scanner scanner = new Scanner(System.in);// 读取一个整数 t,表示测试用例的数量int t = scanner.nextInt();// 使用 while 循环处理 t 个测试用例while (t > 0) {// 读取每个测试用例中的整数 l,表示方格的数量int l = scanner.nextInt();// 如果方格数量 l 小于等于 2if (l <= 2) {// 输出 0 并换行System.out.println(0);} // 如果方格数量 l 等于 3else if (l == 3) {// 输出 2 并换行System.out.println(2);} // 如果方格数量 l 是偶数else if (l % 2 == 0) {// 根据规律计算结果并输出,结果为 2 加上 (l - 3) 除以 2 再乘以 3 最后加 1System.out.println(2 + ((l - 3) / 2) * 3 + 1);} // 如果方格数量 l 是奇数else {// 根据规律计算结果并输出,结果为 2 加上 (l - 3) 除以 2 再乘以 3System.out.println(2 + ((l - 3) / 2) * 3);}// 测试用例数量减 1t--;}// 关闭 Scanner 对象,释放资源scanner.close();}
}

C++版

#include <iostream>
using namespace std;
// 如果真要说,这其实就是一道观察题,首先分析 “说明”
// 然后在纸上画出,4个方格的、5个方格的、6个方格的,最终找出规律。
// 一般思维题,就是找规律题
int main()
{int t;cin>>t;while(t--){int l;cin>>l;if(l<=2) cout<<0<<endl;else if(l==3) cout<<2<<endl;else if(l%2==0) cout<<2+(l-3)/2*3+1<<endl;else cout<<2+(l-3)/2*3<<endl;}return 0;
}

 4、缩位求和(蓝桥真题)

题目描述

在电子计算机普及以前,人们经常用一个粗略的方法来验算四则运算是否正确。

比如:248×15=3720248×15=3720

把乘数和被乘数分别逐位求和,如果是多位数再逐位求和,直到是 1 位数,得

2+4+8=14==>1+4=52+4+8=14==>1+4=5;

1+5=61+5=6;

5×65×6

而结果逐位求和为 3。

5×65×6 的结果逐位求和与 3 符合,说明正确的可能性很大!!(不能排除错误)

请你写一个计算机程序,对给定的字符串逐位求和。

输入描述

输入为一个由数字组成的串,表示 n (n<1000)n (n<1000) 位数;

输出描述

输出为一位数,表示反复逐位求和的结果。

输入输出样例

示例

输入

35379

 

输出

9

 

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

Java版

import java.util.Scanner;
// 这道题,挺简单的
/*但是简单归简单,常人却往往会犯一个致命的错误在输入时,直接把数据放到一个 long 或 int 类型中,包错的!“n (n<1000) 位数”!1000位数,这得多大? 10的一千次方。所以,一般都先用string类型储存。
*/
public class Main {public static void main(String[] args) {// 创建一个 Scanner 对象,用于从标准输入读取数据Scanner scanner = new Scanner(System.in);// 声明一个 String 类型的变量 str,用于存储输入的字符串String str;// 从标准输入读取一行字符串并赋值给 strstr = scanner.nextLine();// 声明一个 long 类型的变量 num,用于存储每一轮各位数字之和,初始化为 0long num = 0;// 当字符串 str 的长度大于 1 时,继续循环while (str.length() > 1) {// 遍历字符串 str 中的每一个字符for (int i = 0; i < str.length(); ++i) {// 将字符转换为对应的数字,并累加到 num 中num += str.charAt(i) - '0';}// 将 num 转换为字符串,并赋值给 strstr = String.valueOf(num);// 将 num 重置为 0,以便下一轮计算num = 0;}// 输出最终结果System.out.println(str);// 关闭 Scanner 对象,释放资源scanner.close();}
}

C++版

#include <iostream>
#define ll long long
using namespace std;
// 这道题,挺简单的
/*但是简单归简单,常人却往往会犯一个致命的错误在输入时,直接把数据放到一个 long 或 int 类型中,包错的!“n (n<1000) 位数”!1000位数,这得多大? 10的一千次方。所以,一般都先用string类型储存。
*/int main()
{string str;cin>>str;ll num=0;while(str.size()>1){for(int i=0; i<str.size(); ++i){num+=str[i]-'0';}str=to_string(num);num=0;}cout<<str<<endl;return 0;
}

5、Goshopping

问题描述

最近 Awell 的运气特别好,这不,他在路边摊买彩票,居然中了大奖。秉着见者有份的原则,他准备请咱们学校 ACM-ICPC 训练基地的全体队员逛商场。

赶巧交大旁边有一家商场新店开张,正在进行打折促销活动。于是,咱们所有队员都在商场中大肆购买之后,在收银台前排起了长队。

话说回来,这家商场的打折方式有些奇怪:他们从在收银台前付账的所有 nn 位顾客中,所有的第 mm 的倍数名顾客享受七五折优惠,其余顾客只能享受九五折。为了方便付账,Awell 拜托老板将付账者的姓名和付款金额打印出来,作为参考。   你需要注意的是,在收银台前长长的队伍中,有的可不止是 ACM 队员,同样,还有很多交大的同学慕名前来消费,为了区分他们,我们规定,所有 ACM 队员必须在姓名前加上前缀 ACM。

现在,请机智的你为 Awell 编写一个小程序,算一算他总共需要花费多少钱呢?

输入格式

输入数据包含不超过 55 组,每组第一行有两个整数 n,m(1≤n,m≤1000)n,m(1≤n,m≤1000),分别代表着在收银台前队伍的全部人数,以及商家将会选择每第 mm 位顾客打 7.57.5 折。

接下来有 nn 行,每行将会输入消费者的姓名(长度不超过 2020 个字符),以及他们各自消费的金额(消费金额不超过 10001000)。

输出格式

每组数据输出一行,每行一个实数,表示 Awell 总共需要花费多少。

你应该注意的是,老板只收取“角”作为最小单位,而且他是一个锱铢必较的人,所以,如果你所付金额中存在小于 0.10.1 元的部分,那就至少要付 0.10.1 元给他(想着即将消瘦的钱包,Awell 泪目中)。

输入样例

4 2
Newee 123.12
ACMAwell 100
PRO 345.5
Sirius 456.99
5 2
Newee 123.12
ACMAwell 100
PROPHET 345.5
Sirius 456.99
ACMProphetK 100

 

输出样例

75.0
170.0

Java版

import java.util.Scanner;public class Main {public static void main(String[] args) {// 创建一个 Scanner 对象,用于从标准输入读取数据Scanner scanner = new Scanner(System.in);// 持续读取输入,直到没有更多输入为止while (scanner.hasNext()) {// 读取第一个整数,表示人数int n = scanner.nextInt();// 读取第二个整数,表示第 m 位顾客int m = scanner.nextInt();// 用于存储顾客的姓名String str;// 用于存储所有符合条件的顾客的总金额double all_money = 0;// 用于存储单个顾客的金额double money;// 循环 n 次,处理每位顾客的信息for (int i = 0; i < n; ++i) {// 读取顾客的姓名str = scanner.next();// 读取顾客的金额money = scanner.nextDouble();// 在顾客姓名后面追加三个 0str = str + "000";// 截取姓名的前三个字符str = str.substring(0, 3);// 判断当前顾客是否是第 m 位顾客且姓名前三位是 "ACM"if ((i + 1) % m == 0 && str.equals("ACM")) {// 如果是,按照 75% 的折扣计算金额并累加到总金额中all_money += money * 0.75;} // 判断姓名前三位是否是 "ACM"else if (str.equals("ACM")) {// 如果是,按照 95% 的折扣计算金额并累加到总金额中all_money += money * 0.95;}}// 实现四舍五入并保留一位小数,然后输出结果,同时换行System.out.printf("%.1f\n", all_money + 0.05);}// 关闭 Scanner 对象,释放资源scanner.close();}
}

C++版

#include <iostream>
using namespace std;
// 本题两大坑
// 1、输出函数的合理运用
// 2、换行符合的运用
int main()
{int n,m; // n(人数) m(第m位顾客)while(cin>>n>>m){string str;double all_money = 0;double money;for(int i=0; i<n; ++i){cin>>str>>money;str += "000";str = str.substr(0,3);if((i+1)%m==0 && str=="ACM"){all_money += money*0.75;}else if(str=="ACM") {all_money += money * 0.95;}}printf("%.1f\n",all_money+0.05); // 这里合理的结合了题目,与四舍五入的特性。}return 0;
}

 

基础:

6、交换瓶子(蓝桥真题)

题目描述

有 NN 个瓶子,编号 1 ~ NN,放在架子上。

比如有 5 个瓶子:

2 1 3 5 4

要求每次拿起 2 个瓶子,交换它们的位置。

经过若干次后,使得瓶子的序号为:

1 2 3 4 5

对于这么简单的情况,显然,至少需要交换 2 次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入描述

输入格式为两行:

第一行: 一个正整数 N (N<104)N (N<104), 表示瓶子的数目

第二行: NN 个正整数,用空格分开,表示瓶子目前的排列情况。

输出描述

输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。

输入输出样例

示例

输入

5
3 1 2 5 4

 

输出

3

Java版

import java.util.Scanner;
import java.util.ArrayList;
/*第一次看到这道题目的时候,我陷入了沉思...什么鬼经过观察,忽然发现,这道题目不就是 排序吗???把无序的换成有序的(1,2,3,4...),哈哈,可真是个大聪明!其实这道题有点像冒泡排序,但本质上却又相差甚远
*/
/*上一个模块只是拓展思维用的,没啥可信性。本题最好的解法,其实是对号入座。确保每次交换,一定有一个能回归原位,具体看代码*这种该死的,对代码的控制力度*
*/
public class Main {public static void main(String[] args) {// 创建 Scanner 对象,用于读取输入Scanner scanner = new Scanner(System.in);// 读取瓶子的数量int n = scanner.nextInt();// 创建一个数组,用于存储瓶子的编号int[] vec = new int[n + 1];for (int i = 1; i <= n; ++i) {vec[i] = scanner.nextInt();}// 初始化交换次数int ans = 0;// 遍历每个瓶子for (int i = 1; i <= n; ++i) {int j = i;// 如果当前瓶子的编号不是 iif (vec[j] != i) {// 找到编号为 i 的瓶子的位置while (vec[j] != i) {j++;}// 交换两个瓶子的位置int temp = vec[j];vec[j] = vec[i];vec[i] = temp;// 增加交换次数ans++;}}// 输出交换次数System.out.println(ans);// 关闭 Scanner 对象scanner.close();}
}

C++版

#include <iostream>
#include <vector>
using namespace std;
/*第一次看到这道题目的时候,我陷入了沉思...什么鬼经过观察,忽然发现,这道题目不就是 排序吗???把无序的换成有序的(1,2,3,4...),哈哈,可真是个大聪明!其实这道题有点像冒泡排序,但本质上却又相差甚远
*/
/*上一个模块只是拓展思维用的,没啥可信性。本题最好的解法,其实是对号入座。确保每次交换,一定有一个能回归原位,具体看代码*这种该死的,对代码的控制力度*
*/
int main()
{int n;cin>>n;vector<int> vec(n+1,0);for(int i=1; i<=n; ++i) cin>>vec[i];int ans = 0;for(int i=1; i<=n; ++i) {int j=i;if(vec[j]!=i){while(vec[j]!=i){j++;}vec[j]=vec[i];vec[i]=i;ans++;}}cout<<ans<<endl;return 0;
}

 7、奇怪的数列(蓝桥真题)

第一次看到这题,有点惊讶,这不又是一道,过程模拟吗!?
而且是过程模拟中一道 非常适合打基础 的题目
** 这该死的对代码的控制力度。

题目描述

从 X 星截获一份电码,是一些数字,如下:

13

1113

3113

132113

1113122113

⋯⋯

YY 博士经彻夜研究,发现了规律:

第一行的数字随便是什么,以后每一行都是对上一行"读出来"

比如第 2 行,是对第 1 行的描述,意思是:1 个 1,1 个 3,所以是:1113

第 3 行,意思是:3 个 1,1 个 3,所以是:3113

请你编写一个程序,可以从初始数字开始,连续进行这样的变换。

输入描述

第一行输入一个数字组成的串,不超过 100 位。

第二行,一个数字 nn,表示需要你连续变换多少次,nn 不超过 20。

输出描述

输出一个串,表示最后一次变换完的结果。

输入输出样例

示例

输入

5
7

输出

13211321322115

Java版

import java.util.Scanner;
public class Main {public static void main(String[] args) {// 创建一个 Scanner 对象,用于从标准输入读取数据Scanner scanner = new Scanner(System.in);// 读取原字符串String str1 = scanner.next();// 读取操作次数int t = scanner.nextInt();// 关闭 Scanner 对象,避免资源泄漏scanner.close();// 循环 t 次,进行字符串变换操作while (t-- > 0) {// 初始化计数器,用于记录连续相同字符的数量int num = 1;// 初始化当前字符为原字符串的第一个字符char c = str1.charAt(0);// 用于存储变换后的字符串StringBuilder str2 = new StringBuilder();// 遍历原字符串,从第二个字符开始for (int i = 1; i < str1.length(); i++) {// 如果当前字符与前一个字符不同if (c != str1.charAt(i)) {// 将连续相同字符的数量和该字符添加到 str2 中str2.append(num).append(c);// 重置计数器为 1num = 1;// 更新当前字符为新的字符c = str1.charAt(i);} else {// 如果当前字符与前一个字符相同,计数器加 1num++;}}// 处理字符串的最后一组连续相同字符str2.append(num).append(c);// 将变换后的字符串赋值给 str1str1 = str2.toString();}// 输出最终变换后的字符串System.out.println(str1);}
}

C++版

#include <iostream>
using namespace std;
/*第一次看到这题,有点惊讶,这不又是一道,过程模拟吗!?而且是过程模拟中一道 非常适合打基础 的题目。
*/
/*这该死的对代码的控制力度
*/
int main()
{int t;string str1; // 原字符串string str2=""; // 接受更换的字符串cin>>str1>>t;while(t--){int num = 1;char c = str1[0];for(int i=1; i<str1.size(); ++i){if(c!=str1[i]){ // 关键点处str2 += to_string(num) + c;num = 1;c=str1[i];}else{num++;}}str2 += to_string(num) + c;str1 = str2;str2 = "";}cout<<str1<<endl;return 0;
}

8、长草(蓝桥真题)

与其说本题是一道模拟题,倒不如说本题是一道考察深搜的bfs题目。
 思考良久,感觉挺遗憾的,本题没有用正宗的bfs(递归)方法写出来。
 网上找了好多答案,都是七七八八,甚至有用队列的。
 那本题,就当作是一个学习bfs过渡题吧。

题目描述

小明有一块空地,他将这块空地划分为 nn 行 mm 列的小块,每行和每列的长度都为 1。

小明选了其中的一些小块空地,种上了草,其他小块仍然保持是空地。

这些草长得很快,每个月,草都会向外长出一些,如果一个小块种了草,则它将向自己的上、下、左、右四小块空地扩展,

这四小块空地都将变为有草的小块。请告诉小明,kk 个月后空地上哪些地方有草。

输入描述

输入的第一行包含两个整数 n,mn,m。

接下来 nn 行,每行包含 mm 个字母,表示初始的空地状态,字母之间没有空格。如果为小数点,表示为空地,如果字母为 gg,表示种了草。

接下来包含一个整数 kk。 其中,2≤n,m≤1000,1≤k≤10002≤n,m≤1000,1≤k≤1000。

输出描述

输出 nn 行,每行包含 mm 个字母,表示 kk 个月后空地的状态。如果为小数点,表示为空地,如果字母为 gg,表示长了草。

输入输出样例

示例

输入

4 5
.g...
.....
..g..
.....
2

 

输出

gggg.
gggg.
ggggg
.ggg.

 

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

Java版

import java.util.Scanner;
// 优化技巧,预处理打表 -> 提前开辟数组
// 定义全局变量 a 和 b,用于存储草地状态
public class GrassGrowthSimulation {// 全局变量 a,用于存储草地的当前状态static int[][] a = new int[1005][1005];// 全局变量 b,用于复刻 a 的状态,辅助更新草地状态static int[][] b = new int[1005][1005];public static void main(String[] args) {// 创建 Scanner 对象,用于从标准输入读取数据Scanner scanner = new Scanner(System.in);// 读取草地的行数 n 和列数 mint n = scanner.nextInt();int m = scanner.nextInt();// 消耗掉 nextInt() 后的换行符scanner.nextLine();// 读取草地的初始状态for (int i = 0; i < n; i++) {// 读取一行字符串,表示当前行的草地状态String str = scanner.nextLine();for (int j = 0; j < m; j++) {// 如果字符为 '.',表示没有草,将 a[i][j] 设为 0if (str.charAt(j) == '.') a[i][j] = 0;// 否则表示有草,将 a[i][j] 设为 1else a[i][j] = 1;}}// 读取需要模拟的天数 kint k = scanner.nextInt();// 关闭 Scanner 对象,防止资源泄漏scanner.close();// 循环 k 次,模拟每天草地的扩展while (k-- > 0) {// 调用 dfs 方法进行草地状态的更新dfs(n, m);}// 输出最终的草地状态for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果 a[i][j] 为 0,表示没有草,输出 '.'if (a[i][j] == 0) System.out.print(".");// 否则表示有草,输出 'g'else System.out.print("g");}// 换行,输出下一行的草地状态System.out.println();}}// dfs 方法用于更新草地的状态public static void dfs(int n, int m) {// 将 a 数组的值复制到 b 数组中,防止在更新 a 数组时产生不必要的影响for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {b[i][j] = a[i][j];}}// 遍历 b 数组,根据 b 数组的值更新 a 数组for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果 b[i][j] 为 1,表示该位置有草if (b[i][j] == 1) {// 检查上方位置,如果存在且没有草,则将其设为有草if (i>=1) a[i - 1][j] = 1;// 检查下方位置,如果存在且没有草,则将其设为有草if (i<n-1) a[i + 1][j] = 1;// 检查左方位置,如果存在且没有草,则将其设为有草if (j>=1) a[i][j - 1] = 1;// 检查右方位置,如果存在且没有草,则将其设为有草if (j<m-1) a[i][j + 1] = 1;}}}}
}
/*拓展: 像本题打表时起初我用的是 a[10005][10005],b[10005][10005]而 a 和 b 数组占用的空间非常大(10001 * 10001 * 4 * 2 字节,约 760MB)本题给出的是:最大运行时间:1s最大运行内存: 256M所以合适最好。*/

C++版

#include <iostream>
using namespace std;
/*与其说本题是一道模拟题,倒不如说本题是一道考察深搜的bfs题目
*/
/*思考良久,感觉挺遗憾的,本题没有用正宗的bfs(递归)方法写出来网上找了好多答案,都是七七八八,甚至有用队列的那本题,就当作是一个学习bfs过渡题吧
*/
/*拓展: 像本题打表时起初我用的是 a[10005][10005],b[10005][10005]而 a 和 b 数组占用的空间非常大(10001 * 10001 * 4 * 2 字节,约 760MB)本题给出的是:最大运行时间:1s最大运行内存: 256M所以合适最好。*/
// 优化技巧,预处理打表 -> 提前开辟数组
int a[1005][1005],b[1005][1005]; // a是正确的储存,b用来复刻
void dfs(int n, int m){// 转移到b组,防止a组扩张,产生不必要的影响for(int i=0; i<n; ++i)for(int j = 0; j<m; ++j)b[i][j]=a[i][j];for(int i=0; i<n; ++i){for(int j=0; j<m; ++j){if(b[i][j]==1){ // 有草的前提下// 设置边界,i与j的边界都要不同if(i>=1) a[i-1][j]=1;if(i<n-1) a[i+1][j]=1;if(j>=1) a[i][j-1]=1;if(j<m-1) a[i][j+1]=1;}}}
}int main()
{int n,m,k;cin>>n>>m;string str;
// 输入// 有草的地方设为1,没草的地方谁for(int i=0; i<n; ++i){cin>>str;for(int j = 0; j<m; ++j){if(str[j]=='.') a[i][j]=0;else a[i][j]=1;}}cin>>k; // 输入一共需要多少天while(k--){dfs(n,m); // 每天向外扩展一圈}
// 输出for(int i=0; i<n; ++i){for(int j = 0; j<m; ++j){if(a[i][j]==0) cout<<".";else cout<<"g";}cout<<endl;}return 0;
}

日期系列

9、跑步(蓝桥真题)

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

问题描述

小蓝每周六、周日都晨跑,每月的 11、1111、2121、3131 日也晨跑。其它时间不晨跑。

已知 20222022 年 11 月 11 日是周六,请问小蓝整个 20222022 年晨跑多少天?

Java版

public class Main {public static void main(String[] args) {// 初始化天数,初始值为 2int day = 2;// 用于标记经过的总天数int flag = 0;// 定义一个数组,存储每个月的天数,假设这一年是闰年,2 月有 29 天int[] monthDay = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 外层循环遍历每个月for (int i = 0; i < monthDay.length; i++) {// 内层循环遍历当前月的每一天for (int j = 0; j < monthDay[i]; j++) {// 跳过 1 月的第 2 天和第 3 天的重复计算if (i == 0 && (j == 1 || j == 2)) {continue;}// 经过的总天数加 1flag++;// 判断是否满足增加天数的条件if (flag % 6 == 0 || flag % 7 == 0 || j + 1 == 11 || j + 1 == 1 || j + 1 == 21 || j + 1 == 31) {// 如果满足条件,总天数加 1day++;}}}// 输出最终的天数System.out.println(day);}
}

C++版

#include <iostream>
using namespace std;
int main()
{// 首先判断是否为闰年,不是闰年,2月有29天int day = 2;int flag = 0;// 本题主打合理运用数据进行计算int monthDay[] = {31,29,31,30,31,30,31,31,30,31,30,31};for(int i=0; i<sizeof(monthDay)/sizeof(monthDay[0]); ++i){ for(int j=0; j<monthDay[i]; ++j){if(i==0&&(j==1||j==2)) continue; // 跳过重复计算flag++;if(flag%6==0 || flag%7==0 || j+1==11 || j+1==1|| j+1==21 || j+1==31) day++;}}cout<<day<<endl;return 0;
}// 数组定义的三种格式
// 数据类型 数组名[长度]
// 数据类型 数组名[数组长度] = { 值1,值2 ... };
// 数据类型 数组名[] = { 值1,值2 ... };

10、跑步计划(蓝桥真题)

问题描述

小蓝计划在某天的日期中出现 11 时跑 55 千米,否则只跑 11 千米。注意日期中出现 11 不仅指年月日也指星期。

请问按照小蓝的计划,20232023 年小蓝总共会跑步锻炼多少千米?例如,55 月 11 日、11 月 1313 日、1111 月 55 日、44 月 33 日 (星期一) 小蓝会跑 55 千米,而 55 月 2323 日小蓝会跑 11 千米 (示例日期均为 20232023 年)

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

Java版

import java.util.Scanner;public class Main {public static void main(String[] args) {// 用于累加最终结果的变量,初始化为 0int s = 0;// 定义一个数组,存储平年每个月的天数int[] monthDay = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 用于记录从年初开始累计的天数int flag = 0;// 外层循环,遍历一年中的每个月for (int i = 0; i < monthDay.length; i++) {// 内层循环,遍历当前月份的每一天for (int j = 0; j < monthDay[i]; j++) {// 每过一天,累计天数加 1flag++;// 判断是否满足月份相关的条件if (i + 1 == 1 || i + 1 >= 10) {// 如果是 1 月或者 10 月及以后的月份,累加 5 到结果中s += 5;} // 判断是否满足日期相关的条件else if (j + 1 == 1 || (10 <= j + 1 && j + 1 <= 19) || j + 1 == 21 || j + 1 == 31) {// 如果是 1 号、10 - 19 号、21 号或者 31 号,累加 5 到结果中s += 5;} // 判断是否满足星期相关的条件else if (flag % 7 == 2) {// 如果当前累计天数对 7 取余结果为 2,累加 5 到结果中s += 5;} else {// 如果不满足上述任何条件,累加 1 到结果中s++;}}}// 输出最终的累加结果System.out.println(s);}
}

C++版

#include <iostream>
using namespace std;
int main()
{int s = 0;int monthDay[] = {31,28,31,30,31,30,31,31,30,31,30,31}; // 每月日期// 需考虑 3 种情况// 1、月份// 2、日期// 3、星期 , 找准1月1,是几月几日非常重要int flag = 0;for(int i=0; i<sizeof(monthDay)/sizeof(monthDay[0]); ++i){for(int j=0; j<monthDay[i]; ++j){flag++;if(i+1==1 || i+1>=10){ // 月份s += 5;}else if(j+1==1 || (10<=j+1 && j+1<=19) || j+1 == 21 || j+1 == 31){ // 日s += 5;}else if(flag%7==2){ // 星期s += 5;}else{s++;}}}cout<<s<<endl;return 0;
}

11、定时任务(蓝桥真题)

问题描述

Cron 表达式在定时任务中经常被使用,在这里我们用了一种简化后的版本 SimpleCron 表达式:SimpleCron 表达式是一个具有时间含义的字符串,字符串以 44 个空格隔开,分为 55 个域,格式为 XXXXXXXXXX,其中 XX 是一个域的占位符。55 个域从左至右依次为秒 (0−59)(0−59)、分钟 (0−59)(0−59)、小时 (0−23)(0−23)、日期 (1−31)(1−31)、月份 (1−12)(1−12),其中括号内为他们各自的取值范围。同时域内取值也可以使用一些特殊字符(每个域内只能使用一种特殊字符):

  1. 特殊字符 ∗∗ (ASCII 码为 4242)表示所有可能的值。例如:在分钟域内表示每一分钟;在日期域内表示月内的每一天。
  2. 特殊字符 ,, (ASCII 码为 4444)表示列出枚举值。例如:在秒域内,3,203,20 表示分别在 33 秒和 2020 秒执行一次任务。
  3. 特殊字符 −− (ASCII 码为 4545)表示范围,可以视为连续的若干个枚举值。例如:1−51−5 等价于 1,2,3,4,51,2,3,4,5。

例如,421,3,151−31∗421,3,151−31∗表示的含义是每个月份中的每一天中的 01:02:0401:02:04、03:02:0403:02:04、15:02:0415:02:04 这三个时刻各执行一次,在 20232023 年一共会执行 10951095 次。

现在给出你一个合法的 SimpleCron 表达式,其中用到的所有数字均没有前导零。请问在 20232023 一整年当中,使用了这个表达式的定时任务总计会执行多少次?

输入格式

输入一行,包含一个 SimpleCron 字符串。

输出格式

输出一行,包含一个整数表示答案。

样例输入

4 2 1,3,15 1-31 *

 

样例输出

1095

Java版

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 生成数量的方法,根据输入的字符串和范围生成对应的数字列表public static List<Integer> generateNum(String str, int range) {List<Integer> res = new ArrayList<>();int cur = 0;int lis = -1; // 作用于 - 时// 遍历输入字符串中的每个字符for (char c : str.toCharArray()) {if (c == ',') {// 遇到逗号,将当前累计的数字添加到结果列表中,并重置当前数字res.add(cur);cur = 0;} else if (c == '-') {// 遇到减号,记录当前数字作为范围起始值,并重置当前数字lis = cur;cur = 0;} else if (c == '*') {// 遇到星号,将 1 到 range 的所有数字添加到结果列表中for (int i = 0; i < range; i++) {res.add(i + 1);}return res;} else {// 其他情况,将字符转换为数字并累加到当前数字中cur = cur * 10 + (c - '0');}}// 处理范围情况if (lis != -1) {for (int i = lis; i <= Math.min(range, cur); i++) {res.add(i);}} else {// 没有范围,直接添加当前数字res.add(cur);}return res;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 每个月份对应的天数int[] monthDay = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 输入秒、分、时、日、月的配置信息String S = scanner.next();String M = scanner.next();String H = scanner.next();String D = scanner.next();String MON = scanner.next();// 计算秒、分、时的可能组合数量int num1 = generateNum(S, 60).size() * generateNum(M, 60).size() * generateNum(H, 24).size();// 计算最终的可能组合数量int num2 = 0;// 遍历每个可能的月份for (int i : generateNum(MON, 12)) {// 每个 i 都是月份num2 += generateNum(D, monthDay[i - 1]).size() * num1;}// 输出结果System.out.println(num2);scanner.close();}
}

C++版

#include "bits/stdc++.h"
using namespace std;// 我很佩服这道题,缘由是因为,它通过vector巧妙地代替了数字,合理的搭配、vector的巧妙运用与for-range的运用,让人感觉道赏心悦目vector<int> generateNum(string str, int range){ // 生成数量vector<int> res;// (每个域内只能使用一种特殊字符)int cur=0;int lis = -1; // 作用于-时,for(char c : str){if(c==','){res.push_back(cur);cur = 0;}else if(c=='-'){lis = cur;cur = 0;}else if(c=='*'){for(int i=0; i<range; i++) res.push_back(i+1);return res;}else{ // 这个用来计算时间cur = cur*10 + c-'0';}}// 存入if(lis!=-1){for(int i=lis; i<=min(range,cur); ++i) res.push_back(i);}else{res.push_back(cur);}return res;
}int main()
{int monthDay[] = {31,28,31,30,31,30,31,31,30,31,30,31}; // 每个月份,对应的天数// 用集合代替,次数,简直是一个天才string S,M,H,D,MON; cin>>S>>M>>H>>D>>MON; // 输入所有// 计算秒、分、时的可能int num1 = generateNum(S,60).size()*generateNum(M,60).size()*generateNum(H,24).size();// 对月份也是有要求的int num2 = 0;for(int i : generateNum(MON,12)){// 每个i都是月份num2+= generateNum(D,monthDay[i-1]).size()*num1;}cout<<num2<<endl;return 0;
}

 

进阶:

12、赢球票 (蓝桥真题)

题目描述

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。

主持人拿出 NN 张卡片(上面写着 1⋯N1⋯N 的数字),打乱顺序,排成一个圆圈。

你可以从任意一张卡片开始顺时针数数: 1,2,3 ⋯⋯

如果数到的数字刚好和卡片上的数字相同,则把该卡片收入囊中,从下一个卡片重新数数。

直到再无法收获任何卡片,游戏结束。囊中卡片数字的和就是赢得球票的张数。

比如:

卡片排列是:1 2 3

我们从 1 号卡开始数,就把 1 号卡拿走。再从 2 号卡开始,但数的数字无法与卡片对上,很快数字越来越大,不可能再拿走卡片了。因此这次我们只赢得了 1 张球票。

还不算太坏!如果我们开始就傻傻地从 2 或 3 号卡片数起,那就一张卡片都拿不到了。

如果运气好,卡片排列是 2 1 3,那我们可以顺利拿到所有的卡片!

本题的目标:已知顺时针卡片序列,随便你从哪里开始数,求最多能赢多少张球票(就是收入囊中的卡片数字之和)

输入描述

第一行一个整数 NN (N≤100N≤100),表示卡片数目。

第二行 NN 个整数,表示顺时针排列的卡片。

输出描述

输出一行,一个整数,表示最好情况下能赢得多少张球票。

输入输出样例

示例

输入

3
1 2 3

 

输出

1

Java版

import java.util.Scanner;
import java.util.Arrays;
/*简单列一下思路1、先列一个循环将所有可能循环一遍2、然后标记一个数,判断最大值是否已经大于纸牌最大值,否则结束3、拿走某个牌时,可用数据记忆是否遍历过这个。
*/
public class CardGame {public static void main(String[] args) {// 创建 Scanner 对象用于从标准输入读取数据Scanner scanner = new Scanner(System.in);// 读取纸牌的数量 nint n = scanner.nextInt();// 创建一个长度为 n 的整型数组来存储每张纸牌的值int[] vec = new int[n];// 循环读取 n 张纸牌的值并存储到数组 vec 中for (int i = 0; i < n; i++) {vec[i] = scanner.nextInt();}// 用于记录最大的得分,初始化为 0int flag = 0;// 从每个位置开始进行一次完整的尝试for (int i = 0; i < n; i++) {// 创建一个长度为 n 的布尔型数组,用于标记每张纸牌是否已被使用// 初始值都为 false,表示所有纸牌都未被使用boolean[] used = new boolean[n];// 记录当前已经消除的纸牌数量,用于判断是否所有纸牌都已消除int cur = 0;// 当前处理的纸牌的索引,从位置 i 开始int index = i;// 当前要匹配的纸牌张数,初始为 1int count = 1;// 当前获得的得分,初始为 0int num = 0;// 开始一个无限循环,模拟依次检查纸牌的过程while (true) {// 如果当前位置的纸牌还未被使用if (!used[index]) {// 检查当前纸牌的值是否等于要匹配的纸牌张数if (vec[index] == count) {// 若相等,说明可以消除这张纸牌cur++;  // 消除的纸牌数量加 1num += count;  // 得分加上当前匹配的纸牌张数used[index] = true;  // 标记这张纸牌已被使用count = 1;  // 重置要匹配的纸牌张数为 1} else {// 若不相等,要匹配的纸牌张数加 1count++;}}// 更新索引,通过取模运算确保索引在 0 到 n - 1 的范围内循环index = (index + 1) % n;// 判断是否满足结束条件:要匹配的纸牌张数大于 n 或者所有纸牌都已消除if (count > n || cur == n) {break;  // 满足条件则跳出循环}}// 更新最大得分,取当前尝试的得分和之前记录的最大得分中的较大值flag = Math.max(num, flag);}// 输出最大得分System.out.println(flag);// 关闭 Scanner 对象,释放资源scanner.close();}
}

C++版

#include <iostream>
#include <vector>
using namespace std;
/*其实不是我说,要是我就直接暴力求解了
*/
/*让我简单列一下思路1、先列一个循环将所有可能循环一遍2、然后标记一个数,判断最大值是否已经大于纸牌最大值,否则结束3、拿走某个牌时,可用数据记忆是否遍历过这个。
*/
int main()
{int n;cin>>n;vector<int> vec(n,0);for(int i=0; i<n; ++i) cin>>vec[i];int flag=0;for(int i=0; i<n; ++i){ // 以此从每个地点开始一次vector<bool> used(n, false); // 为false表示,表示未用过int cur = 0; // 消除的卡牌个数,本题用于判断结束条件int index = i; // 索引,int count = 1; // 卡牌张数int num = 0; // 当前的求票总和while(1){ // 开始循环if(!used[index]) { // 改位置的卡牌还存在if (vec[index] == count) { // 确保能匹配那个数据cur++;num+=count;used[index] = true;count = 1;} else { // 不同时count++;}}index = (index+1)%n; // 维持正常循环if(count>n||cur==n) break; // 对!结束的不应该这么草率}// 这里存储一下flag = max(num,flag);}cout<<flag<<endl;return 0;
}

 13、神奇闹钟(蓝桥真题)

问题描述

小蓝发现了一个神奇的闹钟,从纪元时间(19701970 年 11 月 11 日 00:00:0000:00:00)开始,每经过 xx 分钟,这个闹钟便会触发一次闹铃 (纪元时间也会响铃)。这引起了小蓝的兴趣,他想要好好研究下这个闹钟。

对于给出的任意一个格式为 уууу-MM-ddHH:mm:ssуууу-MM-ddHH:mm:ss 的时间,小蓝想要知道在这个时间点之前 (包含这个时间点) 的最近的一次闹铃时间是哪个时间?

注意,你不必考虑时区问题。

输入格式

输入的第一行包含一个整数 TT,表示每次输入包含 TT 组数据。

接下来依次描述 TT 组数据。

每组数据一行,包含一个时间(格式为 уууу-MM-ddHH:mm:ssуууу-MM-ddHH:mm:ss)和一个整数 xx,其中 xx 表示闹铃时间间隔(单位为分钟)。

输出格式

输出 TT 行,每行包含一个时间(格式为 уууу-MM-ddHH:mm:ssуууу-MM-ddHH:mm:ss),依次表示每组数据的答案。

样例输入

2
2016-09-07 18:24:33 10
2037-01-05 01:40:43 30

 

样例输出

2016-09-07 18:20:00
2037-01-05 01:30:00

 

评测用例规模与约定

对于所有评测用例,1≤T≤10,1≤x≤10001≤T≤10,1≤x≤1000,保证所有的时间格式都是合法的。

Java版

import java.util.Scanner;// 在这里,我先声明一下,答案上能套更简单的模版,但意义不大
// 但如果实在想用模版,都行,这里更多的细节与思路public class TimeCalculation {// 计算从 1970 年 1 月 1 日到指定日期和时间的总分钟数public static long generate(int year, int month, int day, int hour, int minute, int second, int sub) {int totalDays = 0;// 计算从 1970 年到指定年份前一年的总天数for (int y = 1970; y < year; y++) {if (isLeapYear(y)) {totalDays += 366;} else {totalDays += 365;}}// 计算到指定月份前一个月的总天数for (int m = 1; m < month; m++) {totalDays += getDaysInMonth(m, year);}// 加上指定日期的天数(减去 1 是因为从 1 号开始算)totalDays += (day - 1);// 计算总分钟数return (long) totalDays * 24 * 60 + hour * 60 + minute;}// 判断是否为闰年public static boolean isLeapYear(int year) {return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);}// 获取指定月份的天数public static int getDaysInMonth(int month, int year) {switch (month) {case 1:case 3:case 5:case 7:case 8:case 10:case 12:return 31;case 4:case 6:case 9:case 11:return 30;case 2:return isLeapYear(year) ? 29 : 28;default:return 0;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int t = scanner.nextInt(); // 读取测试用例的数量for (int i = 0; i < t; i++) {// 读取日期和时间信息String date = scanner.next();String time = scanner.next();int sub = scanner.nextInt();// 解析日期信息String[] dateParts = date.split("-");int year = Integer.parseInt(dateParts[0]);int month = Integer.parseInt(dateParts[1]);int day = Integer.parseInt(dateParts[2]);// 解析时间信息String[] timeParts = time.split(":");int hour = Integer.parseInt(timeParts[0]);int minute = Integer.parseInt(timeParts[1]);int second = Integer.parseInt(timeParts[2]);// 计算总分钟数long allMinutes = generate(year, month, day, hour, minute, second, sub);// 消减时间差long adjustedMinutes = allMinutes - (allMinutes % sub);// 计算对应的天数、小时和分钟long totalDays = adjustedMinutes / (24 * 60);long hours = (adjustedMinutes / 60) % 24;long minutes = adjustedMinutes % 60;// 初始化日期和时间long currentYear = 1970;long currentMonth = 1;long currentDay = 1;// 逐年累加,直到剩余天数不足一年while (totalDays >= 0) {int daysInYear = isLeapYear((int) currentYear) ? 366 : 365;if (totalDays < daysInYear) {break;}totalDays -= daysInYear;currentYear++;}// 逐月累加,直到剩余天数不足一个月while (totalDays > 0) {int daysInMonth = getDaysInMonth((int) currentMonth, (int) currentYear);if (totalDays < daysInMonth) {break;}totalDays -= daysInMonth;currentMonth++;}// 加上剩余的天数currentDay += totalDays;// 格式化输出结果System.out.printf("%04d-%02d-%02d %02d:%02d:%02d\n", (int) currentYear, (int) currentMonth, (int) currentDay, (int) hours, (int) minutes, 0);}scanner.close();}
}

C++版

#include "bits/stdc++.h"
#define ll long long
using namespace std;ll generate(int y,int M,int d,int h,int m,int s,int sub){ // 这里面有一个精致的细节,时间是从1月1日开始,而非0点0时0分!int D = 0; // 计算天数for(int i=1970; i<=y-1; ++i){ // 算年if( (i%4==0 && i%100!=0) ||  i%400==0){ // 是闰年,!!!这个判断相当重要D+=366;}else{ // 是平年D+=365;}}for(int i=1; i<=M-1; ++i){ // 算月!!!是到 M-1月,否则会多运算if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12) D+=31;else if(i==2&&((y%4==0 && y%100!=0) || y%400==0)) D+=29;else if(i==2) D+=28;else D+=30;}D+=(d-1); // 算日// 返回分钟ll num = D*(24*60) + h*60 + m;return num;
}// 从新来过
// 这次从新来过
int main(){int t;cin>>t;while(t--){// 获得时间差int y,M,d,h,m,s,sub;scanf("%d-%d-%d %d:%d:%d %d",&y,&M,&d,&h,&m,&s,&sub);// 消减时间差ll all_min = generate(y,M,d,h,m,s,sub); // 生成总时间ll acc_time = all_min - (all_min%sub);// 现在已经取到时间,仅需顺流而上即可ll lday,lh,lm;lday = acc_time/(24*60); // 求出天数lh = acc_time/(60)%24; // 求出小时lm = acc_time%(60);// 求出分钟ll YYYY = 1970;ll MM = 1;ll dd = 1;ll HH = lh;ll mm = lm;ll ss = 0;while(lday>=0){ // 加年if( (YYYY%4==0 && YYYY%100!=0) || YYYY%400==0){if(lday<366) break;lday-=366;}else{if(lday<365) break;lday-=365;}YYYY++;}while(lday>0){ // 加月if(MM==1 || MM==3 || MM==5 || MM==7 || MM==8 || MM==10 || MM==12){ // 31天的月if(lday<31) break;lday-=31;}else if(MM==2 &&((YYYY%4==0 && YYYY%100!=0) || YYYY%400==0)){ // 闰年if(lday<29) break;lday-=29;}else if(MM==2){if(lday<28) break;lday-=28;}else{if(lday<30) break;lday-=30;}MM++; // 说实话,我对这一步,表示有点无法理解}dd += lday;printf("%04lld-%02lld-%02lld %02lld:%02lld:%02lld\n",YYYY,MM,dd,HH,mm,ss); // 切记,这里一定要换行}return 0;
}// 记录,如何判断,闰年中的闰月
// 劝告,最好封装一下函数,因为越多的代码,就意味着可能有更多的纰漏
// 不过咱们那个时区计算,好像可有可无

 

 

【最后一题】拉马车 (蓝桥真题)

本题涉及知识点,栈、堆、队列、set集合,对此不了解的,请点击下方链接!

1、什么是栈、队列(基础了解)

2、栈、队列(深入了解)

3、Java中栈和队列的使用及区别(具体用法)

( •̀ ω •́ )y,一点一点学,都能掌握的

题目描述

小的时候,你玩过纸牌游戏吗?

有一种叫做"拉马车"的游戏,规则很简单,却很吸引小朋友。

其规则简述如下:

假设参加游戏的小朋友是 AA 和 BB ,游戏开始的时候,他们得到的随机的纸牌序列如下:

AA 方:[K,8,X,K,A,2,A,9,5,A][K,8,X,K,A,2,A,9,5,A]

BB 方:[2,7,K,5,J,5,Q,6,K,4][2,7,K,5,J,5,Q,6,K,4]

其中的 XX 表示 "10",我们忽略了纸牌的花色。

从 AA 方开始,A、BA、B双方轮流出牌。

当轮到某一方出牌时,他从自己的纸牌队列的头部拿走一张,放到桌上,并且压在最上面一张纸牌上(如果有的话)。

此例中,游戏过程:

AA 出 KK,BB 出 22,AA 出 88,BB 出 77,AA 出 XX,此时桌上的序列为:

K,2,8,7,XK,2,8,7,X

当轮到 BB 出牌时,他的牌 KK 与桌上的纸牌序列中的 KK 相同,则把包括 KK 在内的以及两个 KK 之间的纸牌都赢回来,放入自己牌的队尾。注意:为了操作方便,放入牌的顺序是与桌上的顺序相反的。

此时,A、BA、B双方的手里牌为:

AA 方:[K,A,2,A,9,5,A][K,A,2,A,9,5,A]

B 方:[5,J,5,Q,6,K,4,K,X,7,8,2,K][5,J,5,Q,6,K,4,K,X,7,8,2,K]

赢牌的一方继续出牌。也就是 BB 接着出 55,AA 出 KK,BB 出 JJ,AA 出 AA,BB 出 55,又赢牌了。此时桌上的序列为:

5,K,J,A,55,K,J,A,5

此时双方手里牌:

AA 方:[2,A,9,5,A][2,A,9,5,A]

BB 方:[Q,6,K,4,K,X,7,8,2,K,5,A,J,K,5][Q,6,K,4,K,X,7,8,2,K,5,A,J,K,5]

注意:更多的时候赢牌的一方并不能把桌上的牌都赢走,而是拿走相同牌点及其中间的部分。但无论如何,都是赢牌的一方继续出牌,有的时候刚一出牌又赢了,也是允许的。

当某一方出掉手里最后一张牌,但无法从桌面上赢取牌时,游戏立即结束。

对于本例的初始手牌情况下,最后 AA 会输掉,而 BB 最后的手里牌为:

9K2A62KAX58K57KJ59K2A62KAX58K57KJ5

本题的任务就是已知双方初始牌序,计算游戏结束时,赢的一方手里的牌序。当游戏无法结束时,输出 -1。

输入描述

输入为 2 行,2 个串,分别表示 A、BA、B 双方初始手里的牌序列。我们约定,输入的串的长度不超过 30。2J9A7QA6Q6889977

输出描述

输出为 1 行,1 个串,表示 AA 先出牌,最后赢的一方手里的牌序。

输入输出样例

示例

输入

96J5A898QA
6278A7Q973

 

输出

2J9A7QA6Q6889977

Java版

import java.util.*;
// 过程模拟-题型
/* 我的思考过程1、先将A、B两个字符串存入,存入什么容器中不知道!2、如何对 A-B放牌的缓存区 进行存、取,我好像也不太清楚3、怎么判断结束,好像也不清楚
*/
/*根据在草稿纸上,模拟出来的特性,1、A、B的存入取出,先进先出-适合队列2、A-B放牌的缓存区,先进后出-适合用栈3、检查放牌区里面的是否已经存入该牌,用set集合
*/
public class CardGameSimulation {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取玩家 A 和玩家 B 的初始牌串String s_A = scanner.next();String s_B = scanner.next();scanner.close();// 创建队列来存储玩家 A 和玩家 B 的牌,队列具有先进先出的特性Queue<Character> A = new LinkedList<>();Queue<Character> B = new LinkedList<>();// 创建栈来作为出牌的缓存区,栈具有先进后出的特性Stack<Character> storage = new Stack<>();// 创建集合来检查出牌缓存区中是否已经存在某张牌Set<Character> repeated = new HashSet<>();// 将玩家 A 的牌存入队列 Afor (char c : s_A.toCharArray()) {A.add(c);}// 将玩家 B 的牌存入队列 Bfor (char c : s_B.toCharArray()) {B.add(c);}// 标记游戏是否结束boolean game_over = false;// 计时器,记录出牌的轮数int flag = 0;// 只要玩家 A 和玩家 B 都还有牌,并且游戏没有结束,就继续循环while (!A.isEmpty() && !B.isEmpty() && !game_over) {if (flag % 2 == 0) { // 偶数轮,玩家 A 出牌// 从玩家 A 的队列中取出一张牌char c = A.poll();// 检查出牌缓存区中是否已经存在这张牌if (!repeated.contains(c)) {// 如果不存在,将牌放入出牌缓存区和查重集合storage.push(c);repeated.add(c);} else {// 如果存在,将这张牌放回玩家 A 的队列,并从缓存区取出相关牌A.add(c);get_storage(A, storage, repeated, c);continue; // 跳过本次循环的剩余部分,不增加计数器}} else if (flag % 2 == 1) { // 奇数轮,玩家 B 出牌// 从玩家 B 的队列中取出一张牌char c = B.poll();// 检查出牌缓存区中是否已经存在这张牌if (!repeated.contains(c)) {// 如果不存在,将牌放入出牌缓存区和查重集合storage.push(c);repeated.add(c);} else {// 如果存在,将这张牌放回玩家 B 的队列,并从缓存区取出相关牌B.add(c);get_storage(B, storage, repeated, c);continue; // 跳过本次循环的剩余部分,不增加计数器}}flag++;// 如果出牌轮数超过 1000000 次,认为游戏陷入死循环,结束游戏if (flag >= 1000000) {game_over = true;}}// 输出游戏结果if (game_over) {System.out.println(-1);} else if (!A.isEmpty()) { // 玩家 A 胜利,输出玩家 A 的牌while (!A.isEmpty()) {System.out.print(A.poll());}} else if (!B.isEmpty()) { // 玩家 B 胜利,输出玩家 B 的牌while (!B.isEmpty()) {System.out.print(B.poll());}}}// 从栈中取出数据,从集合中删除对应元素,并将数据存入队列public static void get_storage(Queue<Character> in_q, Stack<Character> out_s, Set<Character> se, char c1) {char c;do {// 从栈中取出顶部元素c = out_s.pop();// 从集合中删除该元素se.remove(c);// 将元素存入队列in_q.add(c);} while (c != c1);}
}

C++版

#include <iostream>
#include <queue>
#include <stack>
#include <set>
using namespace std;
// 过程模拟-题型
/* 我的思考过程1、先将A、B两个字符串存入,存入什么容器中不知道!2、如何对 A-B放牌的缓存区 进行存、取,我好像也不太清楚3、怎么判断结束,好像也不清楚
*/
/*根据在草稿纸上,模拟出来的特性,1、A、B的存入取出,先进先出-适合队列2、A-B放牌的缓存区,先进后出-适合用栈3、检查放牌区里面的是否已经存入该牌,用set集合
*/
void get_storage(queue<char>& in_q, stack<char>& out_s, set<char>& se,char c1){// 作用 - 从stack中去数据,删掉set中得内容,并存入queuechar c;do{c = out_s.top(); // 取出out_s.pop();se.erase(c); // 删掉in_q.push(c); // 存入}while(c!=c1);
}int main()
{string s_A;string s_B;cin>>s_A>>s_B;
//    scanf("%s",&s_A);
//    scanf("%s",&s_B);queue<char> A;queue<char> B;stack<char> storage; // 出牌的缓存区set<char> repeated; // 查重// 存入for(char c : s_A) A.push(c);for(char c : s_B) B.push(c);// 无线循环bool game_over = false;int flag = 0; // 设置一个计时器while(!A.empty()&&!B.empty()&&!game_over){if(flag%2==0){ // 偶数时,A出牌// 从A中取出这张牌// 判断 出牌的缓存区中,是否有这张牌// 将这张牌放入 出牌的缓存区中char c = A.front(); // 取A.pop();if(repeated.find(c)==repeated.end()){storage.push(c);repeated.insert(c); // 如果 出牌的缓存区中 无该牌,插入} else { // 创建一个函数,用于存取A.push(c);get_storage(A,storage,repeated,c);continue; // 用continue跳过,模拟题目要求,胜利过后,就不用++flag了。}}else if(flag%2==1){ // 奇数时,B出牌// 出B的时候,与A是同样的方法char c = B.front(); // 取B.pop();if(repeated.find(c)==repeated.end()){storage.push(c);repeated.insert(c); // 如果 出牌的缓存区中 无该牌,插入}  else { // 创建一个函数,用于存取B.push(c);get_storage(B,storage,repeated,c);continue; // 用continue跳过,模拟题目要求,胜利过后,就不用++flag了。}}flag++;if(flag>=1e6){ // 都循环这么多次了,还不结束,那肯定不对劲game_over = true;}}// 输出if(game_over) cout<<-1<<endl;else if(!A.empty()){ // A胜利,遍历Awhile(!A.empty()){char c = A.front();A.pop();cout<<c;}}else if(!B.empty()){ // B胜利,遍历Bwhile(!B.empty()){char c = B.front();B.pop();cout<<c;}}return 0;
}

 

 

 


借鉴博客、视频、网站:

1、蓝桥官网

2、模拟算法 (算法详解+例题)

3、C++算法:模拟


( •̀ ω •́ )✧点击这里,继续学习其他模块吧!

 


http://www.mrgr.cn/news/92435.html

相关文章:

  • Mellanox的LAG全称是什么?网卡的创建机制如何?(Link Aggregation Group 链路聚合组)
  • 在nodejs中使用ElasticSearch(三)通过ES语义检索,实现RAG
  • 本地部署阿里的万象2.1文生视频(Wan2.1-T2V-1.3B)模型
  • 仿真环境下实现场景切换、定位物体和导航行走
  • 指标异动拆解:数据分析师的实战指南
  • Windows 图形显示驱动开发-WDDM 3.2-自动显示切换(七)
  • 如何搭建起成熟的团队知识文档管理系统
  • 15.5 基于 RetrievalQA 的销售话术增强系统实战:构建智能销售大脑
  • AI知识架构之神经网络
  • 销售成交九步思维魔方
  • C语言文件操作深度解析:从基础到实践
  • 文件系统
  • 项目过程管理思维导图
  • 一文了解Java中的虚拟线程新特性
  • 基于大模型的肺纤维化预测及临床方案研究报告
  • 网页制作09-html,css,javascript初认识のhtml如何使用表单
  • 剑指 Offer II 031. 最近最少使用缓存
  • [已解决]dify设置本地模型deepseek报错[Error 111]
  • 自动驾驶之BEVDet
  • Redis分布式缓存面试题