箱包网站设计,美妆网站开发背景,网站建设行业前景,怎么让网站被收录题目链接
头一回用不是正解的方法做出来#xff0c;也是比较极限#xff0c;直接说做法就是二分数位dp 数位 d p dp dp 求 1 − n 1-n 1−n出现多少含 4 4 4的数字个数 这纯纯板子了 \sout{这纯纯板子了} 这纯纯板子了 设 f ( x ) f(x) f(x) 为 1 − x 1-x 1−x 中含有4的…题目链接
头一回用不是正解的方法做出来也是比较极限直接说做法就是二分数位dp 数位 d p dp dp 求 1 − n 1-n 1−n出现多少含 4 4 4的数字个数 这纯纯板子了 \sout{这纯纯板子了} 这纯纯板子了 设 f ( x ) f(x) f(x) 为 1 − x 1-x 1−x 中含有4的个数 f f f 关于 x x x 单调递增(并非严格) ,题目要找的其实是 x − f ( x ) k x-f(x)k x−f(x)k这样一个解,我们去二分 x x x检查 x − f ( x ) x-f(x) x−f(x) 和 k k k 的大小关系 Specially 我们需要注意 x − f ( x ) x-f(x) x−f(x) 是一个一会儿单调递增一会儿没有增量的一个函数所以我们要找最小的符合上述方程的解
#includebits/stdc.h
using namespace std;
typedef long long i64;
i64 k;
int len,a[20];
i64 dp[20][2][2];i64 dfs(int pos,int limit,int flag){if(poslen) return flag;if(dp[pos][limit][flag]!-1) return dp[pos][limit][flag];int rg limit?a[pos]:9;i64 ans 0;for(int i 0;irg;i){if(i4) ansdfs(pos1,limitirg,1);else ansdfs(pos1,limitirg,flag);}return dp[pos][limit][flag] ans;
}void solve(){cink;i64 l k,r 2e18;while(lr){i64 mid (lr)1;len 0;i64 tmp mid;while(tmp){a[len] tmp%10;tmp/10;}reverse(a,alen);for(int i 0;i20;i){for(int j 0;j2;j){dp[i][j][0]dp[i][j][1]-1;}}i64 t dfs(0,1,0);if(mid-tk) r mid-1;else l mid1;}coutl\n;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t;cint;while(t--) solve();return 0;
}
