牛客小白月赛4 (B 博弈论)

博弈论

地址：https://ac.nowcoder.com/acm/contest/134/B

题意：铁子和顺溜在学习了博弈论的sg函数之后，解决了很多很多博弈题，现在他们遇到了一道难题。给出一个长度为 n 的数列，数列里的每个元素都是个位数，这个数列的每一个连续子数列都能生成一个十进制数，对于子数列a[l~r]，这个十进制数的个位为a[r],十位为a[r - 1]，...，最高位为a[l]。
　　现在铁子需要知道最小的不能被该数列的子数列生成的十进制非负整数是多少？

题解：这道题乍一看以为是博弈，其实和博弈一点关系也没有，题目给出了n的取值范围[1,1000],这是一个突破点仔细想一下，你要想要表示完1~1000之间的数总共需要多少位数。这么看吧，表示[0,9]需要十位数，表示[10,99]需要90*2位，表示[100,1000]需要900*3位，这样想的话如果要全部表示完，肯定是不能实现的，所以我们只需要遍历[0,1000]之间的数字就行，这样就可以简单判断了。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
int main(){
    int n,t;
    cin>>n;
    string ptr;
    for(int i=0;i<n;i++){
        cin>>t;
        ptr=ptr+(char)(t+'0');
    }
    for(int i=0;i<=1000;i++){
        string pt;
        int ar=i;
        if(ar==0){
            pt=pt+(char)(ar+'0');
        }else{
            while(ar){
                pt=pt+(char)(ar%10+'0');
                ar=ar/10;
            }
        }
        string a(pt.rbegin(),pt.rend());
        if(ptr.find(a)==-1){
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

 个人评价：这题应该划分到“思维”那个范围里面去，而不是“博弈”。只能说这个题目有点误导人。