原題及翻譯

For a positive integer N , the digit-sum of N is defined as the sum of N itself and its digits.
對于正整數n，n的位數和定義為n本身及其位數的和。
When M is the digitsum of N , we call N a generator of M .
當M是n的位數，我們稱n為m的生成器。
For example, the digit-sum of 245 is 256 (= 245 + 2 + 4 + 5).
例如，245的數字和為256（=245+2+4+5）。
Therefore, 245 is a generator of256.
因此，245是256的生成器。
Not surprisingly, some numbers do not have any generators and some numbers have more than one generator.
不足為奇，有些數字沒有任何生成器，有些數字有多個生成器。
For example, the generators of 216 are 198 and 207.
例如，216的生成器是198和207。
You are to write a program to find the smallest generator of the given integer.
您要編寫一個程序來查找給定整數的最小生成器。

Input

輸入
Your program is to read from standard input.
您的程序將從標準輸入中讀取。
The input consists of T test cases.
輸入由T測試用例組成。
The number of test cases T is given in the first line of the input.
測試用例數t在輸入的第一行給出。
Each test case takes one line containing an integer N , 1 ≤ N ≤ 100, 000.
每個測試用例取一行，包含一個整數n，1≤n≤100000。

Output

輸出
Your program is to write to standard output.
您的程序將寫入標準輸出。
Print exactly one line for each test case.
每個測試用例只打印一行。
The line is to contain a generator of N for each test case.
對于每個測試用例，該行包含一個n的生成器。
If N has multiple generators, print the smallest.
如果n有多個生成器，請打印最小的。
If N does not have any generators, print ‘0’.
如果n沒有任何生成器，請打印“0”。

Sample Input

3
216
121
2005

Sample Output

198
0
1979

思路

1.第一個想到的就是，暴力枚舉，一開始寫的是六層循環，作死的節奏，結果肯定是超時的，然后再把循環層數減到兩層，從1枚舉到最大值，但是每次枚舉都要與n個數判斷是否符合條件，時間復雜度O（n²），還是會超時，只有把時間復雜度降到O（n），才能AC。

2.枚舉也有兩種方法，第一種就是將1~ max枚舉然后分別判斷，第二種是將1~ 100000的所有生成元與其數字對應，沒有生成元的就標為0，然后分別輸入數字將其對應的生成元輸出。

代碼分析

先把超時的代碼放出來，算法很簡單，很好理解，但是，超時，不管怎樣，沒AC就是WA。

#include <stdio.h> #include <string.h> int main () {int n,max=0;scanf("%d",&n);int m[n];for(int i=0;i<n;i++){scanf("%d",&m[i]);if(m[i]>max) max=m[i];}int x[n],flag[n],index=0;memset(x,0,sizeof(x));memset(flag,0,sizeof(flag));for(int i=1;i<=max;i++){int a=i/100000%10,b=i/10000%10,c=i/1000%10,d=i/100%10,e=i/10%10,f=i/1%10;for(int j=index;j<n;j++){if(a*100000+b*10000+c*1000+d*100+e*10+f+a+b+c+d+e+f==m[j]){x[j]=a*100000+b*10000+c*1000+d*100+e*10+f;flag[j]=1;index++;}}}for(int i=0;i<n;i++){if(flag[i]==0) printf("0 \n");else printf("%d \n",x[i]);}return 0; }

接下來看正確的結果：
1.創建一個全局變量的數組將從1~100000的所有生成元存儲起來：

#define max 100000 int ans[max];

2.計算生成元并存儲：

for(int m=1;m<max;m++){//從1開始遍歷int x=m,y=m;//x，y作為計算生成元的中間變量while(x>0){//將y分別與x的每一位相加，即生成元y+=x%10;x/=10;}if(ans[y]==0||ans[y]>m) ans[y]=m;//將即將輸入的數字y與其生成元m對應}

完整代碼

#include <stdio.h> #include <string.h> #define max 100000 int ans[max]; int main() {int t,n;memset(ans,0,sizeof(ans));for(int m=1;m<max;m++){int x=m,y=m;while(x>0){y+=x%10;x/=10;}if(ans[y]==0||ans[y]>m) ans[y]=m;}scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",ans[n]);}return 0; }

每天磕一道ACM 正月初三打卡

總結

以上是生活随笔為你收集整理的《算法竞赛入门经典》 例题3-5 生成元 （Digit Generator, ACM ICPC Seoul 2005,UVa）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。