X游戏题解

本题暴力遍历每个数再判断是否为好数是可以解决的，但是我这里提供一个非暴力的解法。(用数学找规律）

题目描述
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

输入描述:
输入正整数N
输出描述:
输出1到N中好数个数
示例1
输入

10

输出

4

对输入的N，我们从该数的左边开始遍历，以12为例，设置两个数组num, num_possible,数组长度均为N的位数。num[i]表示截止第i位，可以出现的好数个数，num_possible[i]表示截止第i为，可以出现的有潜力成为好数的个数（均由0,1,8组成的数的个数）
开始遍历12
第0位为1
num[0] = 0（第一位为1，仅可以出现0,1，均不是好数）
num_possible = 2（可取0,1两个）
第1位为2
对num[1]而言，前面几位构成好数（num[i-1]个），现在增加一位，可以取0,1,2,5,6,8,9（7种），前面几位构成潜在好数（num_possible[i-1]个），现增加一位，可以取2,5,6,9四位
所以num[1] = 7*num[0] + num_possible[0]*4
对于num_possible[1]而言，前面几位构成潜在好数（num_possible[i-1]个），现增加一位，可以取0,1,8三位
所以num_possible[1] = num_possible[0]*3
但是现在还没有结束，因为对于第0位为1的时候，我们第二位仅仅可以取0,1,2三种。
1本身是潜在好数（受影响的是num_possible[0]），我们需要把num_possible[0]的其中一个单拎出来讨论
num[1] = 7*num[0] + (num_possible[0]-1)*4 + 1（第0位为1，第二位只有2一种）
num_possible[1] = (num_possible[0]-1)*3 + 2（第0位为1，第二位只有0,1两种）
现在我们有公式：
num[i] = 7*num[i-1] + num_possible[i-1]*4
num_possible[1] = num_possible[i]*3
若N的前i-1项构成好数：
num[i] -= 7 - (N[i]前包含0,1,2,5,6,8,9个数)
若N的前i-1项构成潜在好数：
num[i] -= 4 - (N[i]前包含2,5,6,9个数)
possible_num[i] -= 3 - (N[i]前包含0,1,8个数)
代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    string s = to_string(n);
    vector<int> num(s.length(), 0), possible_num(s.length(), 0);
    int cnt_num[] = {0, 0, 1, 1, 1, 2, 3, 3, 3, 4};
    int cnt_possible[] = {1, 2, 2, 2, 2, 2, 2, 2, 3, 3};
    int flag = 0;
    num[0] = cnt_num[s[0]-'0'];
    possible_num[0] = cnt_possible[s[0]-'0'];
    for(int i = 1; i < s.length(); ++ i){
        if(flag == 2 || s[i-1] == '3' || s[i-1] == '4' || s[i-1] == '7')
            flag = 2;
        else if(s[i-1] == '2' || s[i-1] == '5' || s[i-1] == '6' || s[i-1] == '9')
            flag = 1;
        else if(s[i-1] == '0' || s[i-1] == '1' || s[i-1] == '8')
            flag == 0;
        if(flag == 1)
            num[i] = cnt_num[s[i]-'0']-4 + cnt_possible[s[i]-'0']-3;
        else if(flag == 0){
            possible_num[i] = cnt_possible[s[i]-'0']-3;
            num[i] = cnt_num[s[i]-'0']-4;
        }
        num[i] += possible_num[i-1]*4 + num[i-1]*7;
        possible_num[i] += possible_num[i-1]*3;
    }
    printf("%d",num[s.length()-1]);
}