第 35 课：一维数组模拟
一维数组模拟是一种利用数组下标和元素值来存储状态或者模拟某种操作的手段。这里主要讲解信息学奥赛中一维数组模拟的核心方法与实战技巧。
35.1 核心考查
时间线模拟：用数组下标作为时间点，元素用来存储事件，比如记录各时间点的人数。
状态位置：用数组下标当作位置，用元素存储状态，比如记录线性迷宫的障碍物、线性扫雷中的雷区等。
替代多维数组：将二维数组的行和列展开，用一维数组代替。
35.2 实例讲解
例 1：奇妙的灯控
在一个宽敞明亮的大厅里，整齐排列着 n 盏精致的灯，这些灯从 1 到 n 按照顺序依次被编上了独特的号码。
此时，有 m 位神秘的访客陆续来到这个大厅。这些访客也按照从 1 到 m 的顺序依次排好了队，他们每个人都拥有一项特殊的能力，那就是可以对大厅里的灯进行特定的操作。
首先，第一位访客迈着沉稳的步伐走进了大厅。他拥有掌控所有灯的能力，只见他轻轻一挥手，原本明亮的 n 盏灯瞬间全部熄灭，大厅一下子陷入了黑暗之中。
紧接着，第二位访客缓缓踏入了这片黑暗。他的能力与第一位不同，他只能对编号为 2 的倍数的灯进行操作。他专注地沿着灯的排列顺序走去，每遇到编号是 2 的倍数的灯，便施展能力将其打开。于是，2 号灯、4 号灯、6 号灯……一盏盏地重新亮起，大厅里又有了星星点点的光亮。
随后，第三位访客带着自信的神情走进了大厅。他的任务是对编号为 3 的倍数的灯进行相反的处理。他仔细地观察着每一盏灯，当遇到编号为 3 的倍数的灯时，如果灯是亮着的，他就将其关闭；如果灯是熄灭的，他就将其打开。就这样，3 号灯、6 号灯、9 号灯……它们的状态在第三位访客的操作下发生了改变。
随着时间的推移，后续的访客按照编号递增的顺序依次进入大厅。每一位访客都严格遵循规则，对编号为自己编号倍数的灯进行相反的处理。第四位访客会对 4 号、8 号、12 号等灯进行操作，第五位访客会对 5 号、10 号、15 号等灯进行操作……每一次操作都像是在这个灯的世界里掀起了一阵小小的波澜。
在经过这 m 位访客的操作之后，哪些灯是熄灭的呢？
【输入格式】输入一行，包含两个正整数 n 和 m，n 和 m 均大于 1 且小于 1000。
【输出格式】输出一行，依次输出熄灭状态的灯的编号，用英文状态下的逗号隔开。
【输入样例】10 10
【输出样例】1,4,9
解析
因为灯只会出现 0 和 1 两种状态，我们可以使用数组中的元素来表示每盏灯的状态。随后，只需要重复执行 m 次操作：每次操作中，寻找下标为当前序号的倍数的元素，然后将其状态进行更改，如果是 1 就变成 0，是 0 就变成 1。
最后对数组元素进行判断，找出状态为 0 的元素，并输出其对应的下标。
输出时要注意的问题是，不同编号之间用逗号隔开，而不是用空格。
参考代码
#include <iostream>
using namespace std;
int a[1010]; // 全部是 0，表示关闭
int main()
{
int n, m;
cin >> n >> m;
for (int i = 2; i <= m; i++) // 从第二个人开始操作
for (int j = i; j <= n; j += i) // 编号对应倍数下标
if (a[j] == 1)
a[j] = 0;
else
a[j] = 1; // 更改状态
cout << 1; // 1 号肯定关闭
for (int i = 2; i <= n; i++)
if (a[i] == 0)
cout << "," << i; // 间隔逗号输出
return 0;
}例 2：数组变化
现有一个长度为 n 的数组，对这个数组进行 m 次操作。可以对数组进行的操作分为以下三类。
操作 1：输入 1 i，表示输出数组中第 i 个元素的值。
操作 2：输入 2 i v，表示在数组中第 i 个元素前加入新的元素 v。
操作 3：输入 3 i，表示删除数组中的第 i 个元素。
注意：三类操作都要满足 i ≤ n。
【输入格式】输入 3 + m 行。
第 1 行输入一个正整数 n，表示数组的初始长度。
第 2 行输入 n 个用空格隔开的正整数，表示原始的数组。
第 3 行输入一个正整数 m，表示操作的次数。
接下来的 m 行分别是每次对数组进行的操作（题目描述中三类操作中的一类）。
【输出格式】对于第一种操作输出对应的答案，一行输出一个数。
【输入样例】
5
6 7 8 9 10
5
1 2
2 2 12
1 2【输出样例】
7
12
8【数据范围】n ≤ 500，m ≤ 500。
解析
题目要求对一个长度为 n 的数组进行 m 次操作，操作分为三类：输出指定位置元素的值、在指定位置前插入新元素、删除指定位置的元素。代码通过读取输入的数组和操作信息，根据不同的操作类型对数组进行相应的处理，并输出操作 1 的结果。
- 读取数组初始信息：定义变量 n 表示数组的初始长度，m 表示操作的次数，p 表示操作类型，q 表示操作涉及的数组位置，v 表示插入元素的值。通过循环读取 n 个整数，将其存储到数组 a 中，数组下标从 1 开始，代码如下：
int n, m, p, q, v;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];- 读取操作次数，代码如下：
cin >> m;循环处理操作：使用 for 循环进行 m 次操作，每次循环均输入一次操作 p。
a. 操作 1（p == 1）：读取要查询的数组位置 q，输出数组 a 中第 q 个元素的值，并换行。代码如下：
if (p == 1)
{
cin >> q;
cout << a[q] << endl;
}b. 操作 2（p == 2）：读取要插入的位置 q 和插入的值 v，使用 for 循环从数组末尾开始，将从第 q 个位置开始的元素依次向后移动一位，为插入新元素腾出位置，将新元素 v 插入第 q 个位置，并将数组长度 n 加 1。代码如下：
else if (p == 2)
{
cin >> q >> v;
for (int j = n; j >= q; j--) // 依次向后移动
a[j + 1] = a[j];
a[q] = v; // 单独把插入的数字放入位置
n++; // 数组长度加 1
}c. 操作 3（p == 3）：读取待删除元素的位置 q，使用 for 循环将从第 q + 1 个位置开始的元素依次向前移动一位，覆盖第 q 个元素，并将数组长度 n 减 1。代码如下：
else if (p == 3)
{
cin >> q;
for (int j = q; j < n; j++) // 依次向前移动
a[j] = a[j + 1];
n--; // 数组长度减 1
}参考代码
#include <iostream>
using namespace std;
int a[1001];
int main()
{
int n, m, p, q, v;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> p;
if (p == 1)
{
cin >> q;
cout << a[q] << endl;
}
else if (p == 2)
{
cin >> q >> v;
for (int j = n; j >= q; j--) // 依次向后移动
a[j + 1] = a[j];
a[q] = v; // 单独把插入的数字放入位置
n++; // 数组长度加 1
}
else if (p == 3)
{
cin >> q;
for (int j = q; j < n; j++) // 依次向前移动
a[j] = a[j + 1];
n--; // 数组长度减 1
}
}
return 0;
}例 3：折叠游戏
蛙蛙和氪町博士在玩数组折叠游戏。
游戏规则是，给出 n 个整数，按照从左到右的顺序排列，现在需要将这 n 个整数从中间折叠 m 次，右半部分的元素叠加到左半部分。每次折叠后，重合的两个数字会相加变成一个新的数字。
请你输出折叠 m 次后的 s 数组。
【输入格式】输入两行。
第 1 行输入一个正整数 n 表示序列的长度，输入一个正整数 m 表示折叠的次数。
第 2 行输入 n 个用空格隔开的正整数，数字不超过 100。
【输出格式】输出一行，为折叠 m 次后的数组。
【输入样例】
5 2
1 2 3 4 5【输出样例】9 6
【数据范围】n ≤ 1000，m ≤ 1000。
解析
按照给定的规则对数组进行 m 次折叠操作，每次折叠时将数组右半部分的元素对应叠加到左半部分，之后更新数组的长度，最后输出折叠 m 次后的数组。
读取输入信息：定义变量 n 表示数组的初始长度，m 表示折叠的次数；从标准输入读取 n 和 m 的值，通过循环读取 n 个整数，将其存储到数组 a 中，数组下标从 1 开始。
进行 m 次折叠操作：外层 for 循环控制折叠的次数，共进行 m 次折叠。
a. 内层 for 循环实现当前折叠操作：对于 j 从 1 到 n / 2，将数组 a 中对称位置的元素相加，即 a[j] 加上 a[n - j + 1]。例如，当 n = 5 时，第一次折叠会将 a[1] 和 a[5] 相加，结果存于 a[1]；将 a[2] 和 a[4] 相加，结果存于 a[2]。
b. 折叠后数组长度的处理：如果 n 是奇数，执行 n++。这一步是为了后续计算新长度时能正确处理中间元素。例如，当 n = 5 时，先加 1 变为 6，再除以 2 得到新长度 3，这样中间元素也能正确处理。然后将 n 除以 2，更新数组的长度为原来的一半。
代码如下：
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n / 2; j++)
a[j] += a[n - j + 1];
if (n % 2 != 0)
n++;
n /= 2;
}参考代码
#include <iostream>
using namespace std;
int a[1010];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n / 2; j++)
a[j] += a[n - j + 1];
if (n % 2 != 0)
n++;
n /= 2;
}
for (int i = 1; i <= n; i++) // 输出折叠 m 次后的数组
cout << a[i] << ' ';
return 0;
}例 4：数字消消乐
蛙蛙最近迷上了计算机游戏，有一天他发现了一款叫"数字消消乐"的游戏，其规则如下：给定一个长度为 n 的整型数组，指定一个数 a，如果该数组中有 3 个及 3 个以上的 a 连续出现，则该数字将会从数组中消除。
【输入格式】输入两行。
第 1 行输入 2 个正整数，分别代表数组长度 n 以及需要消除的数字 a，中间用一个空格隔开。
第 2 行输入 n 个正整数，相邻正整数之间用单个空格隔开。
【输出格式】输出一行，表示消除所有数字 a 之后的新整型数组，相邻数之间用单个空格隔开。
【输入样例】
10 4
1 2 4 4 3 4 4 4 4 5【输出样例】1 2 4 4 3 5
【数据范围】1 ≤ n ≤ 1000，1 ≤ a ≤ 100。
解析
要从给定的整型数组中消除连续出现 3 个及 3 个以上的指定数字 a，并输出消除后的新数组，可以通过两层循环遍历数组，统计连续出现的指定数字的个数，若个数达到 3 个，则跳过这些数字，否则正常输出该数字。
先定义变量 n 表示数组的长度，a 表示需要消除的指定数字，num 用于统计连续出现的指定数字 a 的个数。通过循环读取 n 个整数，将其存储到数组 s 中，数组下标从 1 开始。
外层 for 循环从数组的第一个元素开始遍历，直到最后一个元素。
内层 for 循环从当前外层循环的元素位置 i 开始，向后遍历数组，统计连续出现的指定数字 a 的个数。
a. 如果 s[j] 等于 a，则 num 加 1。
b. 如果 s[j] 不等于 a，则跳出内层循环。
内层循环结束后，根据 num 的值进行不同处理。
a. 如果 num 大于或等于 3，说明连续出现了 3 个及 3 个以上的指定数字 a，将外层循环的下标 i 更新为 i + num - 1，即跳过这些连续的数字。
b. 如果 num 小于 3，说明当前元素以及后续连续的指定数字 a 的个数不足 3 个，正常输出当前元素 s[i]。
将 num 计数器归零，以便下一次统计。
参考代码
#include <iostream>
using namespace std;
int s[1110];
int main()
{
int n, a, num;
cin >> n >> a;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= n; i++)
{
num = 0;
for (int j = i; j <= n; j++)
{
if (s[j] == a)
num++;
else
break;
}
if (num >= 3) // 如果连续相同的数字超过 3 个
i = i + num - 1; // 将下标跳过
else
cout << s[i] << " "; // 否则正常输出
num = 0; // 计数器归零
}
return 0;
}