# 模拟
在算法竞赛中,"模拟" 是指通过编写程序来模拟现实中的某个过程或问题。通常情况下,参赛者需要根据题目要求,利用编程语言实现一个模拟器,然后使用这个模拟器来模拟特定的场景或操作。
模拟题目可以涉及各种不同的领域和问题,如模拟物理系统、模拟游戏规则、模拟网络通信等。具体而言,参赛者需要根据题目描述和输入数据,在程序中模拟所需的场景和操作,并输出符合题目要求的结果。
下面举例几道题自己体会
# 题目:乒乓球
华华和朋友打乒乓球, 得到了每一球的输赢记录: w 表示华华得一分, L 表示对手得一分, E 表示比赛信息结束。一局比赛刚开始时比分为 0 : 0 。每一局中达到 11 分或者 21 分( 赛制不同) , 且领先对方 2 分或以上的选手可以赢得
这一局。现在要求输出在 1 1 分制和 21 分制两种情况下的每一局得分。输人数据每行至多有 25 个字母, 最多有 25 行。
# 分析:
根据题意, 只需要对读入的内容进行统计即可。使用数组 a 来记录下从最开始到结束的得分情况, 如果是华华赢了就记为 1 , 反之记为 0 。读到 E 的时候直接就不再继续读人, 而读到换行符时也直接忽略。同时要记录他们一共打了几球( 就是 n)
然后分别对两种赛制进行计算。首先计分板上双方都是 0 。如果华华赢了,w 就增加 1 ,
否则 l 就增加 1 。如果发现计分板上得分高的一方达到了赛制要求的球数, 而且分差也足够,就将计分板的得分输出, 同时计分板清零开始下一局。到最后还要输出正在进行中的比赛的得分。
# 代码
// | |
// Created by Doubeer on 2024/2/1. | |
// 乒乓球 | |
#include <iostream> | |
#include <cmath> | |
using namespace std; | |
int f[2] = {11,22};// 两种赛制 | |
int a[25 * 2500 + 10],n = 0; | |
int main(){ | |
char temp; | |
while(1){ | |
cin >> temp; | |
if(temp == 'E') break; | |
else if(temp = 'W') a[n++] = 1;// 华华赢 | |
else if(temp = 'L') a[n++] = 0;// 华华输 | |
} | |
for(int k = 0;k < 2;k++){// 两种赛制循环 | |
int w = 0, l = 0; | |
for(int i = 0;i < n;i++){ | |
w += a[i]; | |
l += l - a[i]; | |
if((max(w,l) >= f[k]) && abs(w - l) >= 2){// 获胜者超过对应分数且超过对手两分 | |
cout << w << ":" << l << endl; | |
w = l = 0; | |
} | |
} | |
} | |
} |
# 题目:扫雷
给出一个 n × m 的网格, 有些格子埋有地雷。求问这个棋盘上每个没有地雷的格子周围( 上、下、左、右和斜对角) 的地雷数。
输人第一行的两个整数 n 和 m, 表示网格的行数和列数, 接下来的 n 行, 每行 m 个字符, 描述了雷区中的地雷分布情况。字符 * 表示相应格子是地雷格, 字符? 表示相应格子是非地雷格。m 和 n 不超过 100.
输出包含 n 行, 每行 m 个字符, 描述整个雷区。用 * 表示地雷格, 用周围的地雷个数表示非地雷格。
# 分析
分析: 根据题意, 对于每个非地雷的格子, 只需要统计其上、下、左、右、左上、右上、左下、右下 8 个方向的格子中地雷的数量。如果需要统计的格子的坐标是(x,y), 那么它左上角的坐标是 (x-1,y-1 ) 。
需要注意边界的判断。
# 代码
// 扫雷 | |
#include <iostream> | |
using namespace std; | |
const int dx[] = {1,1,1,0,0,-1,-1,-1}; | |
const int dy[] = {-1,0,1,-1,1,-1,0,1}; | |
const int maxn = 105; | |
char g[maxn][maxn]; | |
int n,m; | |
int main(){ | |
cin >> n >> m; | |
for(int i = 1;i <= n;i++) | |
for(int j = 1; j <= m; j++) | |
cin >> g[i][j]; | |
for(int i = 1; i <= n; i++){ | |
for(int j = 1; j <= m; j++) | |
if(g[i][j] != '*'){ | |
int cnt = 0; | |
for(int k = 0; k < 8; k++) | |
if(g[i + dx[k]][j + dy[k]] == '*') cnt++;// 八个方向 | |
cout << cnt; | |
} | |
else cout << "*"; | |
cout << endl; | |
} | |
return 0; | |
} |
# 题目:玩具谜题
n (n < 100000 ) 名同学依次逆时针方向围成一个圈, 有些同学面向圈内, 有些面向圈外。第一个同学手里有礼物。从这名同学开始进行 m( m< 10000 ) 次传递。拥有礼物的同学将礼物传递给左手 / 右手边的第 s(s<n ) 个人。已知每名同学的姓名( 长度不超过 10 的字符串) 和朝向( 0 表示朝圈内, 1 表示朝圈外) , 以及每次传递的方向( 0 表示往这名同学的左边, 1 表示往右边) 和传过的同学人数, 求最后礼物在谁手上,输出姓名
# 分析
类似击鼓传花,面朝的两种方向和左传和右传两种传递方式一共四种情况。
# 代码
// 击鼓传花 | |
#include <iostream> | |
#include <string> | |
using namespace std; | |
const int MAXN = 1e6 + 5; | |
struct node{// 用结构体存储同学的名字和方向 | |
int head; | |
string name; | |
}a[MAXN]; | |
int n,m,x,y; | |
int main(){ | |
cin >> n >> m; | |
for(int i = 0;i < n; i++) | |
cin >> a[i].head >> a[i].name; | |
int now = 0; | |
for(int i; i <= m; i++){ | |
cin >> x >> y;//x 向左向右传递,y 传递几个人 | |
if(a[now].head == 0 && x == 0) | |
now = (now + n - y) % n; | |
else if( a[now].head == 0 && x == 1) | |
now = (now + y) % n; | |
else if(a[now].head == 1 && x == 0) | |
now = (now + y) % n; | |
else if(a[now].head == 1 && x == 1) | |
now = (now + n - y) % n; | |
} | |
cout << a[now].name << endl; | |
return 0; | |
} |
# 高精度运算
数据类型 | 大小(字节) | 最小值 | 最大值 |
---|---|---|---|
bool | 1 | false | true |
char | 1 | -128 | 127 |
unsigned char | 1 | 0 | 255 |
short | 2 | -32,768 | 32,767 |
unsigned short | 2 | 0 | 65,535 |
int | 4 | -2,147,483,648 | 2,147,483,647 |
unsigned int | 4 | 0 | 4,294,967,295 |
long | 4/8 | -2,147,483,648 | 2,147,483,647 |
unsigned long | 4/8 | 0 | 4,294,967,295 |
long long | 8 | -9,223,372,036,854,775,808 | 9,223,372,036,854,775,807 |
unsigned long long | 8 | 0 | 18,446,744,073,709,551,615 |
float | 4 | 1.17549e-38 | 3.40282e+38 |
double | 8 | 2.22507e-308 | 1.79769e+308 |
long double | 10/16 | 3.3621e-4932 | 1.18973e+4932 |
数据类型的范围是有限的,想要存储更多的位数,可以用数组来模拟
# 题目:竖式问题
分别在两行内输人两个 5 位以内的十进制非负整数, 求它们的和。
# 分析
用数组来模拟非常长的整数,需要注意数字串输入数组时,下标 0 的是对应的数字的最大位数
# 代码
//A+B | |
#include <iostream> | |
#include <string> | |
#include <algorithm> | |
#define maxn 520 | |
using namespace std; | |
int a[maxn],b[maxn],c[maxn]; | |
int mian(){ | |
string A,B; | |
cin >> A >> B; | |
int len = max(A.length(),B.length()); | |
for(int i = A.length() - 1,j = 1; i >= 0; i--,j++) | |
a[j] = A[i] - '0'; | |
for(int i = B.length() - 1,j = 1; i >= 0; i--,j++) | |
b[j] = B[i] - '0'; | |
for(int i = 1; i <= len; i++){ | |
c[i] += a[i] + b[i]; | |
c[i + 1] = c[i] / 10;// 模拟进位 | |
c[i] %= 10; | |
} | |
if(c[len + 1])// 最后进位可能导致位数增加 | |
len++; | |
for(int i = len; i >= 1; i--) | |
cout << c[i]; | |
} |
# 题目:竖式乘法
分别在两行内输入两个 2000 位以内的十进制非负整数,求它们的积。
# 分析
假设两个乘数用数组 a,b 存储,它们每一位的乘积的结果存在数组 c 中。根据乘法的规则 a 的第 i 位和 b 的第 j 位的乘积会落在到 c 的第 i+j-1 位上,再对 c 中大于 10 的书进位
# 代码
//A*B | |
#include <iostream> | |
#include <string> | |
#include <algorithm> | |
#define maxn 5010 | |
using namespace std; | |
int a[maxn],b[maxn],c[maxn]; | |
int main(){ | |
string A,B; | |
cin >> A >> B; | |
int lena = A.length(); | |
int lenb = B.length(); | |
for(int i = lena - 1; i >= 0; i--) a[lena - i] = A[i] - '0'; | |
for(int i = lenb - 1; i >= 0; i--) b[lenb - i] = B[i] - '0'; | |
for(int i = 1; i <= lena;i++) | |
for(int j = 1;j <= lenb;j++) | |
c[i + j - 1] += a[i] * b[j];// 对于 a 中的第 i 位和 b 中的第 j 位,将它们的乘积加到 c 的第 i+j-1 位上 | |
int len = lena + lenb; | |
for(int i = 1; i <= len; i++){// 处理进位。从低位向高位遍历 c 数组,如果某一位的值大于等于 10,就向高位进位 | |
c[i + 1] += c[i] / 10; | |
c[i] %= 10; | |
} | |
for(; !c[len];)// 找到结果的最高位。 | |
len--; | |
for(int i = max(1,len); i >= 1; i--)// 从最高位开始遍历 c 数组,直到找到第一个非零的位为止。 | |
cout << c[i]; | |
} |
# 题目:阶乘之和
用高精度计算 S = 1!+2!+3!+.....+n!
# 分析
相当于把上述两道题结合一下,重写加法和乘法
# 代码
#include <iostream> | |
#include <vector> | |
using namespace std; | |
// 大整数相乘 | |
vector<int> multiply(vector<int>& num, int factor) { | |
vector<int> result; | |
int carry = 0; | |
for (int i = 0; i < num.size(); i++) { | |
int product = num[i] * factor + carry; | |
result.push_back(product % 10); | |
carry = product / 10; | |
} | |
while (carry > 0) { | |
result.push_back(carry % 10); | |
carry /= 10; | |
} | |
return result; | |
} | |
// 大整数相加 | |
vector<int> add(vector<int>& num1, vector<int>& num2) { | |
vector<int> result; | |
int carry = 0; | |
int i = 0; | |
while (i < num1.size() || i < num2.size() || carry > 0) { | |
int sum = carry; | |
if (i < num1.size()) | |
sum += num1[i]; | |
if (i < num2.size()) | |
sum += num2[i]; | |
result.push_back(sum % 10); | |
carry = sum / 10; | |
i++; | |
} | |
return result; | |
} | |
// 计算阶乘之和 | |
vector<int> calculateFactorialSum(int n) { | |
vector<int> factorial = {1}; // 初始化为 1 | |
vector<int> sum = {0}; // 初始化为 0 | |
for (int i = 1; i <= n; i++) { | |
factorial = multiply(factorial, i); | |
sum = add(sum, factorial); | |
} | |
return sum; | |
} | |
// 输出大整数 | |
void printBigInteger(vector<int>& num) { | |
for (int i = num.size() - 1; i >= 0; i--) | |
cout << num[i]; | |
cout << endl; | |
} | |
int main() { | |
int n; | |
cin >> n; | |
vector<int> result = calculateFactorialSum(n); | |
printBigInteger(result); | |
return 0; | |
} |