跳到主要内容 模拟算法：核心概念与经典例题实践 | 极客日志
编程语言 java 算法
模拟算法：核心概念与经典例题实践 系统讲解模拟算法的核心概念、特点及解题技巧，强调模块化编程与逻辑梳理。通过单身贵族游戏、日期计算、队列栈应用等多个实例，展示了基础模拟、状态模拟及过程模拟的实现方法。内容包含 Java 与 C++ 代码示例，旨在提升读者的编程逻辑能力与代码调试技巧。
RustyLab 发布于 2026/3/30 更新于 2026/4/13 一、引言
模拟算法 ，简单来说，就是按照题目描述的步骤或规则，一步一步地用代码实现解决问题的过程。就像是你在玩一个游戏，游戏有它自己的规则，而你需要根据这些规则来做出相应的动作以完成特定的目标。
二、模拟算法的特点与技巧
特点
代码量较大
操作步骤多
思路相对复杂
较为复杂的题目出错后难定位错误
技巧
动手前，尽量在电脑或演草纸列好思路
代码中，尽量对代码模块化 ，写成函数 ，类 (Java)/结构体 (C++)
对于一些会重复用到的概念，可以统一转化，方便处理
调试代码时，可分块调试（对代码模块化 的好处）
写代码一定要思路清晰，不要想到啥写啥，按自己提前列好的思路书写
常见题型
基础模拟 (字符串处理、日期处理)，状态模拟，过程模拟等... 其中以基础模拟最常见。
注意事项
模拟这个算法其实非常难，主要是逻辑上的麻烦 ，但正常刷题时我们都不把模拟的逻辑思维理清就直接做，如果这题没有太水 的话，是非常容易错的。
模拟可以与任何算法同时出现，比如模拟与动归 dp、模拟与搜索之类的。
接下来的入门题型 ，就是基础练习。基础与进阶代码量会大一些。但这没啥好担心的 ，这毕竟是算法能力提升的基石 - 敲代码能力。
三、练习
模拟类型是以编程题考察。
提示 ：至少要独立思考 10min，若 20min 后仍无思路在看解析，收获会更大！
入门
单身贵族游戏
问题描述
单身贵族游戏规则：游戏玩法似跳棋，但不能走步，只能跳；棋子只能跳过相邻的棋子（相邻位置上一定要有棋子）到空位上，并且把被跳过的棋子吃掉；棋子可以沿格线横、纵方向跳，但是不能斜跳。
在本题中，给定单身贵族游戏走若干步后的棋盘状态（不用判断是否合理），判断游戏是否已经结束了（即不能再走下去了）。
以下图 (a) 为单身贵族游戏的棋盘，图 (b) 演示了走棋的规则，图 (c) 所示的棋盘状态已经结束了，无法再走棋。
输入格式
输入数据占 7 行，描述了一个单身贵族游戏的棋盘状态。注意第 1、2、6、7 行的数据也是顶格的（在程序处理时，需要还原到棋盘中的位置）。每个位置上为 1 或 0，前者表示有棋子，后者表示没有。
输出格式
测试数据所表示的单身贵族游戏，如果游戏无法进行下去了，输出 yes，否则输出 no。
Java 版
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
int [][] vec = 微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Keycode 信息 查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码 JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化 使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆 Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
new
int
7
7
Scanner
scanner
=
new
Scanner
for
int
i
=
0
7
String
str
=
if
3
for
int
j
=
0
3
2
'0'
else
for
int
j
=
0
7
'0'
boolean
flag
=
true
for
int
i
=
1
6
for
int
j
=
1
6
if
1
if
1
1
1
1
1
1
1
1
false
if
"yes"
else
"no"
#include <iostream>
#include <vector>
using namespace std;
int main () 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' ;
}
}
}
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 ;
}
}
}
}
if (flag) cout<<"yes" <<endl;
else cout<<"no" <<endl;
return 0 ;
}
问题描述
有一个长为 n 的序列 a1,a2.....an 与一个特殊的数 k，ai 小于 k。
当一个序列（元素个数 size≥2）中有一个数 x 会等于其他数的总和 sum % k，即 sum % k==x，则说明此序列为好序列。
求在长度为 n 的序列中有多少连续的子序列为好序列。
输入格式
输入共两行。
第一行包含两个数 n，k，表示序列长和特殊的数。
第二行包含 n 个小于 k 的非负整数 a1,a2,a3,…,an。
输出格式
输出一个数 sum 为好序列个数。
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
int 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);
}
}
#include <iostream>
#include <vector>
using namespace std;
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){
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];
}
}
}
cout<<num<<endl;
return 0 ;
}
问题描述
小浩有一个大小为 N×N 的国际象棋棋盘。
有 N 个主教以之字形的形式放置在棋盘的矩阵上，坐标分别为 (1,1),(2,2),(1,3),(2,4),(1,5),…。
已知主教只能斜向移动且每次可以移动任意距离。
你的任务是找到最少的移动次数，满足对于所有 1≤i≤N，棋盘矩阵上的格子 (i,i) 都被主教占领了。
输入格式
第一行输入一个正整数 T 表示测试数据的组数。
接下来 T 行每行输入一个正整数 N 表示棋盘的大小。
输出格式
对于每组测试数据，输出一个整数表示满足题目要求所需要的最少的移动次数。
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
int t = scanner.nextInt();
while (t > 0 ) {
int l = scanner.nextInt();
if (l <= 2 ) {
System.out.println(0 );
} else if (l == 3 ) {
System.out.println(2 );
} else if (l % 2 == 0 ) {
System.out.println(2 + ((l - 3 ) / 2 ) * 3 + 1 );
} else {
System.out.println(2 + ((l - 3 ) / 2 ) * 3 );
}
t--;
}
scanner.close();
}
}
#include <iostream>
using namespace std;
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 ;
}
题目描述
在电子计算机普及以前，人们经常用一个粗略的方法来验算四则运算是否正确。
比如：248×15=3720
把乘数和被乘数分别逐位求和，如果是多位数再逐位求和，直到是 1 位数。
请你写一个计算机程序，对给定的字符串逐位求和。
输入描述
输入为一个由数字组成的串，表示 n (n<1000) 位数。
输出描述
输出为一位数，表示反复逐位求和的结果。
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
String str = scanner.nextLine();
long num = 0 ;
while (str.length() > 1 ) {
for (int i = 0 ; i < str.length(); ++i) {
num += str.charAt(i) - '0' ;
}
str = String.valueOf(num);
num = 0 ;
}
System.out.println(str);
scanner.close();
}
}
#include <iostream>
#define ll long long
using namespace std;
int main () 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 ;
}
问题描述
最近 Awell 的运气特别好，他在路边摊买彩票，居然中了大奖。秉着见者有份的原则，他准备请咱们学校 ACM-ICPC 训练基地的全体队员逛商场。
赶巧交大旁边有一家商场新店开张，正在进行打折促销活动。于是，咱们所有队员都在商场中大肆购买之后，在收银台前排起了长队。
话说回来，这家商场的打折方式有些奇怪：他们从在收银台前付账的所有 n 位顾客中，所有的第 m 的倍数名顾客享受七五折优惠，其余顾客只能享受九五折。
为了方便付账，Awell 拜托老板将付账者的姓名和付款金额打印出来，作为参考。你需要注意的是，在收银台前长长的队伍中，有的可不止是 ACM 队员，同样，还有很多交大的同学慕名前来消费，为了区分他们，我们规定，所有 ACM 队员必须在姓名前加上前缀 ACM。
现在，请机智的你为 Awell 编写一个小程序，算一算他总共需要花费多少钱呢？
输入格式
输入数据包含不超过 5 组，每组第一行有两个整数 n,m(1≤n,m≤1000)，分别代表着在收银台前队伍的全部人数，以及商家将会选择每第 m 位顾客打 7.5 折。
接下来有 n 行，每行将会输入消费者的姓名（长度不超过 20 个字符），以及他们各自消费的金额（消费金额不超过 1000）。
输出格式
每组数据输出一行，每行一个实数，表示 Awell 总共需要花费多少。
你应该注意的是，老板只收取'角'作为最小单位，而且他是一个锱铢必较的人，所以，如果你所付金额中存在小于 0.1 元的部分，那就至少要付 0.1 元给他。
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int m = scanner.nextInt();
String str;
double all_money = 0 ;
double money;
for (int i = 0 ; i < n; ++i) {
str = scanner.next();
money = scanner.nextDouble();
str = str + "000" ;
str = str.substring(0 , 3 );
if ((i + 1 ) % m == 0 && str.equals("ACM" )) {
all_money += money * 0.75 ;
} else if (str.equals("ACM" )) {
all_money += money * 0.95 ;
}
}
System.out.printf("%.1f\n" , all_money + 0.049999 );
}
scanner.close();
}
}
#include <iostream>
using namespace std;
int main () int n,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 ;
}
基础
题目描述
有 N 个瓶子，编号 1 ~ N，放在架子上。
比如有 5 个瓶子：2 1 3 5 4
要求每次拿起 2 个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：1 2 3 4 5
对于这么简单的情况，显然，至少需要交换 2 次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入描述
输入格式为两行：
第一行：一个正整数 N (N<10^4)，表示瓶子的数目
第二行：N 个正整数，用空格分开，表示瓶子目前的排列情况。
输出描述
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
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;
if (vec[j] != i) {
while (vec[j] != i) {
j++;
}
int temp = vec[j];
vec[j] = vec[i];
vec[i] = temp;
ans++;
}
}
System.out.println(ans);
scanner.close();
}
}
#include <iostream>
#include <vector>
using namespace std;
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 ;
}
题目描述
从 X 星截获一份电码，是一些数字，如下：
13
1113
3113
132113
1113122113
⋯⋯
YY 博士经彻夜研究，发现了规律：
第一行的数字随便是什么，以后每一行都是对上一行"读出来"
比如第 2 行，是对第 1 行的描述，意思是：1 个 1，1 个 3，所以是：1113
第 3 行，意思是：3 个 1,1 个 3，所以是：3113
请你编写一个程序，可以从初始数字开始，连续进行这样的变换。
输入描述
第一行输入一个数字组成的串，不超过 100 位。
第二行，一个数字 n，表示需要你连续变换多少次，n 不超过 20。
输出描述
输出一个串，表示最后一次变换完的结果。
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
String str1 = scanner.next();
int t = scanner.nextInt();
scanner.close();
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.append(num).append(c);
num = 1 ;
c = str1.charAt(i);
} else {
num++;
}
}
str2.append(num).append(c);
str1 = str2.toString();
}
System.out.println(str1);
}
}
#include <iostream>
using namespace std;
int main () int t;
string str1;
cin>>str1>>t;
while (t--){
int num = 1 ;
char c = str1[0 ];
string str2 = "" ;
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;
}
cout<<str1<<endl;
return 0 ;
}
题目描述
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。
输入描述
输入的第一行包含两个整数 n,m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。其中，2≤n,m≤1000，1≤k≤1000。
输出描述
输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
import java.util.Scanner;
public class GrassGrowthSimulation {
static int [][] a = new int [1005 ][1005 ];
static int [][] b = new int [1005 ][1005 ];
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
scanner.nextLine();
for (int i = 0 ; i < n; i++) {
String str = scanner.nextLine();
for (int j = 0 ; j < m; j++) {
if (str.charAt(j) == '.' ) a[i][j] = 0 ;
else a[i][j] = 1 ;
}
}
int k = scanner.nextInt();
scanner.close();
while (k-- > 0 ) {
dfs(n, m);
}
for (int i = 0 ; i < n; i++) {
for (int j = 0 ; j < m; j++) {
if (a[i][j] == 0 ) System.out.print("." );
else System.out.print("g" );
}
System.out.println();
}
}
public static void dfs (int n, int m) {
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 ) {
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 ;
}
}
}
}
}
#include <iostream>
using namespace std;
int a[1005 ][1005 ],b[1005 ][1005 ];
void dfs (int n, int m) 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 ){
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;
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 ;
}
日期系列
问题描述
小蓝每周六、周日都晨跑，每月的 1、11、21、31 日也晨跑。其它时间不晨跑。
已知 2022 年 1 月 1 日是周六，请问小蓝整个 2022 年晨跑多少天？
public class Main {
public static void main (String[] args) {
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 < monthDay.length; 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++;
}
}
}
System.out.println(day);
}
}
#include <iostream>
using namespace std;
int main () 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 时跑 5 千米，否则只跑 1 千米。注意日期中出现 1 不仅指年月日也指星期。
请问按照小蓝的计划，2023 年小蓝总共会跑步锻炼多少千米？例如，5 月 11 日、11 月 13 日、11 月 5 日、4 月 3 日 (星期一) 小蓝会跑 5 千米，而 5 月 23 日小蓝会跑 1 千米。
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
int 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++) {
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++;
}
}
}
System.out.println(s);
}
}
#include <iostream>
using namespace std;
int main () int s = 0 ;
int monthDay[] = {31 ,28 ,31 ,30 ,31 ,30 ,31 ,31 ,30 ,31 ,30 ,31 };
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 ;
}
问题描述
Cron 表达式在定时任务中经常被使用，在这里我们用了一种简化后的版本 SimpleCron 表达式：SimpleCron 表达式是一个具有时间含义的字符串，字符串以 4 个空格隔开，分为 5 个域，格式为 XXXXXXXXXX，其中 XX 是一个域的占位符。5 个域从左至右依次为秒 (0−59)、分钟 (0−59)、小时 (0−23)、日期 (1−31)、月份 (1−12)。
特殊字符 * 表示所有可能的值。特殊字符 , 表示列出枚举值。特殊字符 − 表示范围。
现在给出你一个合法的 SimpleCron 表达式，其中用到的所有数字均没有前导零。请问在 2023 一整年当中，使用了这个表达式的定时任务总计会执行多少次？
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 == '*' ) {
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 )) {
num2 += generateNum(D, monthDay[i - 1 ]).size() * num1;
}
System.out.println(num2);
scanner.close();
}
}
#include "bits/stdc++.h"
using namespace std;
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 )){
num2+= generateNum (D,monthDay[i-1 ]).size ()*num1;
}
cout<<num2<<endl;
return 0 ;
}
进阶
题目描述
某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。
主持人拿出 N 张卡片（上面写着 1⋯N 的数字），打乱顺序，排成一个圆圈。
你可以从任意一张卡片开始顺时针数数：1,2,3 ⋯⋯
如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。
直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。
本题的目标：已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票。
import java.util.Scanner;
import java.util.Arrays;
public class CardGame {
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
int n = scanner.nextInt();
int [] vec = new int [n];
for (int i = 0 ; i < n; i++) {
vec[i] = scanner.nextInt();
}
int flag = 0 ;
for (int i = 0 ; i < n; i++) {
boolean [] used = new boolean [n];
int cur = 0 ;
int index = i;
int count = 1 ;
int num = 0 ;
while (true ) {
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 = Math.max(num, flag);
}
System.out.println(flag);
scanner.close();
}
}
#include <iostream>
#include <vector>
using namespace std;
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 ) ;
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 ;
}
问题描述
小蓝发现了一个神奇的闹钟，从纪元时间（1970 年 1 月 1 日 00:00:00）开始，每经过 x 分钟，这个闹钟便会触发一次闹铃。
对于给出的任意一个格式为 yyyy-MM-ddHH:mm:ss 的时间，小蓝想要知道在这个时间点之前 (包含这个时间点) 的最近的一次闹铃时间是哪个时间？
输入格式
输入的第一行包含一个整数 T，表示每次输入包含 T 组数据。
接下来依次描述 T 组数据。
每组数据一行，包含一个时间和一个整数 x，其中 x 表示闹铃时间间隔（单位为分钟）。
import java.util.Scanner;
public class TimeCalculation {
public static long generate (int year, int month, int day, int hour, int minute, int second, int sub) {
int totalDays = 0 ;
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);
}
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();
}
}
#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) {
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){
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 ){
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 ;
}
综合应用
题目描述
有一种叫做"拉马车"的游戏，规则很简单，却很吸引小朋友。
假设参加游戏的小朋友是 A 和 B，游戏开始的时候，他们得到的随机的纸牌序列如下：
A 方：[K,8,X,K,A,2,A,9,5,A]
B 方：[2,7,K,5,J,5,Q,6,K,4]
其中的 X 表示 "10"，我们忽略了纸牌的花色。
从 A 方开始，A、B 双方轮流出牌。
当轮到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。
当轮到 B 出牌时，他的牌 K 与桌上的纸牌序列中的 K 相同，则把包括 K 在内的以及两个 K 之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。
赢牌的一方继续出牌。
当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。
本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出 -1。
import java.util.*;
public class CardGameSimulation {
public static void main (String[] args) {
Scanner scanner = new Scanner (System.in);
String s_A = scanner.next();
String s_B = scanner.next();
scanner.close();
Queue<Character> A = new LinkedList <>();
Queue<Character> B = new LinkedList <>();
Stack<Character> storage = new Stack <>();
Set<Character> repeated = new HashSet <>();
for (char c : s_A.toCharArray()) A.add(c);
for (char c : s_B.toCharArray()) B.add(c);
boolean game_over = false ;
int flag = 0 ;
while (!A.isEmpty() && !B.isEmpty() && !game_over) {
if (flag % 2 == 0 ) {
char c = A.poll();
if (!repeated.contains(c)) {
storage.push(c);
repeated.add(c);
} else {
A.add(c);
get_storage(A, storage, repeated, c);
continue ;
}
} else if (flag % 2 == 1 ) {
char c = B.poll();
if (!repeated.contains(c)) {
storage.push(c);
repeated.add(c);
} else {
B.add(c);
get_storage(B, storage, repeated, c);
continue ;
}
}
flag++;
if (flag >= 1000000 ) game_over = true ;
}
if (game_over) System.out.println(-1 );
else if (!A.isEmpty()) {
while (!A.isEmpty()) System.out.print(A.poll());
} else if (!B.isEmpty()) {
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);
}
}
#include <iostream>
#include <queue>
#include <stack>
#include <set>
using namespace std;
void get_storage (queue<char >& in_q, stack<char >& out_s, set<char >& se,char c1) char c;
do {
c = out_s.top ();
out_s.pop ();
se.erase (c);
in_q.push (c);
}while (c!=c1);
}
int main () 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 ){
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 ;
}
}else if (flag%2 ==1 ){
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 ;
}
}
flag++;
if (flag>=1e6 ) game_over = true ;
}
if (game_over) cout<<-1 <<endl;
else if (!A.empty ()){
while (!A.empty ()){ char c = A.front (); A.pop (); cout<<c; }
}else if (!B.empty ()){
while (!B.empty ()){ char c = A.front (); A.pop (); cout<<c; }
}
return 0 ;
}
