2018年全国多校算法寒假训练营练习比赛（第二场） G题送分了QAQ 题解

题目大意：

  大致意思是给两个数n和m，其中n<=m，然后求[n,m]中所有包括“38”或者“4”的数，记录个数。

分析：

  直接枚举的话会超时，坑爹的是第一次在牛客网做比赛，然后TLE提示的是没有通过任何一组数据。。。让我误认为是算法错了，搞了各种Java的玄学。。。

  比赛的时候我用的打表，因为范围是1-1000000，所以只要求出这个范围中所有题意要找的数并预先判断即可。

代码：

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, ans;
	static boolean isBad[] = new boolean[1000005];
	public static void fun() {
		boolean tag = false;
		int len;
		for(int k = 1; k <= 1000000; k++) {
			String s = String.valueOf(k);
			tag = false;
			len = s.length();
			for(int i = 0; i < len; i++) {
				if(s.charAt(i) == '3' && i < len - 1 && s.charAt(i + 1) == '8') {
					tag = true;
					break;
				}
				if(s.charAt(i) == '4') {
					tag = true;
					break;
				}
			}
			if(tag) {
				isBad[k] = true;
			}
		}
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		fun();
		while(true) {
			ans = 0;
			n = in.nextInt();
			m = in.nextInt();
			if(n == 0 && m == 0) {
				break;
			}
			for(int i = n; i <= m; i++) {
				if(isBad[i]) {
					ans++;
				}
			}
			System.out.println(ans);
		}
	}
}