Problem - D - Codeforces

題目：

思路：

數位DP + 數論

題目讓我們求這個無限序列 123456789101112.... 的前 k 個數的數位和

題目看起來很不好求，事實上確實是這樣的

我們可以先從簡單問題開始

問題①. 求 k 位置對應著第幾個數

那么顯然我們很好求出這個數，首先每一位的數都有???個數位，比如兩個位數就有 9 * 10 個數，每一個數都有兩位，那么就是有 9 * 10 * 2 位

因此我們可以不斷計算求出一個 wei，其代表 k 處于有 wei 位數字，那么現在求 k 是其中的第幾個，那么此時一個數要占據 wei?位，所以 k 個數就能往后 k / wei 個數了，但是要注意我們從下標 0?開始數的，因此 k 要減一，防止多計算了

所以 k 處于的數就是?，其中 num 代表往后幾位

那么對于這個數也很好求了，我們直接轉為字符串計算即可

問題②. 計算 1 ~ n 的所有數位和

這個問題我們可以使用數位dp來解決，雖然也能用過其他的遞歸+數學解決，但是練習數位dp也是挺好的

我們定義 f[i] 為第 i 位能所有數的數位和，g[i] 為第 i 位時為能構成的數的數量，然后套板子即可，具體實現看代碼，還是很簡單的

代碼：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());int getans(int n)
{string a = to_string(n);int m = a.size();vector<int> f(m,-1),g(m,-1);auto dfs = [&](auto && self,int now,int lim,int zero)->pair<int,int>{if(now == m){return {0,1};}if(!lim && !zero && f[now] != -1) return {f[now],g[now]};int mx = lim ? (a[now] - '0') : 9;int res = 0,cnt = 0;for (int i = 0; i <= mx; i++){auto [ans,num] = self(self,now+1,lim && i == mx,zero && i == 0);res += ans + num * i;cnt += num;}   if(!lim && !zero){f[now] = res;g[now] = cnt;}return {res,cnt};};return dfs(dfs,0,1,1).first;
}   void solve()
{int k;cin >> k;int wei = 1;while (wei * 9 * pow(10, wei - 1) <= k){k -= wei * 9 * pow(10, wei - 1);wei++;}int num = (k - 1) / wei; // 往后多少個數，減一防止多偏移，如 wei = 2，k = 2，那么此時如果不減則 k / wei = 1，即往后一位，算出來位 11，實際上是 10int n = pow(10, wei - 1) + num;string s = to_string(n);int ans = 0;for (int i = 0; i <= (k - 1) % wei; i++) //(k - 1) % wei 第 n 個數其包含了多少位{ans += s[i] - '0';}ans += getans(n - 1);cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while (t--){solve();}return 0;
}