一年的省賽題目。

先容我罵一下，這題目有病吧，我調試了一個下午+晚上，好不容易才順利A了，真是坑。

比賽中能做出來的那絕對是厲害啊！！。

我的思路，方法可能有笨：

1.首先判斷下有幾個0，有一個0的話，

? ? ?一 ?。判斷0后面有沒有比9小的數，有的話那個數加1就可以直接輸出了。

? ???二 ?。如果0是最后一位，前面有比9小的數，那個數+1,后面全輸出0即可

? ? ?三 ?。如果0是最后一位，前面沒有比9小的那直接在最前面加1,后面全輸出0即可。

? ? ?四 ?。如果0后面沒有比9小的，那直接把0位置變成1,后面都變成0輸出即可。

2.如果是有多個0的話

? ? 一。如果在最右0之后有比9小的數，那直接那個數+1 輸出答案即可。

? ? 二。如果沒有的話，那就直接把這個位置的0變成1,后面全部輸出0即可。

3。就是比較一般的情況

? ? 這種是比較簡單的。統計因子2 3 5 7 出現的次數。

? ?因為4可以由 2×2 ? 組成，6可以由 2×3 組成 ?8 9都可以組成，所以只要保留素數因子即可。

然后直接從后往前面遍歷，用直接已經有的因子數，看能不能組成比這個大的，如果可以的話，高位直接不動，這個位置變成這個數。

然后從最后一位開始，把當前擁有因子能組成的最大數組合起來，一個一個往前放，沒有因子的話，那都放1就可以了，然后輸出答案即可。

如果都沒有可能的話，那在這個數前面加1即可。！！！！！！！！！！

！！！！！！！！

比如111126

一開始 a[2]=a[3]=a[5]=a[7]=0;

然后6遍歷到6,a[2]++,a[3]++;

因為沒有能組成比6 大.

然后遍歷2這個時候a[2]=2,a[3]=1;

能組成3那這個位置就放3此時a[2]=2,a[3]=0;

最后一個變成4輸出答案即可。

上代碼！

#include<string> #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[15],b[15];int f() {if(a[3]>=2) { a[3]-=2; return 9;}else if(a[2]>=3) { a[2]-=3; return 8;}else if(a[7]>=1) { a[7]-=1; return 7;}else if(a[2]>=1&&a[3]>=1) { a[2]-=1; a[3]-=1;return 6;}else if(a[5]>=1) { a[5]-=1; return 5; }else if(a[2]>=2) { a[2]-=2; return 4; }else if(a[3]>=1) { a[3]-=1; return 3; }else if(a[2]>=1) { a[2]-=1; return 2; }else return 1; }int fit(int num) {if(num==9&&a[3]>=2) { return 1; }else if(num==8&&a[2]>=3) { return 1; }else if(num==7&&a[7]>=1) { return 1;}else if(num==6&&a[3]>=1&&a[2]>=1) { return 1; }else if(num==5&&a[5]>=1) { return 1;}else if(num==4&&a[2]>=2) { return 1;}else if(num==3&&a[3]>=1) { return 1; }else if(num==2&&a[2]>=1) { return 1;}else return 0; } void add(int num) {if(num%2==0) {if(num==6) { a[2]++; a[3]++; return ; }int temp=num;while(temp!=1&&temp%2==0) {a[2]++;temp/=2;}}else if(num%3==0) {int temp=num;while(temp!=1&&temp%3==0) {a[3]++;temp/=3;}}else if(num%5==0) {int temp=num;while(temp!=1&&temp%5==0) {a[5]++;temp/=5;}}else if(num%7==0) {int temp=num;while(temp!=1&&temp%7==0) {a[7]++;temp/=7;}} } void dd(int num) {if(num%2==0) {if(num==6) { a[2]--; a[3]--; return ;}int temp=num;while(temp!=1&&temp%2==0) {a[2]--;temp/=2;}}else if(num%3==0) {int temp=num;while(temp!=1&&temp%3==0) {a[3]--;temp/=3;}}else if(num%5==0) {int temp=num;while(temp!=1&&temp%5==0) {a[5]--;temp/=5;}}else if(num%7==0) {int temp=num;while(temp!=1&&temp%7==0) {a[7]--;temp/=7;}} }int main() {//freopen("in","r",stdin);//freopen("out","w",stdout);int n;scanf("%d",&n);getchar();for(int ww=1; ww<=n; ww++) {char str[10005];gets(str);int i,l=strlen(str);int num[10005],flag=0;for(i=0; i<l; i++) {num[i]=str[i]-'0';if(num[i]==0) flag++;}for(i=0; i<10; i++) a[i]=0;int rere;if(flag==1) {int ff=0,f_f;for(i=l-1; i>=0; i--) {if(num[i]!=0) {if(num[i]<9) {ff=1;rere=i;break;}}else{f_f=i;}}if(ff) {if(f_f<rere){num[rere]++;for(i=0; i<=rere; i++) printf("%d",num[i]);for(; i<l; i++) printf("0");}else{if(f_f!=l-1){num[f_f]=1;for(i=0;i<=f_f;i++) printf("%d",num[i]);for(;i<l;i++) printf("0");}else{num[rere]++;for(i=0; i<=rere; i++) printf("%d",num[i]);for(; i<l; i++) printf("0");}}}else {if(f_f==l-1) {printf("1");for(i=0; i<l; i++) printf("0");}else{num[f_f]=1;for(i=0;i<=f_f;i++) printf("%d",num[i]);for(;i<l;i++) printf("0");}}}else if(flag>1) {int ff=0;for(i=l-1; i>=0; i--) {if(num[i]==0) {num[i]++;ff=1;rere=i;break;}if(num[i]!=0) {if(num[i]<9) {num[i]++;ff=1;rere=i;break;}}}if(ff) {for(i=0; i<=rere; i++) printf("%d",num[i]);for(; i<l; i++) printf("0");}else {printf("1");for(i=0; i<l; i++) printf("%d",num[i]);}}else {int j,fnow=0;for(i=l-1; i>=0; i--) {add(num[i]);for(j=num[i]+1;j<=9;j++){if(fit(j)){num[i]=j;dd(j);for(j=l-1;j>i;j--){num[j]=f();}fnow=1;break;}}if(fnow) break;}if(fnow) {for(i=0; i<l; i++) printf("%d",num[i]);}else {printf("1");for(i=0; i<l; i++) printf("%d",num[i]);}}printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的zoj 3327 Friend Number 模拟题的全部內容，希望文章能夠幫你解決所遇到的問題。

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