補(bǔ)一下從前的做題記錄。。。。某天一口氣水了三道簡(jiǎn)單的枚舉
這三道題的核心思想就是枚舉，通過(guò)暴力的枚舉所有情況來(lái)結(jié)局題目。 總體來(lái)說(shuō)比較不費(fèi)腦，只需要枚舉所有情況就可以了，但是在枚舉的 方法上，要注意方法的優(yōu)化，不然可能會(huì)超時(shí)的。 第一題： UVA725-7.1-Division 題目鏈接：https://vjudge.net/PRoblem/UVA-725 這個(gè)題的意思是說(shuō)輸入正整數(shù)n，按從小到大的順序輸出所有形如abcde/fghij=n的表達(dá)式。其中a~j正好為數(shù)字0~9的一個(gè)排列（可以有前導(dǎo)零） 如： 62 79546/01283=62 94736/01528=62 題目分析： 這個(gè)題我寫(xiě)的比較麻煩，就是只枚舉分母，結(jié)果乘以分母即為分子。 然后用一個(gè)數(shù)組標(biāo)記哪一個(gè)數(shù)用到過(guò)了，然后直接暴力枚舉所有數(shù) 判斷是否成立。 給出代碼：
#include<iostream>#include<vector>#include<queue>#include<set>#include<cstdio>#include<string.h>using namespace std;int mark[10];int judge(int x){ int h=1; int book=0; while(x%h!=x) { h=h*10; book++; } return book;}void com(int x){ int h=10; while(x) { int t=x%10; mark[t]=0; x=x/10; } return;}int main(){ //freopen("D://output.txt", "w", stdout); int n; memset(mark,1,sizeof(mark)); int a1=0; while(cin>>n&&n) { a1++; if(a1!=1) cout<<endl; int book1=1; for(int i=1234;;i++) { //cout<<i<<endl; int a=n*i; if(a>=100000) break; int h1=judge(a); int h2=judge(i); int h=h1+h2; if(h>10) break; if(h==9) mark[0]=0; com(a); com(i); int book=1; int j; for(j=0;j<10;j++) if(mark[j]) { book=0; break; } if(book) { book1=0; if(h1==4) cout<<0<<a<<" / "<<i<<" = "<<n<<endl; else if(h2==4) cout<<a<<" / "<<0<<i<<" = "<<n<<endl; else cout<<a<<" / "<<i<<" = "<<n<<endl; } memset(mark,1,sizeof(mark)); } if(book1) printf("There are no solutions for %d./n",n); }}第二題： UVA11059-7.2-Maximum Product 題目鏈接： https://vjudge.net/problem/UVA-11059 輸入n個(gè)元素組成的序列S.找出一個(gè)乘積最大的連續(xù)子序列。 題目分析： 因?yàn)檫@個(gè)題的n很小，<=18,所以直接枚舉所有的子序列就可以做出。 給出代碼：
#include<iostream>#include<vector>#include<queue>#include<set>#include<cstdio>#include<string.h>using namespace std;typedef long long int LL;int main(){ //freopen("D://output.txt", "w", stdout); int book=0; int n; LL num[20]; while(cin>>n) { book++; int i; LL MAX=-1;; for(i=1;i<=n;i++) cin>>num[i]; for(i=n;i>0;i--) { int y=1; int turn=n-i+1; while(turn--) { LL x=1; for(int j=y;j<y+i;j++) x*=num[j]; //cout<<"x="<<x<<endl; if(MAX<x) MAX=x; y++; } } if(MAX<0) MAX=0; printf("Case #%d: The maximum product is %lld./n/n",book,MAX); } return 0;}第三題： UVA10976-7.3-Fraction Again 題目鏈接： https://vjudge.net/problem/UVA-10976 輸入正整數(shù)k，找出所有的正整數(shù)x>=y，使得1/k=1/x+1/y. 題目分析： 這個(gè)題同樣就可以通過(guò)枚舉所有情況來(lái)結(jié)局。 不過(guò)通過(guò)對(duì)樣例數(shù)據(jù)的分析我們可以發(fā)現(xiàn)，如 果輸入一個(gè)k，x和y的值最大是無(wú)法超過(guò)k的兩倍的， 這樣就找到了邊界。 給出代碼：
#include<iostream>#include<vector>#include<queue>#include<set>#include<cstdio>#include<string.h>using namespace std;int main(){ //freopen("D://output.txt", "w", stdout); int n; while(cin>>n) { int num1[50000]; int num2[50000]; int book=0; int i; for(i=n+1;i<=n*2;i++) { long long int a=i-n; long long int b=n*i; if(b%a==0) { book++; num1[book]=b/a; num2[book]=i; } } printf("%d/n",book); for(i=1;i<=book;i++) { printf("1/%d = 1/%d + 1/%d/n",n,num1[i],num2[i]); } } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
