【CSP试题回顾】201712-2-游戏

CSP-201712-2-游戏

解题思路

代码实现了一个模拟游戏过程的算法，其中n个小朋友围成一圈，按照顺时针方向依次编号从1到n，然后按顺时针方向依次报数。每当报的数是k的倍数或者个位数是k时，报数的小朋友会被淘汰。游戏继续进行，直到只剩下一个小朋友，这个小朋友就是游戏的赢家。下面是具体的解题思路：

初始化变量：

参数	描述
n	参与游戏的小朋友总数
k	特定的数字，小朋友报的数如果是这个数的倍数或其个位数是这个数则被淘汰
i	当前报数的小朋友在数组中的索引
num	当前报的数
arr	存储还在游戏中的小朋友的编号的向量

填充数组：使用一个循环，将1到n的每个数字添加到数组arr中，这表示初始时所有的小朋友都在游戏中。
游戏循环：使用while循环模拟游戏过程。这个循环会一直执行，直到arr数组的大小缩减到1，即只剩下一个小朋友，游戏结束。
判断条件：在循环中，程序首先将当前报的数num转换为字符串t，然后检查两个条件：
- 如果num是k的倍数（num % k == 0），或者
- num的个位数（t[t.size() - 1] - '0'）等于k，
如果满足以上任一条件，则当前报数的小朋友（arr[i]）被淘汰，从数组中删除。
更新索引和报数：
- 如果一个小朋友被淘汰，i的值会保持不变，但由于数组的大小减少了，我们需要对i执行模数组新大小的操作（i %= arr.size()），以确保i不会超出范围。
- 如果当前小朋友没有被淘汰，那么i就递增1（并在必要时绕回到数组的开头），同时num（报的数）也递增1。
输出胜利者：当数组中只剩下一个元素时，游戏结束，循环退出。最后剩下的这个元素（arr[0]）就是获胜的小朋友的编号，输出这个编号。

完整代码

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int n, k, i, num = 1;

int main() {    
    cin >> n >> k;
	vector<int>arr(n);
	for (int i = 0; i < n; i++) {
		arr[i] = i + 1;
	}

	while (arr.size() != 1)
	{
		string t = to_string(num);
		if (num % k == 0) {
			arr.erase(arr.begin() + i);
			i %= arr.size();
		}
		else if ((t[t.size() - 1] - '0') == k) {
			arr.erase(arr.begin() + i);
			i %= arr.size();
		}
		else i = (i + 1) % arr.size();
		num++;
	}
	cout << arr[0];
    return 0;
}