专栏文章

题解：CF1373E Sum of Digits

WWilliam2022
CF1373E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioipbm0
此快照首次捕获于
2025/12/02 19:51
3 个月前
此快照最后确认于
2025/12/02 19:51
3 个月前
查看原文

约定

本文约定 ∘\circ 运算符表示将若干个整数依次拼接。
例如 12∘34∘0=1234012 \circ 34 \circ 0 = 12340。
显然有 f(a∘b)=f(a)+f(b)f(a\circ b)=f(a)+f(b)。

方法

因为 k≤9k\leq9，所以 xx 在进位的时候至多进一位。
再观察样例，就不难想出将答案表示成这样。
x=p∘99…99⏟t times∘rx=p \circ \underbrace{99\ldots99}_{t \text{ times}} \circ r
其中，pp 是一个末尾不为 99 的数字，rr 是一个一位数字。
因为 rr 和 tt 都非常小，所以我们枚举所有的 rr 与 tt，然后求出最小的 pp。

做法

我们把 x,x+1,x+2,…,x+k−1,x+kx,x+1,x+2,\ldots,x+k-1,x+k 分成两块研究，一块是最后一位进位之前，一块是进位后。
有的时候可能不会进位，也就没有第二块。
第一块大小表示 rr 要加多少才能进位，也就是 10−r10-r。
因为总共有 k+1k+1 个数，第一块已经有了 10−r10-r 个，所以第二块就是 (k+1)−(10−r)(k+1)-(10-r) 个。
要注意的事是：
1.总共有 k+1k+1 个数，所以两块长度都不能超过 kk。
2.块长非负。
记两块长度为：
A=min⁡(k+1,10−r)A=\min(k+1,10-r)
B=max⁡(0,(k+1)−(10−r))B=\max(0,(k+1)-(10-r))
那么 x,x+1,x+2,…,x+k−1,x+kx,x+1,x+2,\ldots,x+k-1,x+k 就应该长这样：
p∘99…99∘rp∘99…99∘(r+1)⋮p∘99…99∘8p∘99…99∘9}A(p+1)∘00…00∘0(p+1)∘00…00∘1⋮(p+1)∘00…00∘(B−2)(p+1)∘00…00∘(B−1)}B\begin{aligned} & \begin{rcases} p \circ 99\ldots99 \circ r \\ p \circ 99\ldots99 \circ (r+1) \\ \vdots \\ p \circ 99\ldots99 \circ 8 \\ p \circ 99\ldots99 \circ 9 \\ \end{rcases} {A} \\ & \begin{rcases} (p+1) \circ 00\ldots00 \circ 0 \\ (p+1) \circ 00\ldots00 \circ 1 \\ \vdots \\ (p+1) \circ 00\ldots00 \circ (B-2) \\ (p+1) \circ 00\ldots00 \circ (B-1) \\ \end{rcases} {B} \end{aligned}
对上面所有数进行 ff 函数的操作。
可以得到：
n=f(x)+f(x+1)+⋯+f(x+k)=Af(p)+9At+Ar+A(A−1)2+B(f(p)+1)+B(B−1)2=(k+1)f(p)+B+9At+Ar+A(A−1)+B(B−1)2\begin{align*} n &= f(x) + f(x + 1) + \dots + f(x + k) \\ &= Af(p) + 9At + Ar + \frac{A(A-1)}{2} + B\left(f(p)+1\right) + \frac{B(B-1)}{2} \\ &= (k+1)f(p)+B+9At+Ar+\frac{A(A-1)+B(B-1)}{2} \end{align*}
∴f(p)=n−B−9At−Ar−A(A−1)+B(B−1)2k+1\therefore f(p) = \frac{n - B - 9At - Ar - \frac{A(A-1) + B(B-1)}{2}}{k+1}

答案计算

在已知 f(p)f(p) 后，为了让 pp 尽可能小，就尽可能填入 99，但末尾不能是 99 所以填入 88。
如果 f(p)≤8f(p)\leq 8 那么 p=f(p)p=f(p)。
否则填入 88 后尽可能填入 99，形如 p=X∘99…99∘8p=X \circ99\ldots99 \circ 8。
其中 XX 是 f(p)f(p) 减掉 88 再模 99 得到的数。
得出这次对应得答案为 p∘99…99⏟t times∘rp \circ \underbrace{99\ldots99}_{t \text{ times}} \circ r。
所有答案取 min⁡\min 即为答案。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF=9e18;

void add(ll &a,ll b){// 拼接函数，将 a 拼上 b
	for(ll b1=b;b1;b1/=10)a*=10;
	a+=b;
}

ll construct(int fp,int t,int r){// 输入 f(p),t,r 返回最小的 x
	ll fr=0;

	if(fp<=8)add(fr,fp);
	else{
		fp-=8;// 末尾会填入 8
		if(fp%9)add(fr,fp%9);
		for(;fp>=9;fp-=9)add(fr,9);// 尽可能用 9
		add(fr,8);// 末尾一个 8，因为 p 的末尾不能是 9
	}

	while(t--)add(fr,9);
	if(r)add(fr,r); else fr*=10;//我的拼接函数拼不上 0
	return fr;
}

ll solve(){
	ll n,k;
	cin>>n>>k;
	ll ans=INF;

	ll A,B;
	for(int t=0;t<=18;t++){
		for(int r=0;r<=9;r++){
			A=10-r; B=(k+1)-(10-r);
			A=min(A,k+1); B=max(B,0LL); //块长限制
			ll D=n-B-9*A*t-A*r-(A*(A-1)+B*(B-1))/2;

			if(D<0 || D%(k+1))continue;
			ll fp=D/(k+1);
			ans=min(ans,construct(fp,t,r));
		}
	}
	if(ans>=INF)return -1;
	return ans;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin>>T;
	while(T--)cout<<solve()<<'\n';
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...