C++(g++ 7.5.0) 解法, 执行用时: 3123ms, 内存消耗: 2228K, 提交时间: 2022-09-09 20:00:44

#include <bits/stdc++.h>
using namespace std;
using LL = unsigned long long;
constexpr LL mod = 1000000007;
LL solve(LL x) {
    auto f = [&](LL x) {
        auto sx = to_string(x);
        LL p = 1, ans = 1;
        for (int i = 1; i < sx.size(); i += 1) {
            ans += p * 9 * i;
            p *= 10;
        }
        ans += (x - p) * sx.size() + 1;
        return ans;
    };
    auto sx = to_string(x);
    LL ans = f(x);
    for (int i = 1; i < sx.size(); i += 1) {
        auto L = stoull(sx.substr(0, i));
        auto RL = sx.substr(i);
        auto RR = to_string(L + 1);
        if (RR.size() > i) {
            auto R = RL + string(i, '0');
            ans = min(ans, f(stoull(R)) - i);
        }
        int kk = 0;
        for (int k = 1; k <= RL.size() and k <= RR.size(); k += 1)
            if (RL.substr(RL.size() - k) == RR.substr(0, k))
                kk = k;
        auto R = RL + RR.substr(kk);
        if (R.size() <= 18)
            ans = min(ans, f(stoull(R)) - i);
    }
    for (int i = 0; i < sx.size(); i += 1) {
        for (int j = i; j < sx.size(); j += 1) {
            LL cur = stoull(sx.substr(i, j - i + 1));
            LL pre = cur - 1;
            auto st = to_string(pre);
            if (st.size() <= i) continue;
            int ok = st.substr(st.size() - i) == sx.substr(0, i);
            for (int k = j + 1; k < sx.size() and ok; ) {
                auto sw = to_string(cur += 1);
                if (k + sw.size() >= sx.size()) ok &= sw.substr(0, sx.size() - k) == sx.substr(k);
                else ok &= sw == sx.substr(k, sw.size());
                k += sw.size();
            }
            if (ok) ans = min(ans, f(pre) + (int)st.size() - i);
        }
    }
    return ans;
}
LL brute(LL x) {
    static string s = "0";
    static int i = 0;
    auto sx = to_string(x);
    int res = -1;
    while (res == -1) {
        for (int i = 0; i < s.size(); i += 1) {
            if (s.substr(i, sx.size()) == sx) {
                res = i;
                break;
            }
        }
        if (res == -1) s += to_string(i ++);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    for (cin >> q; q; q -= 1) {
        LL x;
        cin >> x;
        cout << solve(x) << "\n";
    }
    return 0;
    for (int i = 1; i <= 1000; i += 1) {
        auto x = to_string(i);
        //if (ranges::count(x, '0')) continue;
        if (solve(i) != brute(i)) {
            cout << i << " " << solve(i) << " " << brute(i) << endl;
            break;
        }
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 384ms, 内存消耗: 2232K, 提交时间: 2022-09-14 09:57:32

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
void write(__int128 a){
	if(a>9) write(a/10);
	putchar(a%10+48);
}
int q,len;long long a;__int128 ans;char s[50],str[50],t[50];
inline __int128 calc(long long x){
	__int128 res=2,t=1,i=1;
	for(;t<=x;t*=10,++i) res+=i*9*t;
	return res-(t-x)*(i-1);
}
int main(){
	for(scanf("%d",&q);q--;write(ans),putchar('\n')){
		scanf("%s",s+1);len=strlen(s+1);a=0;
		for(int i=1;i<=len;++i) a=a*10+(s[i]-=48);
		ans=calc(a);
		for(int i=1;i<len;++i){
			for(int j=1;j<=i;++j) str[j]=s[j];
			str[0]=0;++str[i];
			for(int j=i;str[j]>9;--j) str[j]=0,++str[j-1];
			for(int j=0,flg;j<=i&&i+j<=len;++j){
				flg=1;
				for(int k=1;k<=j&&flg;++k) flg=(str[k]==s[len-j+k]);
				if(flg){
					a=0;
					for(int k=i+1;k<=len;++k) a=a*10+s[k];
					for(int k=j+1;k<=i;++k) a=a*10+str[k];
					ans=min(ans,calc(a)-i);
				}
			}
		}
		for(int i=1,flg;i<=len;++i) for(int j=i;j<=len;++j) if(j-i+1>=i-1){
			for(int k=i;k<=j;++k) str[k-i+1]=s[k];
			for(int k=1;k<=j-i+1;++k) t[k]=str[k];
			t[0]=0;flg=1;
			for(int k=j+1;k<=len&&flg;k+=j-i+1){
				++t[j-i+1];
				for(int $=j-i+1;t[$]>9;--$) t[$]=0,++t[$-1];
				if(t[0]) t[1]=t[0],t[2]=0,++j;
				for(int $=1;$<=j-i+1&&k+$-1<=len&&flg;++$) flg=(t[$]==s[k+$-1]);
				if(t[0]) --j;
			}
			if(!flg) continue;
			--str[j-i+1];
			for(int k=1;k<i&&flg;++k) flg=(s[k]==str[(j-i+1)-(i-1)+k]);
			if(flg){
				a=0;
				for(int k=i;k<=j;++k) a=a*10+s[k];
				ans=min(ans,calc(a)-i+1);
			}
		}
	}
	return 0;
}