首页 > 代码库 > bzoj1833
bzoj1833
http://www.lydsy.com/JudgeOnline/problem.php?id=1833
2.5个小时就花在这上面了。。。
水到200题了。。。然并卵,天天做水题有什么前途。。。
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll A, B; ll dp[20][20][20], a[20], ret[20], ans[20], bin[20]; void solve(ll n, int f) { int len = 0; ll t = n; memset(a, 0, sizeof(a)); memset(ret, 0, sizeof(ret)); while(n) a[++len] = n % 10, n /= 10; for(int i = 1; i < len; ++i) for(int j = 1; j <= 9; ++j) for(int k = 0; k <= 9; ++k) ret[k] += dp[i][j][k]; // for(int i = 1; i < a[len]; ++i) // for(int j = 0; j <= 9; ++j) ret[j] += dp[len][i][j]; for(int i = len; i; --i) { for(int j = 0; j < a[i]; ++j) { if(!j && i == len) continue; for(int k = 0; k <= 9; ++k) ret[k] += dp[i][j][k]; } ret[a[i]] += t % bin[i] + 1; } for(int i = 0; i <= 9; ++i) ans[i] += f * ret[i]; } int main() { // freopen("countzj.in", "r", stdin); // freopen("countzj.out", "w", stdout); bin[1] = 1ll; for(int i = 2; i <= 13; ++i) bin[i] = bin[i - 1] * 10ll; for(int i = 0; i <= 9; ++i) dp[1][i][i] = 1; for(int i = 2; i <= 13; ++i) for(int j = 0; j <= 9; ++j) for(int k = 0; k <= 9; ++k) for(int l = 0; l <= 9; ++l) dp[i][j][l] += dp[i - 1][k][l] + (ll)(j == l) * bin[i - 1]; scanf("%lld%lld", &A, &B); solve(B, 1); solve(A - 1, -1); for(int i = 0; i <= 8; ++i) printf("%lld ", ans[i]); printf("%lld\n", ans[9]); // fclose(stdin); fclose(stdout); return 0; }
bzoj1833
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。