1 条题解

  • 0
    @ 2024-12-24 9:49:41

    C++ :

    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    
    typedef long long ll;
    
    ll dp[20][20][20][20];
    ll l,r;
    int num[20],len;
    
    
    inline ll dfs(int i,int s,int p,int q,bool e,bool pre){
        if(i==-1){
            if(s<=1) return 1;
            return 0;
        }
        if(!e && dp[i][s][p][q]!=-1) return dp[i][s][p][q];
        int v=(e?num[i]:9);
        ll ans=0;
        for(int j=0;j<=v;j++){
            int news=s;
            if(j!=4&&j!=7){
                if(j!=0||(!pre&&j==0))
                    news++;
            }
            ans+=dfs(i-1,news,p+(j==4),q+(j==7),e&&(j==v),(j==0&&pre));
        }
        if(!e) dp[i][s][p][q]=ans;
        return ans;
    }
    inline ll solve(ll n){
        if(n<0) return 0;
        if(n==0) return 1;
        len=0;
        while(n){
            num[len++]=n%10;
            n/=10;
        }
        //for(int i=0;i<len;i++) printf("%d z\n",num[i]);
        return dfs(len-1,0,0,0,1,1);
    }
    
    int gao(ll w){
        int a=0;
        while(w){
            int b=w%10;
            w/=10;
            if(b!=4&&b!=7) a++;
        }
        return a;
    }
    int main(){
    
        memset(dp,-1,sizeof(dp));
        int ans=0;
       // printf("%d z\n",ans);
        while(~scanf("%lld%lld",&l,&r)){
                printf("%lld\n",solve(r)-solve(l-1));
        }
        return 0;
    }
    
    

    Java :

    import java.io.*;
    import java.math.*;
    import java.util.*;
    
    public class Main {
    	static long a, b, tmp;
    	static int cnt;
    
    	static void dfs(long n, boolean has) {
    		if (n > a)
    			return;
    		if (n >= b && n <= a)
    			cnt++;
    		dfs(n * 10 + 4, has);
    		dfs(n * 10 + 7, has);
    		if (has)
    			for (int i = (n == 0 ? 1 : 0); i <= 9; i++) {
    				if (i == 4 || i == 7)
    					continue;
    				dfs(n * 10 + i, false);
    			}
    	}
    
    	public static void main(String[] args) {
    		InputReader cin = new InputReader(System.in);
    		OutputWriter out = new OutputWriter(System.out);
    		while (cin.hasNext()) {
    			a = cin.nextLong();
    			b = cin.nextLong();
    			if (a < b) {
    				tmp = a;
    				a = b;
    				b = tmp;
    			}
    			cnt = 0;
    			dfs(0, true);
    			out.println(cnt);
    		}
          	out.close();
    	}
    }
    
    class InputReader {
    	private boolean finished = false;
    
    	private InputStream stream;
    	private byte[] buf = new byte[1024];
    	private int curChar;
    	private int numChars;
    	private SpaceCharFilter filter;
    
    	public InputReader(InputStream stream) {
    		this.stream = stream;
    	}
    
    	public int read() {
    		if (numChars == -1)
    			throw new InputMismatchException();
    		if (curChar >= numChars) {
    			curChar = 0;
    			try {
    				numChars = stream.read(buf);
    			} catch (IOException e) {
    				throw new InputMismatchException();
    			}
    			if (numChars <= 0)
    				return -1;
    		}
    		return buf[curChar++];
    	}
    
    	public int peek() {
    		if (numChars == -1)
    			return -1;
    		if (curChar >= numChars) {
    			curChar = 0;
    			try {
    				numChars = stream.read(buf);
    			} catch (IOException e) {
    				return -1;
    			}
    			if (numChars <= 0)
    				return -1;
    		}
    		return buf[curChar];
    	}
    
    	public int nextInt() {
    		int c = read();
    		while (isSpaceChar(c))
    			c = read();
    		int sgn = 1;
    		if (c == '-') {
    			sgn = -1;
    			c = read();
    		}
    		int res = 0;
    		do {
    			if (c < '0' || c > '9')
    				throw new InputMismatchException();
    			res *= 10;
    			res += c - '0';
    			c = read();
    		} while (!isSpaceChar(c));
    		return res * sgn;
    	}
    
    	public long nextLong() {
    		int c = read();
    		while (isSpaceChar(c))
    			c = read();
    		int sgn = 1;
    		if (c == '-') {
    			sgn = -1;
    			c = read();
    		}
    		long res = 0;
    		do {
    			if (c < '0' || c > '9')
    				throw new InputMismatchException();
    			res *= 10;
    			res += c - '0';
    			c = read();
    		} while (!isSpaceChar(c));
    		return res * sgn;
    	}
    
    	public String nextString() {
    		int c = read();
    		while (isSpaceChar(c))
    			c = read();
    		StringBuilder res = new StringBuilder();
    		do {
    			res.appendCodePoint(c);
    			c = read();
    		} while (!isSpaceChar(c));
    		return res.toString();
    	}
    
    	public boolean isSpaceChar(int c) {
    		if (filter != null)
    			return filter.isSpaceChar(c);
    		return isWhitespace(c);
    	}
    
    	public static boolean isWhitespace(int c) {
    		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    	}
    
    	private String readLine0() {
    		StringBuilder buf = new StringBuilder();
    		int c = read();
    		while (c != '\n' && c != -1) {
    			if (c != '\r')
    				buf.appendCodePoint(c);
    			c = read();
    		}
    		return buf.toString();
    	}
    
    	public String nextLine() {
    		String s = readLine0();
    		while (s.trim().length() == 0)
    			s = readLine0();
    		return s;
    	}
    
    	public String nextLine(boolean ignoreEmptyLines) {
    		if (ignoreEmptyLines)
    			return nextLine();
    		else
    			return readLine0();
    	}
    
    	public BigInteger nextBigInteger() {
    		try {
    			return new BigInteger(nextString());
    		} catch (NumberFormatException e) {
    			throw new InputMismatchException();
    		}
    	}
    
    	public char nextCharacter() {
    		int c = read();
    		while (isSpaceChar(c))
    			c = read();
    		return (char) c;
    	}
    
    	public double nextDouble() {
    		int c = read();
    		while (isSpaceChar(c))
    			c = read();
    		int sgn = 1;
    		if (c == '-') {
    			sgn = -1;
    			c = read();
    		}
    		double res = 0;
    		while (!isSpaceChar(c) && c != '.') {
    			if (c == 'e' || c == 'E')
    				return res * Math.pow(10, nextInt());
    			if (c < '0' || c > '9')
    				throw new InputMismatchException();
    			res *= 10;
    			res += c - '0';
    			c = read();
    		}
    		if (c == '.') {
    			c = read();
    			double m = 1;
    			while (!isSpaceChar(c)) {
    				if (c == 'e' || c == 'E')
    					return res * Math.pow(10, nextInt());
    				if (c < '0' || c > '9')
    					throw new InputMismatchException();
    				m /= 10;
    				res += (c - '0') * m;
    				c = read();
    			}
    		}
    		return res * sgn;
    	}
    
    	public boolean isExhausted() {
    		int value;
    		while (isSpaceChar(value = peek()) && value != -1)
    			read();
    		return value == -1;
    	}
    
    	public boolean hasNext() {
    		return !isExhausted();
    	}
    
    	public String next() {
    		return nextString();
    	}
    
    	public SpaceCharFilter getFilter() {
    		return filter;
    	}
    
    	public void setFilter(SpaceCharFilter filter) {
    		this.filter = filter;
    	}
    
    	public interface SpaceCharFilter {
    		public boolean isSpaceChar(int ch);
    	}
    }
    
    class OutputWriter {
    	private final PrintWriter writer;
    
    	public OutputWriter(OutputStream outputStream) {
    		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
    				outputStream)));
    	}
    
    	public OutputWriter(Writer writer) {
    		this.writer = new PrintWriter(writer);
    	}
    
    	public void print(Object... objects) {
    		for (int i = 0; i < objects.length; i++) {
    			if (i != 0)
    				writer.print(' ');
    			writer.print(objects[i]);
    		}
    	}
    
    	public void print(int[] array) {
    		for (int i = 0; i < array.length; i++) {
    			if (i != 0)
    				writer.print(' ');
    			writer.print(array[i]);
    		}
    	}
    
    	public void print(long[] array) {
    		for (int i = 0; i < array.length; i++) {
    			if (i != 0)
    				writer.print(' ');
    			writer.print(array[i]);
    		}
    	}
    
    	public void printLine(int[] array) {
    		print(array);
    		writer.println();
    	}
    
    	public void printLine(long[] array) {
    		print(array);
    		writer.println();
    	}
    
    	public void printLine() {
    		writer.println();
    	}
    
    	public void printLine(Object... objects) {
    		print(objects);
    		writer.println();
    	}
    
    	public void print(char i) {
    		writer.print(i);
    	}
    
    	public void printLine(char[] array) {
    		writer.println(array);
    	}
    
    	public void printFormat(String format, Object... objects) {
    		writer.printf(format, objects);
    	}
    
    	public void println(Object... objects) {
    		print(objects);
    		writer.println();
    	}
    
    	public void println() {
    		writer.println();
    	}
    
    	public void printf(String format, Object... args) {
    		writer.printf(format, args);
    	}
    
    	public void close() {
    		writer.close();
    	}
    
    	public void flush() {
    		writer.flush();
    	}
    }
    
    
    • 1

    信息

    ID
    986
    时间
    3000ms
    内存
    128MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者