---

title: 牛客練習賽34 E little w and Digital Root(數位dp)
date: 2018-12-17 22:38:37
tags: 數位dp
categories：ACM

題目鏈接

題目描述

數根(又稱數字根Digital root)是正整數的一種性質，換句話說，每個正整數都有一個數根。 數根是將一正整數的各個位數相加(即橫向相加)，若加完后的值大于等于10的話，則繼續將各位數進行橫向相加直到其值小于十為止，或是，將一數字重復做數字和，直到其值小于十為止，則所得的值為該數的數根。

比如：12345->15->6。

小w現在定義一種叫做小w數根運算，這種運算的規則如下： 首先對十進制數的每個數位定義了一個權值，個位為1，十位為2，百位為3，千位為4，萬為為5…以此類推 接下來把這個數的各個位數乘以該數位的權值再相加求和，若加完后的值大于等于10的話，則重復此過程，直到整個數字小于10為止，所得的值為小w數根。 現在小w想知道給定一個值域L,R，請你告訴他，值域范圍內有多少個數字的小w數根等于1,2,3,4,5,6,7,8,9。

輸入描述:

第一行輸入一個正整數T(T<=10^4)，表示樣例的組數。對于每組案例： 輸入兩個正整數L,R(1<=L<=R<=1000000000000000000)

輸出描述:

對于每組案例，請先輸出Case #x:，x表示當前樣例編號。
然后在同一行輸出9個整數，分別表示值域內小w數根等于1,2,3,4,5,6,7,8,9的數各有多少個。 整數之間用空格隔開，行末不允許有多余空格。

輸入

10 1 10 2 55 36 78 15 15 3 59 56 77 89 93 90 90 55 99 1 99

輸出

Case #1: 1 2 1 1 1 1 1 1 1 Case #2: 0 7 7 7 7 7 7 6 6 Case #3: 0 5 5 6 6 6 5 5 5 Case #4: 0 0 0 0 0 0 1 0 0 Case #5: 0 7 8 7 7 7 7 7 7 Case #6: 0 3 3 3 3 2 2 3 3 Case #7: 0 1 1 1 1 0 0 0 1 Case #8: 0 1 0 0 0 0 0 0 0 Case #9: 0 6 6 5 5 5 6 6 6 Case #10: 1 13 13 12 12 12 12 12 12

思路

• 最大的數根：999999999999999999 -> 1539，小于1600。
• 可以用數位dp模擬，dp[i][j][k], i < 1600 表示數根，j < 20 表示位數，k < 10表示（1-9）的數根

#include <bits/stdc++.h>#define LL long long#define P pair<int, int>#define lowbit(x) (x & -x)#define mem(a, b) memset(a, b, sizeof(a))#define REP(i, n) for (int i = 1; i <= (n); ++i)#define rep(i, n) for (int i = 0; i < (n); ++i)#define N 206using namespace std;int num[20];LL dp[1600][20][10];int judge(int sta, int tar) {int sum = 0;int pos = 1;while (sta) {sum += pos * (sta % 10);sta /= 10;++pos;}if (sum < 10) return sum == tar;else return judge(sum, tar);}LL dfs(int sta, int pos, int tar, int limit) {if (pos == 0) return judge(sta, tar);if (!limit && dp[sta][pos][tar] != -1) return dp[sta][pos][tar];LL sum = 0;int up = limit ? num[pos] : 9;rep(i, up + 1) {sum += dfs(sta+pos*i, pos-1, tar, limit&&(i == up));}if (!limit) dp[sta][pos][tar] = sum;return sum;}LL solve(LL x, int tar) {int len = 0;while (x) {num[++len] = x % 10;x /= 10;}return dfs(0, len, tar, 1);}int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endifint T, kase = 1;scanf("%d", &T);mem(dp, -1);while (T--) {printf("Case #%d:", kase++);LL l, r;scanf("%lld%lld", &l, &r);REP(i, 9) {printf(" %lld", solve(r, i) - solve(l-1, i));}puts("");}return 0;}

總結

以上是生活随笔為你收集整理的牛客练习赛34 E little w and Digital Root(数位dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。