自动搬运

查看原文

来自洛谷，原作者为

	Phoenix_2010 "The dark gives way to the light of dawn."

搬运于2025-08-24 23:13:27，当前版本为作者最后更新于2025-04-13 22:01:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd 2025.4.26:改了一个小笔误

可以列出如下方程：

$$\left\{ \begin{array}{l} a_1=(b_1-[a_2\ge5])\bmod10\\ a_2=(b_2-[a_3\ge5])\bmod10\\ \qquad\qquad\quad\vdots\\ a_{n-1}=(b_{n-1}-[a_n\ge5])\bmod10\\ a_n=(b_n-[a_1\ge5])\bmod10 \end{array} \right. $$

这是由于四舍五入的定义，$(a_i+[a_{i+1}\ge5])\bmod10=b_i$。

由于这个小数是循环的，所以第 $n+1$ 位等于第一位。

乍一看这个东西不太能解的样子，但是发现只要确定一个未知数的值，可以通过 $n-1$ 组确定其他未知数，而且剩下一组用于检验。

考虑枚举 $a_1$。发现它只有两种情况：$a_1=b_1$ 或 $a_1=(b_1-1)\bmod10$。

然后就能算出 $a_n$，进而 $a_{n-1},\dots,a_2$。然后检查一下通过 $a_2$ 算出的 $a_1$ 与刚开始钦定的是否相等。

答案就是 $\sum (10^n-1)a=\sum(10^n-1)\frac{\overline{a_1a_2\dots a_n}}{10^n-1}=\sum \overline{a_1a_2\dots a_n}$，写一个简单的高精度加法即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,b[N],a[N],ans[N];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i];
    if(n==1){cout<<(b[1]<5?b[1]:0);return 0;}//n=1时a[2]不存在，要特判。注意无解代表和为0。
    //第一种情况
    a[1]=b[1];a[n]=(b[n]-(a[1]>=5)+10)%10;
    for(int i=n-1;i>1;i--) a[i]=(b[i]-(a[i+1]>=5)+10)%10;
    if(a[1]==(b[1]-(a[2]>=5)+10)%10) for(int i=1;i<=n;i++) ans[i]+=a[i];
    //第二种情况
    a[1]=(b[1]+9)%10;a[n]=(b[n]-(a[1]>=5)+10)%10;
    for(int i=n-1;i>1;i--) a[i]=(b[i]-(a[i+1]>=5)+10)%10;
    if(a[1]==(b[1]-(a[2]>=5)+10)%10) for(int i=1;i<=n;i++) ans[i]+=a[i];
    for(int i=n;i>1;i--) if(ans[i]>9) ans[i]-=10,ans[i-1]++;//保证了答案不超过n位
    for(int i=1;i<=n;i++) cout<<ans[i];
    return 0;
}