題目鏈接：點擊查看

題目大意：定義 $3?friendly$ 數(shù)字為，將十進制的數(shù)字 $x$ 轉(zhuǎn)換為字符串后，存在一個子串所代表的數(shù)字，可以被 $3$ 所整除，求區(qū)間 $[L,R]$ 內(nèi)的 $3?friendly$ 數(shù)字的個數(shù)

題目分析：當思維題來做的話，就是大于 $100$ 的數(shù)字一定是 $3?friendly$ 數(shù)字，證明的話也很簡單，因為十進制下長度大于等于 $3$ 的數(shù)字轉(zhuǎn)換為字符串有三個前綴和，根據(jù)鴿巢原理一定存在著一個子串的 $sum=0$，證畢

如果用數(shù)位 dp 去實現(xiàn)的話確實也是個裸題，但是涉及到了前導(dǎo)零的特判，所以記錄一發(fā)數(shù)位 dp 的解法

注意，因為是多組樣例，每個樣例的 $limit$ 所代表的上限可能各不相同，所以 $limit=true$ 的時候應(yīng)該爆搜而不應(yīng)該記憶化

代碼：

// Problem: Find 3-friendly Integers // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11166/F // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int b[20]; LL dp[20][2][3][3][3][2]; LL dfs(int pos,int s0,int s1,int s2,int sum,int limit,int lead) {if(pos==-1) {return s0==1||s1==2||s2==2;}if(!limit&&dp[pos][s0][s1][s2][sum][lead]!=-1) {return dp[pos][s0][s1][s2][sum][lead];}int up=limit?b[pos]:9;LL ans=0;for(int i=0;i<=up;i++) {if(lead&&i==0) {ans+=dfs(pos-1,s0,s1,s2,sum,limit&&i==up,1);continue;}int nsum=(sum+i)%3;if(nsum==0) {ans+=dfs(pos-1,min(s0+1,1),s1,s2,nsum,limit&&i==up,lead&&i==0);} else if(nsum==1) {ans+=dfs(pos-1,s0,min(s1+1,2),s2,nsum,limit&&i==up,lead&&i==0);} else if(nsum==2) {ans+=dfs(pos-1,s0,s1,min(s2+1,2),nsum,limit&&i==up,lead&&i==0);}}if(!limit) {dp[pos][s0][s1][s2][sum][lead]=ans;}return ans; } LL solve(LL x) {int cnt=0;while(x) {b[cnt++]=x%10;x/=10;}return dfs(cnt-1,0,0,0,0,1,1); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);memset(dp,-1,sizeof(dp));int w;cin>>w;while(w--) {LL l,r;read(l),read(r);write(solve(r)-solve(l-1)),putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021牛客多校1 - Find 3-friendly Integers(数位dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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