模拟算法总述

模拟

1.模拟算法介绍

模拟算法通过模拟实际情况来解决问题，一般容易理解但是实现起来比较复杂，有很多需要注意的细节，或者是一些所谓很”麻烦”的东西。
模拟题一般不涉及太难的算法，一般就是由较多的简单但是不好处理的部分组成的，考察选手的细心程度和整体的逻辑思维。
一般为了使得模拟题写的逻辑清晰一些，经常会写比较多的小函数来帮助解题，例如int和string的相互转换、回文串的判断、日期的转换、各种特殊条件的判断等等。

2.例题

2.1 地址转换

题目描述

Excel是最常用的办公软件。每个单元格都有唯一的地址表示。比如：第12行第4列表示为:“D12”，第5行第255列表示为"IU5"。
事实上，Excel提供了两种地址表示方法，还有一种表示法叫做RC格式地址。第12行第4列表示为"R12C4"，第5行第255列表示为"R5C255""。你的任务是:编写程序，实现从RC地址格式到常规地址格式的转换。

输入描述
用户先输入一个整数 $n (n < 100)$ ，表示接下来有 $n$ 行输入数据。
接着输入的n行数据是RC格式的Excel单元格地址表示法。

输出描述
程序则输出 $n$ 行数据，每行是转换后的常规地址表示法。

输入输出样例

示例

输入

2
R12C4
R5C255

输出

D12
IU5

思路

这个题本质就是进制的转化，Excel表中的列可以转换为26进制。

代码

#include <bits/stdc++.h>
using namespace std;

int n, r, c;
char a, b;
int main() {
	cin >> n;
	while(n --) {
		cin >> a >> r >> b >> c;
		if(b <= 26) {
			char d = c + 'A' - 1;
			cout << d << r << endl;
		} else if(b > 26) {
			char d = 'A' + c/26 - 1;
			char e = 'A' + c%26 - 1;
			cout << d << e << c << endl;
		}
	}	
	return 0;
}

2.2 DNA序列修正

问题链接：https://www.lanqiao.cn/problems/3904/learning/page=1&first_category_id=1&name=DNA

问题描述
在生物学中， $D N A$ 序列的相似性常被用来研究物种间的亲缘关系。现在我们有两条 $D N A$ 序列，每条序列由 $A 、 C 、 G 、 T$ 四种字符组成，长度相同。但是现在我们记录的 $D N A$ 序列存在错误，为了严格满足 $D N A$ 序列的碱基互补配对即 $A - T$ 和 $C - G$ ，我们需要依据第—条 $D N A$ 序列对第二条 $D N A$ 序列进行以下操作:
1.选择第二条 $D N A$ 序列的任意两个位置，交换他们的字符。
2.选择第二条 $D N A$ 序列任意一个位置，将其字符替换为 $A 、 C 、 G 、 T$ 中的任何一个。
需要注意的是：每个位置上的碱基只能被操作一次!
你的任务是通过最小的操作次数，使第二条 $D N A$ 序列和第一条 $D N A$ 序列互补。并且已知初始两条 $D N A$ 序列长度均为 $N$ 。

输入格式
第一行包含一个整数 $N$ ， $1 <N<10^3)$ ，表示 $D N A$ 序列的长度。
接下来的两行，每行包含一个长度为 $N$ 的字符串，表示两条 $D N A$ 序列。

输出格式
输出一个整数，表示让第二条DNA序列和第—条DNA序列互补所需的最小操作次数。

样例输入

5
ACGTG
ACGTC

样例输出

样例说明

将第二条DNA序列中的第一个和第四个碱基交换，将第二个和第三个碱基交换即可完成全部配对，共操作两次。

思路

我们可以考虑贪心的思路，因为每次修改操作只能修正一个位置，就是操作和得分比是1∶1;如果我们考虑通过交换来同时修正两个位置，那么操作和得分比就是1∶2，我们应当尽可能多地使用该操作。那么整个过程就是:

1.从左到右扫描第一条DNA序列和第二条DNA序列的每一个位置，检查它们是否互补。

2.**如果某个位置不互补，我们需要寻找第二条DNA序列中后续位置的碱基，看是否可以通过交换使这两个位置都互补。**如果可以，我们就进行交换。注意：**这里必须是交换后，两个位置都互补，否则交换没有意义。**如果交换后，一个位置互补，另一个位置不互补，此次交换等价于直接改变元素，所以不能交换。同时，这样的交换还会影响到交换两个位置都互补的情况。简单来说，如果交换的条件是：有一个位置互补，另一位置不互补也交换，导致后面交换两个位置都互补的情况不存在了，就会影响最终的结果。

3.如果在后续位置找不到可以交换的碱基，说明这个位置只能通过替换来满足要求。因为每个位置只能修改一次，所以我们不能把不配对的碱基交换到当前位置作为中转站，则只能进行修改。

4.每次交换或替换，操作计数器增加1。

5.最后输出操作计数器的值。

代码

#include<iostream>
#include<map>
using namespace std;

map<char, int> mp{
        {'A', 0},
        {'C', 1},
        {'G', 2},
        {'T', 3}
};

int main() {
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (mp[a[i]] + mp[b[i]] != 3) {
            for (int j = i + 1; j < n; j++) {
                if (mp[a[i]] + mp[b[j]] == 3 && mp[a[j]] + mp[b[i]] == 3) {
                    swap(b[i], b[j]);
                    break;
                }
            }
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

2.3 拉马车

问题链接：https://www.lanqiao.cn/problems/101/learning/page=1&first_category_id=1&name=%E6%8B%89%E9%A9%AC%E8%BD%A6

题目描述

小的时候，你玩过纸牌游戏吗?有一种叫做"拉马车"的游戏，规则很简单，却很吸引小朋友。其规则简述如下:

假设参加游戏的小朋友是 $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$ 双方轮流出牌。
当轮到某一方出牌时，他从自己的纸牌队列的头部拿走—张，放到桌上，并且压在最上面—张纸牌上(如果有的话)。

此例中，游戏过程:
$A$ 出 $K$ ， $B$ 出 $2$ ， $A$ 出 $8$ ， $B$ 出 $7$ ， $A$ 出 $X$ ，此时桌上的序列为:
$K, 2, 8, 7, X$
当轮到 $B$ 出牌时，他的牌 $K$ 与桌上的纸牌序列中的 $K$ 相同，则把包括 $K$ 在内的以及两个 $K$ 之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。
此时， $A$ 、 $B$ 双方的手里牌为:
$A$ 方： $[K, A, 2, A, 9, 5, A]$
$B$ 方： $[5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]$ 赢牌的一方继续出牌。也就是 $B$ 接着出 $5$ ， $A$ 出 $K$ ， $B$ 出 $J$ ， $A$ 出 $A$ ， $B$ 出 $5$ ，又赢牌了。此时桌上的序列为:
$5, K, J, A, 5$

此时双方手里牌:

$A$ 方： $[2, A, 9, 5, A]$

$B$ 方： $[Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]$

注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。
当某一方出掉手里最后—张牌，但无法从桌面上赢取牌时，游戏立即结束。
对于本例的初始手牌情况下，最后 $A$ 会输掉，而 $B$ 最后的手里牌为:
$9 K 2 A 62 K A X 58 K 57 K J 5$
本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出 $- 1$ 。

输入描述

输入为 $2$ 行， $2$ 个串，分别表示 $A 、 B$ 双方初始手里的牌序列。我们约定，输入的串的长度不超过 $30$ 。 $2 J 9 A 7 Q A 6 Q 6889977$

输出描述

输出为 $1$ 行， $1$ 个串，表示 $A$ 先出牌，最后赢的一方手里的牌序。

输入输出样例

示例

输入

96J5A898QA
6278A7Q973

输出

2J9A7QA6Q6889977

思路

代码使用string、stack去模拟这个过程。 $A$ 、 $B$ 双方的出牌是从头部拿走一张，可以用队列来存储字符，也可以用string类的模仿字符队列。

xxxx.erase(0, 1) // 实现头部数据的弹出

stack的入栈和出栈操作与牌堆类似，所以用stack模拟牌堆。

在题目中，交换A、B双方的操作权是一大难点。下面给出了详细的解决过程。使用到了指针、bool变量来完成。

代码

#include <bits/stdc++.h>
using namespace std; 


bool a[128]; // a[i]表示牌堆中是否存在i这张牌 
int main() { 
  string A, B; 
  cin >> A >> B; 
  stack<char> S; // 用栈作为牌堆
  S.push(A[0]); a[A[0]-0]=1; A.erase(0,1); // A先出牌
  bool flag=1; // flag控制到谁出牌 
  int times=0; // times表示出牌次数，超过10000认为会无限循环 
  while(A.length() && B.length() && times<10000){ 
    string* sp=flag?&B:&A; // flag为1时B出牌，将string指针指向B，方便实现B的出牌和收牌 
    char tmp=(*sp)[0];
    S.push(tmp); sp->erase(0,1); // 玩家出牌 
    if(a[tmp-0]==0) { a[tmp-0]=1; flag = !flag; } // 牌堆中没有当前出的牌，牌权更换 
    else{ // 若包含当前字符，收回一部分牌 
      *sp += S.top(); S.pop(); // 收回刚出的那张牌，位于栈顶 
      while(S.top()!=tmp){ *sp += S.top(); a[S.top()-0] = 0; S.pop(); } //一直收牌到与所出牌相同的另一张牌处 
      *sp += S.top(); a[S.top()-0] = 0; S.pop(); 
    } 
    times++; 
  } 
  if(times>=10000) return -1; 
  if(A.length()) cout<<A; else cout<<B; 
  return 0; 
}

2.4 机器人行走

题目链接：https://www.lanqiao.cn/problems/283/learning/page=1&first_category_id=1&name=%E6%9C%BA%E5%99%A8%E4%BA%BA%E8%A1%8C%E8%B5%B0

题目描述

某少年宫引进了一批机器人小车。可以接受预先输入的指令，按指令行动。小车的基本动作很简单，只有 $3$ 种：左转(记为 $L$ )，右转（记为 $R$ )，向前走若干厘米(直接记数字)。
例如，我们可以对小车输入如下的指令：
$15 L 10 R 5 L RR 10 R 20$
则，小车先直行 $15$ 厘米，左转，再走 $10$ 厘米，再右转，….
不难看出，对于此指令串，小车又回到了出发地。
你的任务是：编写程序，由用户输入指令，程序输出每条指令执行后小车位置与指令执行前小车位置的直线距离。

输入描述

用户先输入一个整数 $n (n < 100)$ ，表示接下来将有 $n$ 条指令。
接下来输入 $n$ 条指令。每条指令只由 $L 、 R$ 和数字组成(数字是 $0$ ~ $100$ 之间的整数)
每条指令的长度不超过 $256$ 个字符。

输出描述
程序则输出 $n$ 行结果，每条结果表示小车执行相应的指令前后位置的直线距离。要求四舍五入到小数后 $2$ 位。

输入输出样例

示例

输入

5
L100R50R10
3LLL5RR4L12
LL
100R
5L5L5L5

输出

思路

这个题的难点分别包括模拟小车的方向和坐标、小车的指令与行驶距离的区分。

首先，解决小车的方向和坐标问题。使用int变量x,y分别代表小车的横纵坐标。使用int k代表小车的方向。

在这里插入图片描述

默认车的方向为 $k = 0$ ，如果想要实现右转， $k = (k + 1)$ % $4$ 即可。如果想要实现左转， $k = (k + 3)$ % $4$ 。

实现函数为：

void move(int dis){
  if(k == 0)y += dis;
  else if(k == 1)x += dis;
  else if(k == 2)y -= dis;
  else x-= dis;
}

小车的指令与行驶距离的区分，可以使用if条件语句进行区分，当读到指令后，调整方向，如果读到数字，说明为距离，应该继续向后读，读完整个距离。

代码

#include <bits/stdc++.h>
using namespace std;

int n, x, y, k;
// k = 0向上走, k = 1向右走, k = 2向下走, k = 3向左走
void move(int dis){
  if(k == 0)y += dis;
  else if(k == 1)x += dis;
  else if(k == 2)y -= dis;
  else x-= dis;
}

int main(){
  cin >> n;     // 读取指令的个数
  while(n--){
    x = 0, y = 0, k = 0; // x, y代表坐标, k代表方向
    string str; // 接收当前的指令
    cin >> str;
    for(int i = 0;i < str.length();++i){
      if(str[i] == 'L')k = (k+3)%4; 
      else if(str[i] == 'R')k = (k+1)%4;
      else{
        int dis = str[i] - '0'; // 说明当前时为距离
        while(++i < str.length() && str[i]!='L' && str[i]!='R') // 完整读取当前的距离
          dis = dis*10 + str[i] - '0';
        move(dis);// 进行移动
        --i;//在寻找完整距离时, i的下标已经指向数字的下一位
      }
    }
    printf("%.2f\n", sqrt(x*x + y*y));
  }
  return 0;
}


; 
      else if(str[i] == 'R')k = (k+1)%4;
      else{
        int dis = str[i] - '0'; // 说明当前时为距离
        while(++i < str.length() && str[i]!='L' && str[i]!='R') // 完整读取当前的距离
          dis = dis*10 + str[i] - '0';
        move(dis);// 进行移动
        --i;//在寻找完整距离时, i的下标已经指向数字的下一位
      }
    }
    printf("%.2f\n", sqrt(x*x + y*y));
  }
  return 0;
}