題目連結:https://vjudge.net/problem/HDU-4352
題目大意:
給你一個區間[l,r],讓你求這個區間内符合條件的數的個數。
條件:這個數的數位上的LIS的長度等于k。
題解:
一道很好的題目,需要知道怎麼O(nlogn)求LIS,這樣在才能進行狀态轉移。
如果不懂怎麼O(nlogn)求LIS,可以看下我的的部落格:https://blog.csdn.net/qq_43472263/article/details/105084063
然後知道怎麼求之後我們可以考慮用一個9位的二進制數state表示(1,2,...9)哪些數字出現了。
舉個例子:110110000,其中1,2,4,5出現,其中1表示長度為1的上升序列的最小最末元素(類比d數組),
4表示長度為3(前面有3個1,包括自己)的上升序列的最小最末元素,2和5的定義也一樣。
在轉移狀态時,就需要根據上一個狀态和目前數位的值更新狀态就行了,
類比O(nlogn)的更新方法:如果前面沒有比他大的,就直接插入,否則把前面比他大的第一個元素改成它。
最後LIS的長度就是狀态state中的1的個數,其實也就是最後的d數組長度。
代碼實作:
#pragma GCC optimize(2) #include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <set> #include <stack> #include <queue> #define PI atan(1.0) * 4 #define E 2.718281828 #define rp(i, s, t) for (register int i = (s); i <= (t); i++) #define RP(i, t, s) for (register int i = (t); i >= (s); i--) #define ll long long #define ull unsigned long long #define mst(a, b) memset(a, b, sizeof(a)) #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define pii pair<int, int> #define mp make_pair #define pb push_back #define debug printf("ac\n"); using namespace std; inline int read() { int a = 0, b = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') b = -1; c = getchar(); } while (c >= '0' && c <= '9') { a = (a << 3) + (a << 1) + c - '0'; c = getchar(); } return a * b; } int a[20],num,k; ll dp[20][1<<10][10]; int getnew(int x,int s){//類比O(nlogn)維護d數組的操作 rp(i,x,9) if(s&(1<<i))//如果[x,9]有數出現,那麼就出現的數的位置變成0(s^(1<<i)),然後再把第x位變成1(state(|1<<x)) return (s^(1<<i))|(1<<x); return s|(1<<x);//如果沒有數出現,證明目前數比之前的數都大,直接插入,把第x位變為1(s|(1<<x)) } int getnum(int x){//求狀态中1的個數 int res=0; while(x){ if(x&1) res++; x>>=1; } return res; } ll dfs(int pos,int state,int k,int lead,int limit){ if(pos==-1) return getnum(state)==k; if(!lead&&!limit&&dp[pos][state][k]!=-1) return dp[pos][state][k]; int up=limit?a[pos]:9; ll ans=0; rp(i,0,up){ ans+=dfs(pos-1,(lead&&i==0)?0:getnew(i,state),k,lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead) return dp[pos][state][k]=ans; return ans; } ll solve(ll x){ num=0; while(x) a[num++]=x%10,x/=10; return dfs(num-1,0,k,1,1); } int main(){ mst(dp,-1); ll l,r; int T=read(); int kcase=0; while(T--){ scanf("%lld%lld%d",&l,&r,&k); printf("Case #%d: %lld\n",++kcase,solve(r)-solve(l-1)); } return 0; }