一、引言
模拟算法，简单来说，就是按照题目描述的步骤或规则，一步一步地用代码实现解决问题的过程。就像是你在玩一个游戏，游戏有它自己的规则，而你需要根据这些规则来做出相应的动作以完成特定的目标。
二、模拟算法的特点与技巧
特点
- 代码量较大
- 操作步骤多
- 思路相对复杂
- 较为复杂的题目出错后难定位错误
技巧
- 动手前，尽量在电脑或演草纸列好思路
- 代码中，尽量对代码模块化，写成函数，类 (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) {
// 定义一个 7x7 的二维数组，初始化为 0
int[][] 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 {
System.out.println("no");
}
}
}
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';
}
}
}
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 为好序列个数。
Java 版
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);
}
}
C++ 版
#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 表示棋盘的大小。
输出格式
对于每组测试数据，输出一个整数表示满足题目要求所需要的最少的移动次数。
Java 版
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();
}
}
C++ 版
#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) 位数。
输出描述
输出为一位数，表示反复逐位求和的结果。
Java 版
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();
}
}
C++ 版
#include <iostream>
#define ll long long
using namespace std;
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;
}
- Goshopping
问题描述
最近 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 元给他。
Java 版
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();
}
}
C++ 版
#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 个正整数，用空格分开，表示瓶子目前的排列情况。
输出描述
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
Java 版
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();
}
}
C++ 版
#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。
输出描述
输出一个串，表示最后一次变换完的结果。
Java 版
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);
}
}
C++ 版
#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，表示长了草。
Java 版
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;
}
}
}
}
}
C++ 版
#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 年晨跑多少天？
Java 版
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);
}
}
C++ 版
#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 千米。
Java 版
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);
}
}
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};
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 一整年当中，使用了这个表达式的定时任务总计会执行多少次？
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 == '*') {
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();
}
}
C++ 版
#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 ⋯⋯ 如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。 直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。 本题的目标：已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票。
Java 版
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();
}
}
C++ 版
#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 表示闹铃时间间隔（单位为分钟）。
Java 版
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();
}
}
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){
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。
Java 版
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);
}
}
C++ 版
#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() {
string s_A; string s_B;
cin>>s_A>>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){
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;
}
