当前位置：首页 > news >正文

每日一题——博弈论（枚举与暴力）

news 2025/8/5 0:52:10

博弈论

题目描述

运行代码

#include<iostream>
#include<vector>
using namespace std;
int main(){int n;cin >> n;vector<int> d(n,0);for(int i = 0;i < n;i++){cin >> d[i];}vector<int> in(1000,0);for(int k = 1;k<=3;k++){for(int i=0;i<=n-k;i++){int t = 0;for(int j=i;j<i+k;j++){t = 10*t+d[j];}in[t] = 1;}}for(int i = 0;i < 1000;i++)if(in[i] == 0){cout << i << endl;return 0;}return 0;
}

代码思路

输入处理:
- 首先，程序接收一个整数n，表示数字序列的长度。
- 然后，程序读取接下来的n个整数并存储在一个名为d的vector（动态数组）中。
初始化标记数组:创建一个大小为1000的vector in，并将其所有元素初始化为0。这个数组用来标记长度为1至3位的整数是否在给定序列中出现过。由于最大的3位数是999，因此1000的大小足够覆盖所有可能的情况。
检查数字序列:对于长度为1、2、3的子序列，程序遍历所有可能的起始位置i：计算从位置i开始，长度为k（当前循环的长度）的子序列对应的整数t。这是通过将子序列中的每个数字乘以相应位值（10的幂）并求和得到的。将计算出的整数t在in数组中标记为1，表示这个数值已经在输入序列中出现过了。
寻找未出现的最小整数:
- 遍历in数组，找到第一个值为0的元素的索引，这代表了未在输入序列中出现过的最小正整数。
- 一旦找到这样的索引，立即输出该索引（即对应的整数），并结束程序。
返回:如果遍历完整个in数组都没有找到未出现的整数（理论上这种情况不应该发生，但代码逻辑没有直接处理这种特殊情况），程序会正常结束。

改进思路

减少内存使用：目前使用了一个大小为1000的vector来标记数字是否出现，其实最大只需要到n的长度变化的所有组合即可，特别是当n远小于3时。可以通过动态调整in的大小或者使用更高效的数据结构如set或unordered_set来改进。
优化寻找未出现数字的步骤：当前实现是线性查找in数组中值为0的第一个元素，若大多数数字都已出现，则效率较低。可以在遍历过程中直接记录第一个未出现的数字，减少后续查找步骤。
增加对极端情况的处理：例如，当输入序列为空或全为0时，原始代码可能表现得不够直观或正确。

改进代码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;int main() {int n;cin >> n;vector<int> d(n, 0);// 输入数字序列for (int i = 0; i < n; ++i) {cin >> d[i];}// 使用unordered_set存储已出现的数字，自动去重且查找效率高unordered_set<int> appeared;// 检查数字序列，添加长度为1到3的数字到集合中for (int k = 1; k <= min(3, n); ++k) { // 添加边界条件避免n<k时的无效迭代for (int i = 0; i <= n - k; ++i) {int t = 0;for (int j = i; j < i + k; ++j) {t = 10 * t + d[j];}appeared.insert(t);}}// 寻找未出现的最小正整数int i = 1;while (appeared.find(i) != appeared.end()) {++i;}cout << i << endl;return 0;
}