P12178 DerrickLo's Decimals 题解

Phoenix_2010 · 2025-04-13 22:01:36 · 题解

upd 2025.4.26:改了一个小笔误

可以列出如下方程：

这是由于四舍五入的定义，(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;
}