這一次有題解了！！

• T1：CF54C First Digit Law
• • title
  • solution
  • code
• T2：CF509C Sums of Digits
• • title
  • solution
  • code
• T3：CF431D Random Task
• • title
  • solution
  • code
• T4：CF628D Magic Numbers
• • title
  • solution
  • code
• T5：CF855E Salazar Slytherin's Locket
• • title
  • solution
  • code
• T6：CF1245F Daniel and Spring Cleaning
• • title
  • solution
  • code
• T7：CF95D Horse Races
• • title
  • code

T1：CF54C First Digit Law

title

solution

這個(gè)題目是真的繞！！
其次本題是數(shù)位$dp$，概率$dp$，背包的結(jié)合

對(duì)于數(shù)位$dp$板塊，其實(shí)我是沒有寫的，因?yàn)橛煤?jiǎn)單的組合數(shù)就可以代替，顯然

如果這個(gè)數(shù)長(zhǎng)成$1??????$，那么如果位數(shù)小于這個(gè)數(shù)的就是可以亂填出$1$的，
然后再加上$1000000?1??????$中的個(gè)數(shù)就好了

如果這個(gè)數(shù)長(zhǎng)成$(>1)??????$，那只要位數(shù)小于等于這個(gè)數(shù)都可以亂填

然后以取的區(qū)間個(gè)數(shù)作為重量，概率作為價(jià)值，乘號(hào)轉(zhuǎn)移，然后自己領(lǐng)悟吧

code

#include <cstdio> #define ll long long int n, k; double dp[1100], p[1100];ll solve( ll num ) {ll cnt = 0, last = 0, Pow = 1, ans = 0, x = num;while( x ) {last = x % 10;cnt ++;x /= 10;}for( int i = 1;i < cnt;i ++, Pow *= 10 )ans += Pow;if( last > 1 ) ans += Pow;else if( last == 1 ) ans += num - Pow + 1;return ans; }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) {ll l, r;scanf( "%I64d %I64d", &l, &r );ll temp = solve( r ) - solve( l - 1 );p[i] = temp * 1.0 / ( r - l + 1 );}scanf( "%d", &k );dp[0] = 1.0;for( int i = 1;i <= n;i ++ )for( int j = n;~ j;j -- ) {dp[j] = dp[j] * ( 1 - p[i] );if( j > 0 ) dp[j] += dp[j - 1] * p[i];}double ans = 0;for( int i = 0;i <= n;i ++ )if( i * 100 >= n * k )ans += dp[i];printf( "%.12lf", ans );return 0; }

T2：CF509C Sums of Digits

title

solution

我們想一下怎么才能構(gòu)造出最小的？顯然
從低到高位開始填，一直填$9$，到首位的時(shí)候就填剩下的那個(gè)數(shù)$r$
因?yàn)?strong>數(shù)的大小首先是位數(shù)，其次是位數(shù)上的值！

---

第一個(gè)數(shù)肯定這樣構(gòu)造出來(lái)最小
接下來(lái)我們考慮后續(xù)數(shù)怎么構(gòu)造出來(lái)
只有三種填法

①：仿照第一個(gè)數(shù)，也是后面全填$9$，首位填剩的
②：在前一個(gè)構(gòu)造出來(lái)的數(shù)上的首位$+1$，這樣保證大于后，后面就亂填
③：在前一個(gè)構(gòu)造出來(lái)的數(shù)上的任意一位增加至$9$，直到滿足數(shù)位和相等才停
顯然，從低位往高位填是最小的

code

#include <cstdio> int n, len; int b[400], a[400];void solve( int num ) {for( int i = 1;num;i ++ ) {while( a[i] < 9 && num )a[i] ++, num --;if( i > len && ! num ) len = i;} }void print() {for( int i = len;i;i -- )printf( "%d", a[i] );printf( "\n" ); }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ )scanf( "%d", &b[i] );solve( b[1] );print();for( int i = 2;i <= n;i ++ ) {int temp = b[i] - b[i - 1];if( temp > 0 ) {solve( temp );print();}else {int k = 1;while( 1 ) {if( k > len ) len = k;if( a[k] < 9 && temp > 0 ) {a[k] ++;solve( temp - 1 );print();break;}temp += a[k];a[k] = 0;k ++;}}}return 0; }

T3：CF431D Random Task

title

solution

首先看$n$的范圍$[1,1e18]$我們想要把這個(gè)降下來(lái)，唯一支持的時(shí)間復(fù)雜度就是$logN$
自然而然就會(huì)想到去二分答案$n$
但是二分必須要保證單調(diào)性，現(xiàn)在我們來(lái)證明一下n越大，二進(jìn)制中有k個(gè)1的個(gè)數(shù)一定變大或不變

假設(shè)當(dāng)前二分的答案為$n$
那么計(jì)算范圍就是$[n+1,2n]$
對(duì)于$n+1$而言，我們主觀是認(rèn)為$n+1$一定不劣于$n$，有時(shí)候我們的主觀是正確的
$n+1$計(jì)算范圍為$[n+2,2n+2]$

分別把區(qū)間劃分一下
$[n+1,2n]=n+1,[n+2,2n]$
$[n+2,2n+2]=[n+2,2n],2n+1,2n+2$
發(fā)現(xiàn)$[n+2,2n]$可以抵消
$n+1,2n+2$也可以抵消！！

這個(gè)時(shí)候巧妙轉(zhuǎn)化為二進(jìn)制思考

$2n+2$是$n+1$的兩倍，也就相當(dāng)于$2n+2=(n+1)<<1$
二進(jìn)制左移以為不就相當(dāng)補(bǔ)了一個(gè)$0$，那么前面兩個(gè)數(shù)中二進(jìn)制含有$1$的個(gè)數(shù)是不變的！！
所以也可以抵消

此時(shí)$[n+1,2n+2]$就還剩下一個(gè)$2n+1$，所以一定不劣于，證畢

所以為什么題目是$[n+1,2n]$范圍，如果是$[n,2n]$就不好說(shuō)了，而且要求必須恰好為$m$不能大于

---

好了接下來(lái)，就是普通的數(shù)位$dp$了，先把套路搞起來(lái)
把$[l,r]$轉(zhuǎn)化為$[1,r]?[1,l?1]$
然后用二進(jìn)制數(shù)位$dp$
就是控制前$i$位相等，然后后面亂填，這里不再贅述（你看代碼就會(huì)馬上get）

code

#include <cstdio> #include <cstring> #define ll long long ll m; int k, num[100]; ll dp[100][100];ll dfs( int pos, int sum, bool lim ) {if( ! pos ) return ( sum == k );if( ! lim && dp[pos][sum] != -1 ) return dp[pos][sum];int up = lim ? num[pos] : 1;ll ans = 0;for( int i = 0;i <= up;i ++ ) if( sum + ( i == 1 ) <= k )ans += dfs( pos - 1, sum + ( i == 1 ), lim && ( i == up ) );if( ! lim ) dp[pos][sum] = ans;return ans; }ll solve( ll x ) {int len = 0;while( x ) num[++ len] = x & 1, x >>= 1;return dfs( len, 0, 1 ); }ll calc( ll x ) {return solve( x << 1 ) - solve( x ); }int main() {scanf( "%lld %d", &m, &k );memset( dp, -1, sizeof( dp ) );ll l = 1, r = 1e18;while( l <= r ) {ll mid = ( l + r ) >> 1, ans = calc( mid );if( ans == m ) return ! printf( "%lld", mid );else if( ans > m ) r = mid - 1;else l = mid + 1;}return 0; }

T4：CF628D Magic Numbers

title

solution

這是道中規(guī)中矩的數(shù)位$DP$題目，只不過(guò)設(shè)計(jì)了一丁點(diǎn)的高精
按照套路我們會(huì)轉(zhuǎn)化成$[1,r]?[1,l?1]$，但是$l?1$涉及高精減，所以我們就單獨(dú)拎出來(lái)
寫一個(gè)$check$專門判斷$l$是否符合，然后差分計(jì)算$[1,r]?[1,l]$

注意，題目翻譯是錯(cuò)誤的
是從高位到低位（從左往右）首位是奇數(shù)，然后偶數(shù)位，奇數(shù)位，偶數(shù)位

這種看代碼就會(huì)秒懂的，不展開敘述

code

#include <cstdio> #include <cstring> #define mod 1000000007 #define ll long long int m, d, len; ll ans; int num[2005]; char l[2005], r[2005]; ll dp[2005][2005];ll dfs( int pos, int sum, bool lim ) {if( pos == -1 ) return ( sum == 0 );if( ! lim && ~ dp[pos][sum] ) return dp[pos][sum];int up = lim ? num[pos] : 9;ll ans = 0;for( int i = 0;i <= up;i ++ ) {if( ( ( len - pos ) & 1 ) && i == d ) continue;if( ( ! ( ( len - pos ) & 1 ) ) && i != d ) continue;ans = ( ans + dfs( pos - 1, ( sum * 10 + i ) % m, lim && ( i == up ) ) ) % mod;}if( ! lim ) dp[pos][sum] = ans;return ans; }ll calc( char *x ) {len = strlen( x );for( int i = 0;i < len;i ++ )num[len - i - 1] = x[i] - '0';return dfs( len - 1, 0, 1 ); }bool check() {len = strlen( l );ll sum = 0;for( int i = 0;i < len;i ++ ) {int j = l[i] - '0';if( ( ( i + 1 ) & 1 ) && j == d ) return 0;if( ( ! ( ( i + 1 ) & 1 ) ) && j != d ) return 0;sum = ( sum * 10 + j ) % m;}return ( sum == 0 ); }int main() {memset( dp, -1, sizeof( dp ) );scanf( "%d %d %s %s", &m, &d, l, r );ans = ( calc( r ) - calc( l ) + mod ) % mod;ans += check();printf( "%lld", ans % mod );return 0; }

T5：CF855E Salazar Slytherin’s Locket

title

solution

這個(gè)也是很簡(jiǎn)單的數(shù)位$DP$，只不過(guò)中間我們套一個(gè)狀壓$DP$
如果狀態(tài)$s$的第$i$位為$0$，表示數(shù)字$i$出現(xiàn)了偶數(shù)次，反之出現(xiàn)奇數(shù)次
轉(zhuǎn)化成$b$進(jìn)制直接搞就行了唄

code

#include <cstdio> #include <cstring> #define ll long long int Q, b; int num[70]; ll l, r; ll dp[12][70][( 1 << 11 ) - 1];ll dfs( int pos, int s, bool zero, bool lim ) {if( !pos ) return !s;if( ~dp[b][pos][s] && !zero && !lim ) return dp[b][pos][s];int up = lim ? num[pos] : b - 1;ll ans = 0;for( int i = 0;i <= up;i ++ )ans += dfs( pos - 1, ( !i && zero ) ? s : s ^ ( 1 << i ), zero && !i, lim && ( i == up ) );if( !zero && !lim ) dp[b][pos][s] = ans;return ans; }ll solve( ll x ) {int len = 0;while( x ) num[++ len] = x % b, x /= b;return dfs( len, 0, 1, 1 ); }int main() {memset( dp, -1, sizeof( dp ) );scanf( "%d", &Q );while( Q -- ) {scanf( "%d %lld %lld", &b, &l, &r );printf( "%lld\n", solve( r ) - solve( l - 1 ) );}return 0; }

T6：CF1245F Daniel and Spring Cleaning

title

solution

異或可以轉(zhuǎn)化成二進(jìn)制下不進(jìn)位加法
樸素?cái)?shù)位$DP$直接上

code

#include <cmath> #include <cstdio> #include <cstring> #define ll long long int T, L, R; ll dp[40][2][2];ll dfs( int pos, bool limL, bool limR ) {if( pos == -1 ) return 1;if( ~ dp[pos][limL][limR] ) return dp[pos][limL][limR];dp[pos][limL][limR] = 0;int upL = limL ? ( L >> pos ) & 1 : 1;int upR = limR ? ( R >> pos ) & 1 : 1;for( int i = 0;i <= upL;i ++ )for( int j = 0;j <= upR;j ++ )if( ! ( i & j ) )dp[pos][limL][limR] += dfs( pos - 1, limL && ( i == upL ), limR && ( j == upR ) );return dp[pos][limL][limR]; }ll solve( int l, int r ) {if( l == -1 ) return 0;memset( dp, -1, sizeof( dp ) );L = l, R = r;dfs( log2( R + 1 ) + 1, 1, 1 ); }int main() {scanf( "%d", &T );while( T -- ) {int l, r;scanf( "%d %d", &l, &r );printf( "%lld\n", solve( r, r ) - solve( l - 1, r ) * 2 + solve( l - 1, l - 1 ) );}return 0; }

T7：CF95D Horse Races

title

code

直接看代碼即可

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define mod 1000000007 #define ll long long int T, k; int num[1005]; char l[1005], r[1005]; ll dp[1005][1005][2]; //pos表示當(dāng)前位置 //d表示k+1減去與前一個(gè)幸運(yùn)數(shù)字的距離 //那么當(dāng)d降到0時(shí)，它與前面的幸運(yùn)數(shù)字的距離就超過(guò)k了 //flag表示之前是否符合要求，符合要求為1，不符合為0 //lim表示當(dāng)前位能否取到9，即之前是否達(dá)到上界，達(dá)到上界就為1，沒有就為0 ll dfs( int pos, int d, bool flag, bool lim ) {if( ! pos ) return flag;if( ! lim && ~ dp[pos][d][flag] ) return dp[pos][d][flag];int up = lim ? num[pos] : 9;ll ans = 0;for( int i = 0;i <= up;i ++ ) {if( i != 4 && i != 7 )ans = ( ans + dfs( pos - 1, max( d - 1, 0 ), flag, lim && ( i == up ) ) ) % mod;elseans = ( ans + dfs( pos - 1, k, flag || d, lim && ( i == up ) ) ) % mod;}if( ! lim ) dp[pos][d][flag] = ans;return ans; }ll calc( char *x ) {int len = strlen( x );for( int i = len - 1;i >= 0;i -- )num[len - i] = x[i] - '0';return dfs( len, 0, 0, 1 ); }bool check() {int len = strlen( l ), last = 0x3f3f3f3f;for( int i = len - 1;~ i;i -- ) {int j = l[i] - '0';if( j == 4 || j == 7 ) {if( last - i <= k ) return 1;else last = i;}}return 0; }int main() {memset( dp, -1, sizeof( dp ) );scanf( "%d %d", &T, &k );while( T -- ) {scanf( "%s %s", l, r );printf( "%lld\n", ( calc( r ) - calc( l ) + check() + mod ) % mod );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【数位DP】CF 54C，509C，431D，628D，855E，1245F，95D的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。