洛谷官方题单——模拟与高精度题解

模拟是指的是按照题目给的要求一步一步的考虑各种条件，不需要进行任何花里胡哨的其他操作就可以做出来的题，但是这些题有一个很大的特点：代码量很大且边界条件多，因此在WA了之后查找自己错误的地方会比较麻烦。

而高精度则是我们模拟数字的加减乘除。由于在C/C++等某些编程语言中，在语言设计的时候都对数据类型进行了大小范围限制（如int的范围时-2^31到2^31-1），而有的时候我们要计算的部分超过了这些范围甚至达到了惊人的100位以上的时候，我们就要使用高精度来进行计算。

当然，在一般的比赛当中，可以采用python等自带大数的语言，或者我们也可以将高精度的模板打印下来，需要使用的时候直接誊抄即可，但是一定要对过程有一定的理解。

题目10和题目11十分繁琐，建议多读几次题，我代码的变量在这两道题相当繁琐（为了可读性）。

题目0: 乒乓球

按照题目条件模拟即可，但是需要注意以下的情况：

1. 胜利的条件是一方优先达到11分且双方差值大于等于2，否则应当继续，且由于存在差值大于2，因此无法使用取模来进行归0；
2. 由于分部分输出，因此需要先把后续的存起来，而前面的直接输出即可；
3. 题目中的描述“其中EE表示比赛信息结束，程序应该忽略E之后的所有内容。”说明E可能在文件中间，切勿使用EOF判断；
4. 由于使用的是getchar()，因此还需要额外判断我们的换行符。

#pragma warning(disable:4996)
#include<stdio.h>
#include<math.h>
int ans_21[3000][2];
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    char temp;
    int w_11 = 0, l_11 = 0, w_21 = 0, l_21 = 0, pos = 0;
    temp = getchar();
    while (temp != 'E') {
        if (temp == '\n') {
            temp = getchar();
            continue;
        } 
        if (temp == 'W')  w_11++, w_21++;
        else if (temp == 'L') l_11++, l_21++;
        if (w_11 >= 11 || l_11 >= 11) {
            if (abs(w_11 - l_11) > 1) {
                printf("%d:%d\n", w_11, l_11);
                w_11 = l_11 = 0;
            }
        }
        if (w_21 >= 21 || l_21 >= 21) {
            if (abs(w_21 - l_21) > 1) {
                ans_21[pos][0] = w_21;
                ans_21[pos++][1] = l_21;
                w_21 = l_21 = 0;
            }
        }
        temp = getchar();
    }
    printf("%d:%d\n\n", w_11, l_11);
    for (int i = 0; i < pos; i++)printf("%d:%d\n", ans_21[i][0], ans_21[i][1]);
    printf("%d:%d\n", w_21, l_21);
    return 0;
}

题目1: 扫雷

这也是一到模拟题，只需要按照其所给的方法直接计算就行了，但是我们从这道题可以学习到如何进行方向的移动和边界的处理，详见代码。

#include<stdio.h>
char map[105][105];
int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    getchar();
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= m + 1; j++)
            map[i][j] = getchar();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int cnt = 0;
            if (map[i][j] == '?') {
                for (int k = 0; k < 8; k++) {
                    int temp_x = i + dx[k], temp_y = j + dy[k];
                    if (temp_x >= 1 && temp_x <= n && temp_y >= 1 && temp_y <= m)
                        if (map[temp_x][temp_y] == '*') cnt++;
                }
            }
            if (map[i][j] == '?') map[i][j] = cnt + '0';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printf("%c", map[i][j]);
        printf("\n");
    }
    return 0;
}

题目2: 玩具谜题

读入数据然后按照其要求来进行游戏就行了，这里由于是一个循环（或者一个圈），所以采用取模来进行模拟n-1到0的过程。

#include<stdio.h>
#define MAXN 100050
typedef struct node{
    int head;
    char name[100];
}node;
node memo[MAXN];
int main(){
    int n, m, x, y;
    scanf("%d%d",&n,&m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &memo[i].head);
        scanf(" %s", memo[i].name);
    }
    int now = 0;
    for (int i = 1; i <= m; i++){
        scanf("%d%d", &x, &y);
        if (memo[now].head == 0 && x == 0) now = (now + n - y) % n;
        else if (memo[now].head == 0 && x == 1) now = (now + y) % n;
        else if (memo[now].head == 1 && x == 0) now = (now + y) % n;
        else if (memo[now].head == 1 && x == 1) now = (now + n - y) % n;
    }
    printf("%s", memo[now].name);
    return 0;
}

题目3和题目4：A+B,A*B

这两道题这里略过，洛谷的题解有很多的相关模板建议各位直接CV并添加到自己的模板当中。

题目5：阶乘之和

略过，前面循环那一节有。

题目6：魔法少女小Scarlet

就是矩阵的某一个“环”的旋转问题，首先就是要生成这个举证，然后重点是需要中间额外加一个数组来保存原始矩阵，同时需要构造从原来的地图到中间数组的映射，然后再从中间数组到期望数组的映射。
当然你也可以只使用一个中间变量，然后通过2r+1为循环界限，然后直接一次性旋转四个元素，这样可以节省很大一部分空间。

#pragma warning(disable:4996)
#include<stdio.h>
int map[505][505], media[505][505];
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    int m, n, x, y, z, r;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) map[i][j] = (i - 1) * n + j;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d%d", &x, &y, &r, &z);
        int begin_x = x - r, begin_y = y - r, temp_r = 2 * r + 1;
        if (z) {
            for (int i = 1; i <= temp_r; i++)
                for (int j = 1; j <= temp_r; j++)
                    media[i][j] = map[begin_x + i - 1][begin_y + j - 1];
            for (int i = 1; i <= temp_r; i++)
                for (int j = 1; j <= temp_r; j++) 
                    map[i + begin_x - 1][j + begin_y - 1] = media[j][temp_r - i + 1];
        }
        else {
            for (int i = 1; i <= temp_r; i++)
                for (int j = 1; j <= temp_r; j++) 
                    media[i][j] = map[begin_x + i - 1][begin_y + j - 1];
            for (int i = 1; i <= temp_r; i++)
                for (int j = 1; j <= temp_r; j++) 
                    map[i + begin_x - 1][j + begin_y - 1] = media[temp_r - j + 1][i];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) printf("%d ", map[i][j]);
        printf("\n");
    }
    return 0;
}

题目7：生活大爆炸版石头剪刀布

简单的石头剪刀布题，提前打表，且由于是规律出拳，因此需要采用取模来模拟这个循环。

#include<cstdio>
int ans[5][5] = { {0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0} };
int memoa[250];
int memob[250];

int main() {
    int N, NA, NB;
    int Aans = 0, Bans = 0;
    scanf("%d%d%d", &N, &NA, &NB);
    for (int i = 0; i < NA; i++) scanf("%d", &memoa[i]);
    for (int i = 0; i < NB; i++) scanf("%d", &memob[i]);
    for (int i = 0; i < N; i++) {
        Aans += ans[memoa[i % NA]][memob[i % NB]];
        Bans += ans[memob[i % NB]][memoa[i % NA]];
    }
    printf("%d %d", Aans, Bans);
    return 0;
}

题目8：两只塔姆沃斯牛

采用beacon_cwk大佬的特征值做法，若存在两次特征值相同，则说明存在某个循环导致他们永远不可能相遇，代码如下。

#pragma warning(disable:4996)
#include<stdio.h>
bool eigen_value[200000];
char map[15][15];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
bool farmercheck(int farmer_x, int farmer_y, int farmer_state) {
    return farmer_x + dx[farmer_state] < 0 || farmer_x + dx[farmer_state] >= 10 || farmer_y + dy[farmer_state] < 0 || farmer_y + dy[farmer_state] >= 10 || map[farmer_x + dx[farmer_state]][farmer_y + dy[farmer_state]] == '*';
}
bool cowcheck(int cow_x, int cow_y, int cow_state) {
    return cow_x + dx[cow_state] < 0 || cow_x + dx[cow_state] >= 10 || cow_y + dy[cow_state] < 0 || cow_y + dy[cow_state] >= 10 || map[cow_x + dx[cow_state]][cow_y + dy[cow_state]] == '*';
}
int main(){
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    int cow_x, cow_y, cow_state = 0, farmer_x, farmer_y, farmer_state = 0, now_eigen, step = 0;
    for (int i = 0; i < 10; i++) scanf("%s", map[i]);
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++){
            if (map[i][j] == 'F') farmer_x = i, farmer_y = j;
            if (map[i][j] == 'C') cow_x = i, cow_y = j;
        }
    while (1){
        if (farmer_x == cow_x && farmer_y == cow_y)
            return 0 * printf("%d", step);
        now_eigen = farmer_x + farmer_y * 10 + cow_x * 100 + cow_y * 1000 + farmer_state * 10000 + cow_state * 40000;
        if (eigen_value[now_eigen]) return 0 * printf("0");
        eigen_value[now_eigen] = true;
        if (farmercheck(farmer_x, farmer_y, farmer_state))
            farmer_state = (farmer_state + 1) % 4;
        else farmer_x = farmer_x + dx[farmer_state], farmer_y = farmer_y + dy[farmer_state];
        if (cowcheck(cow_x, cow_y, cow_state))
            cow_state = (cow_state + 1) % 4;
        else cow_x = cow_x + dx[cow_state], cow_y = cow_y + dy[cow_state];
        step++;
    }
}

题目9：多项式输出

这道题我们只需要解决以下条件：系数是不是0，是不是第一项，系数正负，系数正负1，指数为1的时候。于是就可以得到我们的代码啦。

#include<stdio.h>
#include<math.h>
int main() {
    int n;
    scanf("%d", &n);
    for (int i = n; i >= 0; i--) {
        int poly;
        scanf("%d", &poly);
        if (poly) {
            if (i != n && poly > 0)
                printf("+");
            if (abs(poly) > 1 || i == 0)
                printf("%d", poly);
            if (poly == -1 && i)
                printf("-");
            if (i > 1)
                printf("x^%d", i);
            if (i == 1)
                printf("x");
        }
    }
    return 0;
}

题目10：字符串展开

先提前写判断字母和数字的接口，因为输入只有小写所以不需要写大写的判断；然后根据输入的系数来确定输出什么就可以了，注意减号在最后的时候的边界条件。

#pragma warning(disable:4996)
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
int p1, p2, p3;
bool isNumber(char n) { return ((n >= '0') && (n <= '9')); }
bool isAlpha(char n) { return ((n >= 'a') && (n <= 'z')); }
bool work_check(char start, char ending) {
    return (start >= ending || (isNumber(start) && isAlpha(ending)) || (isNumber(ending) && isAlpha(ending)));
}
void work(char start, char ending){
    if (work_check(start, ending)) printf("-");
    else if (start + 1 == ending) return;
    else{
        if (isAlpha(start)) 
            if(p1 == 2) start = start - 'a' + 'A', ending = ending - 'a' + 'A';
        if (p3 == 1)
            for (char i = start + 1; i < ending; i++)
                for (int n = 0; n < p2; n++)
                    printf("%c", (p1 == 3) ? '*' : i);
        else if (p3 == 2)
            for (char i = ending - 1; i > start; i--)
                for (int n = 0; n < p2; n++)
                    printf("%c", (p1 == 3) ? '*' : i);
    }
}
int main(){
    scanf("%d%d%d", &p1, &p2, &p3);
    string s; 
    cin >> s;
    char temp; 
    int first_signal, len = s.size();
    for (int i = 0; i < len; i++){
        if (s[i] == '-') printf("-");
        else{
            first_signal = i;
            break;
        }
    }
    for (int i = first_signal; i < len; i++){
        if (s[i] != '-') printf("%c", s[i]);
        else if (i + 1 == len || (i + 1 != len && s[i + 1] == '-') || (temp == '-')) printf("-");
        //字符串的下一位结束||下一位是-号且没有到达结尾||上一位是减号
        else work(temp, s[i + 1]);
        temp = s[i];
    }
    return 0;
}

题目11：作业调度方案

大模拟题，不仅考代码能力，还考你的语文阅读理解能力（大雾）；如果学过操作系统课程，实际上这道题就是希望你实现“若从0开始的第一个内存空洞大于进程所需要的内存时，将进程放入这片内存”即“最先匹配”的内存匹配机制。
题目的含义是给你一堆数据（具体含义详见代码），我们将每个工序需要的时间的序偶称之为时间片。你需要依照将这些时间片按照给定的顺序中加入到时间轴，使得所需要的时间最短，我们采取“贪心”的策略，即每个时间片扫描时间轴，当某一个空洞的大小大于当前时间片，就插入到这个空洞的最左边。

#pragma warning(disable:4996)
#include<stdio.h>
int work_list[500], m, n, ans = -1;
int opera_machine_number[25][25];
//opera_machine_number[i][j]的值为"第i个工件的第j个工序所需要使用的机械号。"
int oprea_time[25][25];
//oprea_time[i][j]的值为"第i个工件的第j个工序所需要使用的时间。"
int answer_set[500];
//answer_set[k]表示前k个工序需要的最少时间
int timeline_book[500][500];
//timeline_book[i][j]表示第i台机械在时刻j是否工作
int now_step[25];
//当前所在工件的工序数
int max(int x, int y) { return x > y ? x : y; }
int check(int begin_time, int end_time, int work_number) {
    for (int time = begin_time; time <= end_time; time++)
        if (timeline_book[work_number][time] == 1) return 0;
    return 1;
}
void input() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m * n; i++) scanf("%d", &work_list[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%d", &opera_machine_number[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%d", &oprea_time[i][j]);
}
int main() {
    input();
    for (int i = 1; i <= n * m; i++) {
        now_step[work_list[i]]++;
        //从第一个工件开始
        int now_number = opera_machine_number[work_list[i]][now_step[work_list[i]]];
        int cost_time = oprea_time[work_list[i]][now_step[work_list[i]]];
        for (int time = answer_set[work_list[i]] + 1;; time++) {
            if (check(time, time + cost_time - 1, now_number)) {
                for (int j = time; j <= time + cost_time - 1; j++) 
                    timeline_book[now_number][j] = 1;
                //-1的原因是种树原理，后面的则是标记
                answer_set[work_list[i]] = time + cost_time - 1;
                //记录所需要花费的最多的时间，因为可能插在最后一个时间记录段后面
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++) ans = max(ans, answer_set[i]);
    //虽然题目求的是最小值，但是我们需要知道，我们的方法一定可以只有前k个工序时获得所需要时间的最小值
    //即我们的answer_set[k]的值是我们求的前k个工序最多需要的时间
    //故此处取最大值指的是所有的工序全部做完的时间
    return 0 * printf("%d\n", ans);
}

题目12：帮贡排序

（先吐槽一下，这居然是我的童年回忆Q宠大乱斗的背景）
这道题就是我们要对副帮主以下的人进行按照贡献度进行排序，排序要求是按照贡献度进行通排序以分配职位，但是如果排序前后职位都没有发生变化，则需要排在前面。
所以相当于一到结构体排序的问题，由于涉及到前后未发生变化，因此需要加一个原来所在序列的位置Number。

#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define inf 0x7ffffffffffff     
//这里科普下，在符号整数的情况下，如果第一位是1，则这个数是负数，7=0111B，f=1111B
typedef struct Member {
    string Name, Post;
    //名字，职位
    long long int Contribution,Rank;
    //贡献度，等级
    int Number;
    //在输入列表中的位置
}Mem;
Mem book[200];
map<string, int> Post_Level;
//因为涉及到比较职位的大小，而字符串的比较是字典序而不是我们想要的顺序，所以我们需要
//建立从职位到等级的映射，职位越大，数字越小
long long int work_num[7] = { 0, 2, 4, 8, 15, 40, inf };
//这里看个人不同的，因为我是从0开始输入，所以是0为第一个，但是如果你是1开头，那么所有数字+1
string Post_name[7] = { "BangZhu", "FuBangZhu","HuFa", "ZhangLao","TangZhu",
             "JingYing", "BangZhong" };
bool cmp1(Mem a, Mem b) {
    if (a.Contribution == b.Contribution) return a.Number < b.Number;//输入序列顺序的从小到大
    else return a.Contribution > b.Contribution;//贡献从大到小排序
}
bool cmp2(Mem a, Mem b) {
    if (a.Post == b.Post) {
        if (a.Rank == b.Rank) return a.Number < b.Number;//输入序列顺序的从小到大
        else return a.Rank > b.Rank;//等级的从大到小排序
    }
    else return Post_Level[a.Post] < Post_Level[b.Post];//职位从小到大
}
int main() {
    for (int i = 0; i < 7; i++) Post_Level[Post_name[i]] = i;
    int num;
    cin >> num;
    for (int i = 0; i < num; i++) {
        cin >> book[i].Name >> book[i].Post >> book[i].Contribution >> book[i].Rank;
        book[i].Number = i;//就是分析所说的，前后职位都没变要放在前面
    }
    sort(book + 3, book + num, cmp1); //帮主和副帮主的相对顺序不能动，所以从3开始排序
    for (int i = 3; i < num; i++) 
        for (int j = 0; j < 7; j++) 
            if (i <= work_num[j]) {
                book[i].Post = Post_name[j];
                break;
            }
    sort(book, book + num, cmp2);
    for (int i = 0; i < num; i++) 
        cout << book[i].Name << " " << book[i].Post << " " << book[i].Rank << endl;
    return 0;
}

题目13：阶乘数码

高精度模拟阶乘，可以加入模板。

#include<iostream>
#include<string.h>
using namespace std;
int ans[2000000];
int main(){
    int t, n, a;
    cin >> t;
    for (int i = 0; i < t; i++){
        cin >> n >> a;
        memset(ans, 0, sizeof(ans));
        ans[0] = 1;
        int length = 1, cf = 0;
        for (int j = 2; j <= n; j++){
            for (int k = 0; k < length; k++){
                ans[k] = ans[k] * j + cf;
                cf = ans[k] / 10;
                ans[k] %= 10;
            }
            while (cf > 0){
                ans[length] = cf % 10;
                length++;
                cf /= 10;
            }
        }
        int cnt = 0;
        for (int j = 0; j < length; j++) if (ans[j] == a) cnt++;
        cout << cnt << endl;
    }
    return 0;
}

题目14：最大成绩

从2开始遍历，然后登记到book数组里面，这样从小到大直到不能再分，则乘积为最大值，因为乘数越多，答案越大。

#pragma warning(disable:4996)
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
const int L = 500;
int n, c = 1, number[10000];//number是存储拆分的数字
string ans[10000], total = "1";//s数组用来存每一个数字
string add(string str1, string str2) {
    string str;
    int len1 = str1.length(), len2 = str2.length();
    if (len1 < len2)
        for (int i = 1; i <= len2 - len1; i++) str1 = "0" + str1;
    else
        for (int i = 1; i <= len1 - len2; i++) str2 = "0" + str2;
    len1 = str1.length();
    int cf = 0;
    int temp;
    for (int i = len1 - 1; i >= 0; i--) {
        temp = str1[i] - '0' + str2[i] - '0' + cf;
        cf = temp / 10;
        temp %= 10;
        str = char(temp + '0') + str;
    }
    if (cf != 0)  str = char(cf + '0') + str;
    return str;
}
string mul(string str1, string str2) {
    string str;
    int len1 = str1.length();
    int len2 = str2.length();
    string tempstr;
    for (int i = len2 - 1; i >= 0; i--) {
        tempstr = "";
        int temp = str2[i] - '0';
        int t = 0;
        int cf = 0;
        if (temp != 0) {
            for (int j = 1; j <= len2 - 1 - i; j++) tempstr += "0";
            for (int j = len1 - 1; j >= 0; j--) {
                t = (temp * (str1[j] - '0') + cf) % 10;
                cf = (temp * (str1[j] - '0') + cf) / 10;
                tempstr = char(t + '0') + tempstr;
            }
            if (cf != 0) tempstr = char(cf + '0') + tempstr;
        }
        str = add(str, tempstr);
    }
    str.erase(0, str.find_first_not_of('0'));
    if (str.length() == 0) str = "0";
    return str;
}
string Num_to_String(int x) {
    int i = 0, j;
    string p = "";
    char ch[10], t;
    do {
        ch[i] = x % 10 + '0';
        x /= 10;
        i++;
    } while (x != 0);
    ch[i] = '\0';
    for (j = 0, i--; j <= i / 2; j++, i--) {
        t = ch[j];
        ch[j] = ch[i];
        ch[i] = t;
    }
    return ch;
}
int main() {
    scanf("%d", &n);
    if (n <= 4) return 0 * printf("%d\n%d\n", n, n);
    for (int i = 2; i <= n; i++) {
        if (n >= i) n -= i, number[c++] = i, ans[c - 1] = Num_to_String(i);
        else break;
    }
    for (int i = c - 1; i >= 1; i--) if (n > 0) 
        number[i]++, ans[i] = Num_to_String(number[i]), n--;
    if (n > 0) 
        number[c - 1]++, ans[c - 1] = Num_to_String(number[c - 1]);
    for (int i = 1; i < c; i++) {
        cout << number[i] << " ";
        total = mul(ans[i], total);
    }
    cout << endl << total;
    return 0;
}

题目15：麦森数

位数可以使用n*log10(2)+1公式来获得（这个是专门求位数的函数），推导的话后续再补上。

#include<stdio.h>
#include<math.h>
#include<string.h>
int even_res[2000], res[2000], temp[2000], p;
void odd(){//这个函数接口是当前数字为奇数的时候，由于除二会阶段最后的1，需单独计算一次
    memset(temp, 0, sizeof(temp));
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            temp[i + j - 1] += res[i] * even_res[j];
    for (int i = 1; i <= 500; i++) {
        temp[i + 1] += temp[i] / 10;
        temp[i] %= 10;
    }
    memcpy(res, temp, sizeof(res));
}
void even(){//这个函数接口是当前数字为偶数的时候
    memset(temp, 0, sizeof(temp));
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            temp[i + j - 1] += even_res[i] * even_res[j];
    for (int i = 1; i <= 500; i++){
        temp[i + 1] += temp[i] / 10;
        temp[i] %= 10;
    }
    memcpy(even_res, temp, sizeof(even_res));
}
int main(){
    scanf("%d", &p);
    printf("%d\n", (int)(log10(2) * p + 1));
    res[1] = 1, even_res[1] = 2;
    while (p != 0){//快速幂基本思想，分治
        if (p & 1) odd();
        p /= 2;
        even();
    }
    res[1]--;
    for (int i = 500; i >= 1; i--)
        if (i != 500 && i % 50 == 0) printf("\n%d", res[i]);
        else printf("%d", res[i]);
    return 0;
}

模拟题是考验代码和细心程度的题，一定要尽可能的自己敲，虽然“算法”含量不高，但是确是一定程度上不能够丢的题。