# 模拟

在算法竞赛中,"模拟" 是指通过编写程序来模拟现实中的某个过程或问题。通常情况下,参赛者需要根据题目要求,利用编程语言实现一个模拟器,然后使用这个模拟器来模拟特定的场景或操作。

模拟题目可以涉及各种不同的领域和问题,如模拟物理系统、模拟游戏规则、模拟网络通信等。具体而言,参赛者需要根据题目描述和输入数据,在程序中模拟所需的场景和操作,并输出符合题目要求的结果。

下面举例几道题自己体会

# 题目:乒乓球

华华和朋友打乒乓球, 得到了每一球的输赢记录: 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;
}