P11059 [入门赛 #27] 数字 (Hard Ver.)题解

Solution

先读题:

在给定x的位数\(n\)和模数\(p\)后,要求构造一个\(x\)在满足\(x\mod p\)的余数尽可能小的前提下使\(x\)的数字尽可能小。

我们假设\(x\)的各位数字之和为\(m\),有\(1\le m\le 9n\)。.
(当\(x\)仅在最高位有1时\(m=1\),称为情况一,当x每位为9时\(m=9n\),称为情况二)
此时对于\(m\)有两种情况:

在\(p> 9n\)或\(p=1\)时无需构造,属于情况一。

\(1<p\le9n\)时需构造,属于情况二,且可以简单证明必定有一个合法\(x\)使\(x\mod p=0\)。

做法:

对于情况二，容易想到一种贪心解法,此时的模数\(p\)可直接看作能在每一位放的所有数字之和,步骤如下：

1. 在最高位先放数字1维持\(x\)合法并是\(p\)减1。
2. 再从最低位开始放数字，当\(p>=9\)时该位放9且让\(p\)减去9,当\(1\le p\le8\)且不为最高位时使该位为p，接着走向较高的下一位。
3. 放置过程中若\(p=0\),那么说明所有数字放完,退出。
4. 若在最高位仍有\(p>0\),那么时最高位为\(p+1\)(在步骤一中最高位已经放了1,再加上此时的\(p\))并退出。

复杂度分析:

因为按位放数字,有\(n\)位,复杂度为\(O(n)\),且\(1\le n\le 10^{6}\),该方式可行。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,p,a[N],idx=1;
int main() {cin>>n>>p;if(n*9<p){putchar('1');for(int i=1;i<n;++i)putchar('0');}else{p--;while(idx!=n&&p){if(p>=10)a[idx]=9;else a[idx]=p;p-=a[idx];++idx;}a[n]=++p;for(int i=n;i>=1;--i)cout<<a[i];}return 0;
}