题目pdf：
大致题意：求第n个不包含"4"和"13"为子串的数是多少 ， n<= 1e18
思路：就是一般的数位DP，，二分答案，对答案的数求数位DP算出此数以内有多少个满足条件的数
但是….居然答案爆long long，要用unsigned long long 才能过，就这个坑点
// 0 ms 0 KB 2633 B 2015-08-15 01:02:36 //#pragma comment(linker, "/STACK:1024000000,1024000000")#include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#include <string>#include <vector>#include <cstdio>#include <ctime>#include <bitset>#include <algorithm>#define SZ(x) ((int)(x).size())#define ALL(v) (v).begin(), (v).end()#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)#define reveach(i, v) for (__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++ i)#define REP(i,n) for ( int i=1; i<=int(n); i++ )#define rep(i,n) for ( int i=0; i< int(n); i++ )using namespace std;typedef unsigned long long ull;#define X first#define Y secondtypedef pair<int,int> pii;template <class T>inline bool RD(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void PT(T x) {if (x < 0) {putchar('-');x = -x;}if (x > 9) PT(x / 10);putchar(x % 10 + '0');}ull dp[20][3];/* dp[i][0] 不包含4和13 dp[i][1] 不包含4和13最高位为3 dp[i][2] 包含4或13 */int bit[20];ull cal(ull x){ull t = x;int c = 0;while(t){bit[++c] = t%10;t /= 10;}bit[c+1] = 0;ull ans = 0;bool is_13 = 0;for(int p = c; p >= 1; p–){ans += bit[p]*dp[p-1][2];if(is_13) ans += bit[p]*dp[p-1][0];else{if(bit[p] > 4) ans += dp[p-1][0];if(bit[p] > 1) ans += dp[p-1][1];if(bit[p+1] == 1 && bit[p] > 3) ans += dp[p-1][0];if( (bit[p+1] == 1 && bit[p] == 3)||bit[p] == 4)is_13 = 1;}}return x-ans;}int main(){dp[0][0] = 1;REP(i,18){dp[i][0] = dp[i-1][0]*9-dp[i-1][1];dp[i][1] = dp[i-1][0];dp[i][2] = dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];}ull n;while(RD(n)){ull lb = 0,ub = (ull)1000000000000000000*18;while(ub-lb > 1){ull mid = lb/2 + ub/2 + ((lb&1)+(ub&1))/2;if(cal(mid) <= n) lb = mid;else ub = mid;}PT(lb);puts("");}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
往事是尘封在记忆中的梦，而你是我唯一鲜明的记忆，
