import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Solution4_X游戏 {

    static HashMap<Character, Character> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');
        map.put('2', '5');
        map.put('5', '2');
        map.put('6', '9');
        map.put('9', '6');
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isGoodNum(i)) count++;
        }
        System.out.println(count);
    }

    //自己第一时间写的，相比下面的方法显得有些笨重了...
    private static boolean isGoodNum(int x) {
        String s = String.valueOf(x);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                sb.append(map.get(s.charAt(i)));
            } else {
                return false;
            }
        }
        return x == Integer.parseInt(sb.toString()) ? false : true;
    }


    /**
     * 此法更优，如果数字是 0 1 8，flag不需要变，它序x值相等
     */
    private static boolean isGoodNum1(int x) {
        boolean flag = false;
        int a = 0;
        while (x > 0) {
            a = x % 10;
            if (a == 3 || a == 4 || a == 7) {
                return false;
            } else if (a == 2 || a == 5 || a == 6 || a == 9) {
                flag = true;
            }
            x /= 10;
        }
        return flag;
    }
}

"""
暴力枚举，判断是不是好数
"""
def is_good(s):
    if '3' in s or '4' in s or '7' in s:
        return False
    if '2' in s or '5' in s or '6' in s or '9' in s:
        return True
    return False


if __name__ == "__main__":
    N = int(input().strip())
    ans = 0
    for i in range(1, N + 1):
        if is_good(str(i)):
            ans += 1
    print(ans)

	

	
	

		#include <bits/stdc++.h>
	

	

		using namespace std;
	

	

		bool f(string s){
	

	

		int l = s.length();
	

	

		bool change = false;
	

	

		for(int i=0;i<l;i++){
	

	

		if(s[i]=='2' || s[i]=='5' || s[i]=='6' || s[i]=='9'){
	

	

		change = true;
	

	

		continue;
	

	

		}else if(s[i]=='1' || s[i]=='0' || s[i]=='8')
	

	

		continue;
	

	

		else
	

	

		return false;
	

	

		}
	

	

		if(change)
	

	

		return true;
	

	

		else
	

	

		return false;
	

	

		}
	

	

		int main(){
	

	

		long n, cnt=0;
	

	

		cin>>n;
	

	

		for(long i=1;i<=n;i++){
	

	

		string s = to_string(i);
	

	

		if(f(s))
	

	

		cnt++;
	

	

		}
	

	

		cout<<cnt<<endl;
	

	

		return 0;
	

	

		}
	

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,res=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s=to_string(i);
        if((s.find("3")== string::npos&&s.find("4")== string::npos&&s.find("7")== string::npos)&&(s.find("2")!= string::npos||s.find("5")!= string::npos||s.find("6")!= string::npos||s.find("9")!= string::npos))
            res++;
    }
    cout<<res<<endl;
    return 0;
}

以下是思路代码，没有通过cases，貌似有地方挂掉了
而且事实上这个代码的效率低于暴力穷举……
但我还是把这个贴出来，因为这个思路的正确写法效率可以很高。
以下是错误代码：

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
struct item {
    int nums[10];
};
class Solution {
    public :
    // 入口
    int solve(int n) {
        // 存每一位的数字
        vector<int> mods;
        // 统计有多少位
        int k = get_k(n, mods);
        // 分别对有效数和好数进行dp
        vector<item> dp0;
        vector<item> dp1;
        make_dp(k, dp0, dp1);
        int count = 0;
        // 当某一位确定强有效时变为真
        bool flag = false;
        for(int i=k-1; i>=0; i--) {
            int m = mods[i];
            // 值为1代表强有效，0代表弱有效，-1代表无效
            int u = is_useful(m);
            // 如果前面有一位已经是强有效了，那么后面弱有效就可以了
            if(flag) {
                if(u == -1) {
                    count += dp0[i].nums[m-1];
                    break;
                } else {
                    count += dp0[i].nums[m-1];
                }
            } else {
                if(u == -1) {
                    count += dp1[i].nums[m-1];
                    break;
                } else if(u == 0) {
                    count += dp1[i].nums[m-1];
                } else {
                    count += dp0[i].nums[m-1];
                    flag = true;
                }
            }
        }
        return count;
    }

    void make_dp(int k, vector<item> &dp0, vector<item> &dp1) {
        item item0; int a[] = {1,2,3,3,3,4,5,5,6,7};
        item item1; int b[] = {1,2,3,3,3,4,5,5,6,7};
        memcpy(item0.nums, a, sizeof(a));
        memcpy(item1.nums, b, sizeof(b));
        dp0.push_back(item0);
        dp1.push_back(item1);
        for(int i=1; i<k; i++) {
            item marks0;
            item marks1;
            marks0.nums[0] = pow(7,i);
            marks1.nums[0] = dp1.back().nums[9];
            for(int m=1; m<10; m++) {
                int u = is_useful(m);
                if(u==-1) {
                    marks0.nums[m] = marks0.nums[m-1];
                    marks1.nums[m] = marks1.nums[m-1];
                } else if(u==0) {
                    marks0.nums[m] = marks0.nums[m-1] + marks0.nums[0];
                    marks1.nums[m] = marks1.nums[m-1] + marks1.nums[0];
                } else {
                    marks0.nums[m] = marks0.nums[m-1] + marks0.nums[0];
                    marks1.nums[m] = marks1.nums[m-1] + marks0.nums[0];
                }
            }
            dp0.push_back(marks0);
            dp1.push_back(marks1);
        }
    }

    int is_useful(int m) {
        if(m==3||m==4||m==7) return -1;
        if(m==0||m==1||m==8) return 0;
        return 1;
    }

    int get_k(int n, vector<int> mods) {
        int k=0;
        while(n!=0) {
            mods.push_back(n % 10);
            k++;
            n/=10;
        }
        return k;
    }

    int pow(int x, int p) {
        int r = 1;
        while(p-->0) {
            r*=x;
        }
        return r;
    }
};

int main(void) {
    int n;
    scanf("%d", &n);
    int result = Solution().solve(n);
    printf("%d", result);
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            String str = String.valueOf(i);
            // 包含2、5、6、9中任意个，且不包含3、4、7的即为好数
            if ((str.contains("2") || str.contains("5") || str.contains("6") || str.contains("9")) && (!str.contains("3") && !str.contains("4") && !str.contains("7"))) {
                count++;
            }
        }
        System.out.println(count);
    }
}

#include<bits/stdc++.h>
using namespace std;
inline bool check(int x)
{
    int flag=0;
    while(x)
    {
        int q=x%10;
        x/=10;
        if(q==2||q==5||q==6||q==9)    flag=1;
        else if(q==0||q==1||q==8)    continue;
        else return false;
    }
    if(flag)    return true;
    else    return false;
}
int main()
{
    int n,sum=0;cin>>n;
    for(int i=1;i<=n;i++)
        if(check(i))    sum++;
    cout<<sum;
}

#include<iostream>
using namespace std;
int main(){
    int n,count=0;
    int a,b,m;
    bool effecient=false;
    cin>>n;
    m=n;
    while(m)
    {
        effecient=false;
        while(n)
        {
            a=n/10;
            b=n-a*10;
            if(b==2||b==5||b==6||b==9)
            {
                effecient=true;
            }
            if(b==3||b==7||b==4)
            {
                effecient=false;
                break;
            }
            n=n/10;
        }
        if(effecient)
        count++;
        m--;
        n=m;
    }
    cout<<count;
    return 0;
}

数位DP

先求出所有由0, 1, 2, 5, 6, 8, 9构成的且小于N的数的个数res，这些数是翻转有效的，然后求出所有由0, 1, 8构成的且小于N的数的个数las，这些数是翻转有效而且翻转后等于自己。res-las就是所求的答案。

#include <iostream>
#include <vector>

using namespace std;

int power7(int x)
{
  int res = 1;
  for (int i = 0; i < x; i ++) res *= 7;
  return res;
}

int power3(int x)
{
  int res = 1;
  for (int i = 0; i < x; i ++) res *= 3;
  return res;
}

int main()
{
  int f[7] = {0, 1, 2, 5, 6, 8, 9};
  int g[3] = {0, 1, 8};
  int n;
  cin >> n;
  vector<int> vec;
  while (n)
  {
    vec.push_back(n % 10);
    n /= 10;
  }

  int res = 0;
  int las = 0;

  for (int i = vec.size() - 1; i >=0; i --)
  {
    for (int j = 0; j < 7; j ++)
    {
      int x = f[j];
      if (x < vec[i]) res += power7(i);
    }
    if (vec[i] == 3 || vec[i] == 4 || vec[i] == 7) break;

    if (!i) res ++;
  }

  for (int i = vec.size() - 1; i >= 0; i --)
  {
    for (int j = 0; j < 3; j ++)
    {
      int x = g[j];
      if (x < vec[i]) las += power3(i);
    }
    if (!(vec[i] == 0 || vec[i] == 1 || vec[i] == 8)) break;

    if (!i) las ++;
  }

  cout << res - las << endl;
  return 0;

}