/*——————————————————————————————————————————————————————————— 【結果填空題】T1 (分值：3) 題目：煤球數目有一堆煤球，堆成三角棱錐形。具體： 第一層放1個， 第二層3個（排列成三角形）, 第三層6個（排列成三角形）, 第四層10個（排列成三角形）, .... 如果一共有100層，共有多少個煤球？ 請填表示煤球總數目的數字。 注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。1 * (1) 2 *** (3) 3 ****** (6) 4 ********** (10) 5 ..............(15) ————————————————————————————————————————————————————————————*/ // /*** pre 定義上一層* plus 定義增量差值 */ #include<iostream> using namespace std ; int main(int argc, char const *argv[]) {int pre = 1 ; // int plus = 2 ; // long sum = 1 ;for (int k = 2; k <= 100; ++k){sum += (pre+plus) ;pre = pre + plus ;//sum+=preplus++ ;}cout << sum << endl ;return 0; } //結果：171700/*——————————————————————————————————————————————————————————— 【結果填空題】T2 (分值：5) 題目：生日蠟燭某君從某年開始每年都舉辦一次生日party， 并且每次都要吹熄與年齡相同根數的蠟燭。 現在算起來，他一共吹熄了236根蠟燭。 請問，他從多少歲開始過生日party的？ 請填寫他開始過生日party的年齡數。 注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。 ————————————————————————————————————————————————————————————*/ // /* 思路：236 i ~ j for(i:100) for(j:100) 等差數列求和：(i+j)/2*(j-i-1) (a0+a0*(n-1)*d/2)*n*/#include<iostream> using namespace std ; int main() {//枚舉兩個年齡for (int i = 1; i < 100; ++i){for (int j = i; j < 100; ++j){if((i*j)*(j-i-1)/2==236)cout << i << " "<< j << endl ;}}//枚舉生日舉辦次數for (int i = 1; i < 100; ++i){int t = i*(i-1)/2 ;if((236-t)%i==2){//輸出首項cout << (236-t)/i << " " << i << endl ;}}return 0 ; }/*——————————————————————————————————————————————————————————— 【結果填空題】T3 (分值：11) 題目：湊算式B DEF A + --- + ------- = 10C GHI（如果顯示有問題，可以參見【圖1.jpg】） 這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。 比如： 6+8/3+952/714 就是一種解法， 5+3/1+972/486 是另一種解法。 這個算式一共有多少種解法？ 注意：你提交應該是個整數，不要填寫任何多余的內容或說明性文字。 ————————————————————————————————————————————————————————————*/ // //全排列 #include<iostream> #include<math.h>using namespace std ; int a[] = {1,2,3,4,5,6,7,8,9} ; int ans ; bool check() {int x = a[3] * 100 + a[4] * 10 + a[5] ;int y = a[6] * 100 + a[7] * 10 + a[8] ;if((a[1]*y + a[2]*x) % (y*a[2])==0 && a[0] + (a[1]*y + a[2]*x)/(y*a[2]==10)) return true ;return false ; }//遞歸回溯生成全排列 適用于無重復元素的情況 //考慮前k位，前面已經排定 void f(int k) {if(k==9) {//其中一種排列已經生成if(check()) ans++ ;}//從k往后的每個數字都可以放在k位for (int i = k; i < 9; ++i){{int t=a[i]; a[i]=a[k]; a[k]=t;}f(k+1) ; //遞歸{int t=a[i]; a[i]=a[k]; a[k]=t;} //回溯 } }int main() {f(0) ;cout << ans << endl ;return 0 ; }//思路二 next_permutation() #include<iostream> #include<math.h>using namespace std ; int a[] = {1,2,3,4,5,6,7,8,9} ; int ans ; bool check() {int x = a[3] * 100 + a[4] * 10 + a[5] ;int y = a[6] * 100 + a[7] * 10 + a[8] ;if((a[1]*y + a[2]*x) % (y*a[2])==0 && a[0] + (a[1]*y + a[2]*x)/(y*a[2]==10)) return true ;return false ; }int main() {do{if(check()) ans++ ;}while(next_permutation(a,a+9)) ;cout << ans << endl ;return 0 ; }/*——————————————————————————————————————————————————————————— 【代碼填空題】T4 (分值：9) 題目：快速排序 排序在各種場合經常被用到。 快速排序是十分常用的高效率的算法。 其思想是：先選一個“標尺”， 用它把整個隊列過一遍篩子， 以保證：其左邊的元素都不大于它，其右邊的元素都不小于它。 這樣，排序問題就被分割為兩個子區間。 再分別對子區間排序就可以了。下面的代碼是一種實現，請分析并填寫劃線部分缺少的代碼。 ————————————————————————————————————————————————————————————*/ // #include <stdio.h>void swap(int a[], int i, int j)//交換 {int t = a[i];a[i] = a[j];a[j] = t; }int partition(int a[], int p, int r) {int i = p; //i指向大于x ——>找大int j = r + 1; //j指向小于等于x ——>找小int x = a[p];while(1){while(i<r && a[++i]<x);while(a[--j]>x);if(i>=j) break;swap(a,i,j);}/*代碼填空處swap(a,p,j) ; //______________________; */return j; }void quicksort(int a[], int p, int r) {if(p<r){int q = partition(a,p,r); //q為標尺quicksort(a,p,q-1);quicksort(a,q+1,r);} }int main() {int i;int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};int N = 12;quicksort(a, 0, N-1); //排序for(i=0; i<N; i++) printf("%d ", a[i]);printf("\n");return 0; }/*——————————————————————————————————————————————————————————— 【代碼填空題】T5 (分值：13) 題目：抽簽X星球要派出一個5人組成的觀察團前往W星。 其中： A國最多可以派出4人。 B國最多可以派出2人。 C國最多可以派出2人。 ....那么最終派往W星的觀察團會有多少種國別的不同組合呢？下面的程序解決了這個問題。 數組a[] 中既是每個國家可以派出的最多的名額。 程序執行結果為： DEFFF CEFFF CDFFF CDEFF CCFFF CCEFF CCDFF CCDEF BEFFF BDFFF BDEFF BCFFF BCEFF BCDFF BCDEF .... (以下省略，總共101行) ————————————————————————————————————————————————————————————*/ //遞歸填空 #include <stdio.h> #define N 6 #define M 5 #define BUF 1024 /*** k = 數組的下標 * m代表人數，初始為5* b緩沖字符串*/void f(int a[], int k, int m, char b[]) {int i,j;if(k==N){ b[M] = 0; //字符串結尾的標志if(m==0) {printf("%s\n",b); ans++ ;}return;}//遞歸for(i=0; i<=a[k]; i++){ //試著將k國家，排除i人for(j=0; j<i; j++) b[M-m+j] = k+'A'; ////填充buf，有i人就填i個國家符號(k+'A')/*代碼填空處f(a,k+1,m-i,b) ; ______________________; */f(a,k+1,m-i,b) ; } } int main() { int a[N] = {4,2,2,1,1,3};char b[BUF];f(a,0,M,b);printf("%d\n",ans) ;return 0; }/*——————————————————————————————————————————————————————————— 【結果填空題】T6 (分值：19) 題目：方格填數 如下的10個格子+--+--+--+| | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | +--+--+--+（如果顯示有問題，也可以參看【圖1.jpg】） 填入0~9的數字。要求：連續的兩個數字不能相鄰。 （左右、上下、對角都算相鄰） 一共有多少種可能的填數方案？請填寫表示方案數目的整數。 注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。 ————————————————————————————————————————————————————————————*/ // 全排列 + 檢查 #include<iostream> using namespace std ;int a[10] = {0,1,2,3,4,5,6,7,8,9} ; int ans ;void check()//檢查 {if(abs(a[0] - a[1])==1 ||abs(a[0] - a[3])==1 ||abs(a[0] - a[4])==1 ||abs(a[0] - a[5])==1 ||abs(a[1] - a[2])==1 ||abs(a[1] - a[4])==1 ||abs(a[1] - a[5])==1 ||abs(a[1] - a[6])==1 ||abs(a[2] - a[5])==1 ||abs(a[2] - a[6])==1 ||abs(a[3] - a[4])==1 ||abs(a[3] - a[7])==1 ||abs(a[3] - a[8])==1 ||abs(a[4] - a[5])==1 ||abs(a[4] - a[7])==1 ||abs(a[4] - a[8])==1 ||abs(a[4] - a[9])==1 ||abs(a[5] - a[6])==1 ||abs(a[5] - a[8])==1 ||abs(a[5] - a[9])==1 ||abs(a[6] - a[9])==1 ||abs(a[7] - a[8])==1 ||abs(a[8] - a[9])==1 ||)return false ;return true ; }/*考慮第k個位置，一般從0開始*/ void f(int k)//遞歸函數 { //出口 if(k==0){bool b = check() ; //檢查if(b)ans++ ;return ;}for (int i = k; i < 10; ++i)//嘗試將位置i與位置k交換，以此確定k位的值 {int t = a[i] ;a[i] = a[k] ;a[k] = t ; }f(k+1) ;//回溯 {int t = a[i] ;a[i] = a[k] ;a[k] = t ;}}int main() {f(0) ; //初始化cout << ans << endl ;return 0 ； }//思路2 使用二維數組 /* 3*4 ——> 5*6 -10-10-10-10-10+--+--+--+| | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | +--+--+--+ -10-10-10-10-10*/ #include<iostream> using namespace std ;int a[5][6] ; int vis[10] ; int ans ;bool check(int i ,int y) //檢查 {for (int x = x-1; x<= i+1; ++x){for (int y = j-1; y <= j+1; ++y){if(abs(a[x][y]-a[i][j])==1)return false ;}}return true ; }//全排列 void f(int k,int y) {if(x==3 & y == 4){ans++ ;return ;}//從0-9中抓一個for (int i = 0; i < 10; ++i){if(vis[i]==0) //i沒有沒用過 {a[x][y] = i ; //填數if(!check(x,y)) //不合法，恢復并continue {a[x][y] = -10 ;continue ;}vis[i] = 1 ;if(y ==4)f(x+1,1) ; //換行else f(x,y+1) ; //繼續填右側的格子 {vis[i] = 0 ;a[x][y] = -10 ;} }} }//初始化 void init() {for (int i = 0; i < 5; ++i){for (int j = 0; j < 6; ++j){a[i][j] = -10 ; //初始化格式 }} }int main(int argc, char const *argv[]) {init() ; //初始化f(1,2) ; //遞歸調用cout << ans <<endl ; //打印輸出return 0; } /*本思路可以防止下標越界的問題*//*——————————————————————————————————————————————————————————— 【結果填空題】T7 (分值：19) 題目：剪郵票 如【圖1.jpg】, 有12張連在一起的12生肖的郵票。 現在你要從中剪下5張來，要求必須是連著的。 （僅僅連接一個角不算相連） +--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | | +--+--+--+--+ 比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。 請你計算，一共有多少種不同的剪取方法。請填寫表示方案數目的整數。 注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。 ————————————————————————————————————————————————————————————*/ // /* 1 2 3 4 5 6 7 8 9 10 11 12 思路1：每個格子作為起點,dfs連五張，去重->結果思路2：暴力枚舉，所有的五張組合，檢查它們是不是一個連通塊。 */ // 12/13 寒假作業 12/5 dfs/*思路1： 生成的方法有太多的重復，效率低下 //此題和13年剪格子有相似之處，但是那個題的限制條件是格子數值之和為總和的一半，此題則限制只能是5個格子 //單純的dfs無法解決T字型連通方案 //本題的解決辦法是，找出任意5個格子，判斷是否連通*/ #include <algorithm> #include <iostream>using namespace std;int ans;bool check(int arr[12]);void dfs(int g[3][4], int i, int j);int main(int argc, const char *argv[]) {int per[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};do {if (check(per))ans++;} while (next_permutation(per, per + 12));cout << ans << endl;return 0; }bool check(int arr[12]) {int g[3][4];memset(g, 0, sizeof(g)); //將相應位置標注為1for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {if (arr[i * 4 + j] == 1)g[i][j] = 1;}} // 經典連通塊計算int cnt = 0;for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {if (g[i][j] == 1) {dfs(g, i, j);cnt++;}}}return cnt == 1; }void dfs(int g[3][4], int i, int j) {g[i][j] = 0;if (i + 1 <= 2 && g[i + 1][j] == 1) dfs(g, i + 1, j);if (i - 1 >= 0 && g[i - 1][j] == 1) dfs(g, i - 1, j);if (j + 1 <= 3 && g[i][j + 1] == 1) dfs(g, i, j + 1);if (j - 1 >= 0 && g[i][j - 1] == 1) dfs(g, i, j - 1); }//思路2： #include <algorithm> #include <iostream> #include <set>using namespace std;int a[]={0,0,0,0,0,0,0,1,1,1,1,1};//它的每個排列代表著12選5的一個方案 int ans; void dfs(int g[3][4],int i , int j){g[i][j]=0;if(i-1>=0&&g[i-1][j]==1)dfs(g,i-1,j);if(i+1<=2&&g[i+1][j]==1)dfs(g,i+1,j);if(j-1>=0&&g[i][j-1]==1)dfs(g,i,j-1);if(j+1<=3&&g[i][j+1]==1)dfs(g,i,j+1); } bool check(){int g[3][4]; // 將某個排列映射到二維矩陣上for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {if(a[i*4+j]==1) g[i][j]=1;else g[i][j]=0;}}int cnt=0;//連通塊的數目 // g上面就有5個格子被標記為1，現在才用dfs做連通性檢查，要求只有一個連通塊for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {if(g[i][j]==1){dfs(g,i,j);cnt++;}}}return cnt==1; } set<string> s1; void a2s(string &s){for (int i = 0; i < 12; ++i) {s.insert(s.end(),a[i]+'0');} } bool isExist(){string a_str;a2s(a_str);if(s1.find(a_str)==s1.end()){s1.insert(a_str);return false;} elsereturn true; } void f(int k){if(k==12){if(!isExist()&&check()){ans++;}}for (int i = k; i < 12; ++i) {{int t=a[i];a[i]=a[k];a[k]=t;}f(k+1);{int t=a[i];a[i]=a[k];a[k]=t;}} } int main(int argc, const char *argv[]) {f(0);printf("%d",ans); //string _s; //a2s(_s); //cout<<_s<<endl;return 0; }//思路3： #include <algorithm> #include <iostream>using namespace std;//它的每個排列代表著12選5的一個方案 int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1}; int ans;void dfs(int g[3][4], int i, int j) {g[i][j] = 0;if (i - 1 >= 0 && g[i - 1][j] == 1)dfs(g, i - 1, j);if (i + 1 <= 2 && g[i + 1][j] == 1)dfs(g, i + 1, j);if (j - 1 >= 0 && g[i][j - 1] == 1)dfs(g, i, j - 1);if (j + 1 <= 3 && g[i][j + 1] == 1)dfs(g, i, j + 1); }bool check(int path[12]) {int g[3][4]; // 將某個排列映射到二維矩陣上for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {if (path[i * 4 + j] == 1) g[i][j] = 1;else g[i][j] = 0;}}int cnt = 0;//連通塊的數目 // g上面就有5個格子被標記為1，現在才用dfs做連通性檢查，要求只有一個連通塊for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {if (g[i][j] == 1) {dfs(g, i, j);cnt++;}}}return cnt == 1; }bool vis[12];void f(int k, int path[12]) {if (k == 12) {if (check(path)) {ans++;}}for (int i = 0; i < 12; ++i) {if (i>0&&a[i]==a[i-1]&&!vis[i-1])continue;//現在準備選取的元素和上一個元素相同，但是上一個元素還沒被使用if(!vis[i]){//沒有被用過的元素可以抓入到pathvis[i]=true;//標記為已訪問path[k]=a[i];//將a[i]填入到path[k]中f(k + 1, path);//遞歸vis[i]=false;//回溯 }} }int main(int argc, const char *argv[]) {int path[12];f(0, path);printf("%d", ans);return 0; }/*——————————————————————————————————————————————————————————— 【代碼編程題】T8 (分值：21) 題目：四平方和四平方和定理，又稱為拉格朗日定理： 每個正整數都可以表示為至多4個正整數的平方和。 如果把0包括進去，就正好可以表示為4個數的平方和。比如： 5 = 0^2 + 0^2 + 1^2 + 2^2 7 = 1^2 + 1^2 + 1^2 + 2^2 （^符號表示乘方的意思）對于一個給定的正整數，可能存在多種平方和的表示法。 要求你對4個數排序： 0 <= a <= b <= c <= d 并對所有的可能表示法按 a,b,c,d 為聯合主鍵升序排列， 最后輸出第一個表示法程序輸入為一個正整數N (N<5000000) 要求輸出4個非負整數，按從小到大排序，中間用空格分開例如，輸入： 5 則程序應該輸出： 0 0 1 2再例如，輸入： 12 則程序應該輸出： 0 2 2 2再例如，輸入： 773535 則程序應該輸出： 1 1 267 838資源約定： 峰值內存消耗 < 256M CPU消耗 < 3000ms請嚴格按要求輸出，不要畫蛇添足地打印類似： “請您輸入...” 的多余內容。所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。注意: main函數需要返回0 注意: 只使用ANSI C/ANSI C++ 標準， 不要調用依賴于編譯環境或操作系統的特殊函數。 注意: 所有依賴的函數必須明確地在源文件中 #include <xxx>， 不能通過工程設置而省略常用頭文件。提交時，注意選擇所期望的編譯器類型。————————————————————————————————————————————————————————————*/ //枚舉+優化 //優化：采用緩存來空間換時間/*思路1： 枚舉abcd for(a) 0~a^2for(b) 0~b^2for(c) 0~c^2for(d) 0~d^2 */ #include<iostream> #include<cstdio> #include<map> int N ;using namespace std ;int main() {scanf("%d",&N) ;// for (int c = 0; c*c <= N/2; ++c){for (int d = c; c*c+d*d <= N ; ++d){if(cache.find(c*c+d*d)==cache.end())cache[c*c+d*d] = c ;}// for (int a = 0; a*a<= N/4; ++a){for (int b = a; a*a+c*c <= N/2; ++b){if(cache.find(N-a*a+b*b)!=cache.end()) ;int c = cache[N-(a*a+b*b+c*c)] ;int d = int(sqrt(N-(a*a+b*b+c*c)) ;printf("%d %d %d %d\n",a,b,c,d) ;return 0 ;}}}return 0 ; }/*——————————————————————————————————————————————————————————— 【代碼編程題】T9 (分值：23) 題目：交換瓶子有N個瓶子，編號 1 ~ N，放在架子上。 比如有5個瓶子： 2 1 3 5 4 要求每次拿起2個瓶子，交換它們的位置。 經過若干次后，使得瓶子的序號為： 1 2 3 4 5 對于這么簡單的情況，顯然，至少需要交換2次就可以復位。 如果瓶子更多呢？你可以通過編程來解決。 輸入格式為兩行： 第一行: 一個正整數N（N<10000）, 表示瓶子的數目 第二行：N個正整數，用空格分開，表示瓶子目前的排列情況。 輸出數據為一行一個正整數，表示至少交換多少次，才能完成排序。例如，輸入： 5 3 1 2 5 4程序應該輸出：3 再例如，輸入： 5 5 4 3 2 1程序應該輸出：2 資源約定： 峰值內存消耗 < 256M CPU消耗 < 1000ms請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內容。所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。注意: main函數需要返回0 注意: 只使用ANSI C/ANSI C++ 標準， 不要調用依賴于編譯環境或操作系統的特殊函數。 注意: 所有依賴的函數必須明確地在源文件中 #include <xxx>， 不能通過工程設置而省略常用頭文件。 提交時，注意選擇所期望的編譯器類型。 ————————————————————————————————————————————————————————————*/ /*3 2 1 5 4 [1] [2] [3] [4] [5] */// 貪心 #include <iostream>using namespace std; int n; int a[10001]; int ans;int pos(int x) {for (int i = 1; i <= n; ++i) {if (a[i] == x)return i;}return -1; }void swap(int i, int j) {int t = a[i];a[i] = a[j];a[j] = t; }void printArr() {for (int i = 1; i <= n; ++i) {printf("%d ", a[i]);}printf("\n"); }int main(int argc, const char *argv[]) {// 處理輸入scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}//遍歷i:1-Nfor (int i = 1; i <= n; ++i) {//如果a[i]=i,已經到位if (a[i] == i)continue;//否則先找到i在a中的位置pos(i)和i位交換——swap(a,pos(i),i)else {swap(pos(i), i);ans++;}}//printArr();printf("%d\n", ans);return 0; }/*——————————————————————————————————————————————————————————— 【代碼編程題】T10 (分值：31) 題目：最大比例X星球的某個大獎賽設了M級獎勵。每個級別的獎金是一個正整數。 并且，相鄰的兩個級別間的比例是個固定值。 也就是說：所有級別的獎金數構成了一個等比數列。比如： 16,24,36,54 其等比值為：3/2現在，我們隨機調查了一些獲獎者的獎金數。 請你據此推算可能的最大的等比值。輸入格式： 第一行為數字 N (0<N<100)，表示接下的一行包含N個正整數 第二行N個正整數Xi(Xi<1 000 000 000 000)，用空格分開。 每個整數表示調查到的某人的獎金數額 要求輸出： 一個形如A/B的分數，要求A、B互質。表示可能的最大比例系數 測試數據保證了輸入格式正確，并且最大比例是存在的。例如，輸入： 3 1250 200 32程序應該輸出：25/4再例如，輸入： 4 3125 32 32 200程序應該輸出：5/2再例如，輸入： 3 549755813888 524288 2程序應該輸出：4/1資源約定： 峰值內存消耗 < 256M CPU消耗 < 3000ms請嚴格按要求輸出，不要畫蛇添足地打印類似： “請您輸入...” 的多余內容。所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。注意: main函數需要返回0 注意: 只使用ANSI C/ANSI C++ 標準， 不要調用依賴于編譯環境或操作系統的特殊函數。 注意: 所有依賴的函數必須明確地在源文件中 #include <xxx>， 不能通過工程設置而省略常用頭文件。提交時，注意選擇所期望的編譯器類型。 ————————————————————————————————————————————————————————————*/ // /* 等比數列：a0、a1、a2、a3、a4 等比數列的性質： a3 p —— ——> (———)^2 a0 q*/ #include<stdio.h> #include<iostream> #include<algorithm> #include<vector>using namespace std ; typedef long long LL ; int N ; LL data[100] ; struct Ratio{LL x,y ;Ratio(LL _x,LL _y):x(_x),(_y){LL _gcd = gcd(x,y) ;x /= _gcd ;y /= _gcd ;}LL gcd(LL a,LL b){if(b==0) return a ;return gcd(b,a%b) ;} } ; //存儲比值 vector<Ratio> ratios ;int main() {//處理輸入scanf("%d",&n) ;for (int i = 0; i < N; ++i) //掃描輸入數據 {scanf("%lld",&data[i]) ;}//排序sort(data,data+N) ;//兩兩比值，以分數形式存儲，vectorfor (int i = 0; i < N-1; ++i){if(data[i+1]!=data[i])//去重ratios.push_back(Ratio(data[i+1],data[]i)) ;}/*對第一個比值開1-..pow(極限為40)次方作為基數，如果這個基數的分子、分母的k1k2次方恰好是其他比值的分子分母的話，基數就是答案*/for (int pow = 0; pow <= 40; ++pow){Ratio ra0 = ratios[0] ;LL x = ra0.x ;LL y = ra0.y ;LL fx = extract(x,pow) ; //對LL fy = extract(y,pow) ; // if(fx==-1 |\ fy ==-1) continue ; //開不出，continue //能開，就要確認所有比值的分子是fx的整數次方，所有比值的分母是fy的整數次方//計px=getPow(xx,fx),py=getPow(yy,fy),要求必須是整數且px==pybool all_match = true ;// for (int i = 1; i < ratios.size(); ++i){LL xx = ratios[i].x ;LL yy = ratios[i].y ;LL px = getPow(xx,fx) ;LL py = getPow(yy,fy) ;if(px == -1 || py == -1 || px != py){all_match = false ;break ;}}if(all_match){Ratio ans = Ratio(fx,fy) ;cout << ans.x << "/" << ans.y << endl ;}return 0 ;}return 0 ; }//優化 + 完善 #include <stdio.h> #include <iostream> #include <vector> #include <map>using namespace std; typedef long long LL; int N; LL data[100];//結構體 struct Ratio {LL x, y;Ratio(LL _x, LL _y) : x(_x), y(_y) {LL _gcd = gcd(x, y);x /= _gcd;y /= _gcd;}LL gcd(LL a, LL b) {if (b == 0)return a;return gcd(b, a % b);} };vector<Ratio> ratios; map<LL, map<LL,LL> > all_ex;//all_ex[x][pow]==x開pow次方 map<LL, map<LL,LL> > all_log;//all_log[x][y]==log_y_x，y的多少次方是x？void init() //預處理 {for (int i = 2; i < 1e6; ++i) {//底數LL cur=(LL)i*i;int pow=2;while(cur<1e12){all_ex[cur][pow]=i;all_log[cur][i]=pow;pow++;cur*=i;}} }/*** 對x開pow次方* @param x* @param pow* @return*/ LL extract(LL x,LL pow) {if(pow==1)return x;if(x==1)return 1;if(all_ex[x].find(pow)!=all_ex[x].end())//意味著x可以開pow整數次方return all_ex[x][pow];elsereturn -1; }/*** 求log_base_x* @param base* @param x* @return*/LL log(LL base,LL x) {if(base==x)return 1;if(all_log[x].find(base)!=all_log[x].end())//意味著可以得打一個k，base的k次方是xreturn all_log[x][base];return -1; }int main(int argc, const char *argv[]) {init();freopen("/Users/zhengwei/CLionProjects/lanqiaobei2019/2016_C_A/data10/in8.txt","r",stdin);//處理輸入scanf("%d", &N);for (int i = 0; i < N; ++i) {scanf("%lld", &data[i]);}//排序sort(data, data + N);//處理只有兩項的特殊情況if(N==2){Ratio ans = Ratio(data[1], data[0]);cout << ans.x << "/" << ans.y << endl;return 0;}//求兩兩比值，以分數形式存儲，vectorfor (int i = 0; i < N - 1; ++i) {if (data[i + 1] != data[i])//去重ratios.push_back(Ratio(data[i + 1], data[i]));}//對第一個比值開1~..pow(極限為40).次方，作為基數，如果這個基數也是其他比值的基數的話，該基數就是答案for (int pow = 1; pow <= 40; ++pow) {Ratio ra0 = ratios[0];LL x = ra0.x;LL y = ra0.y;LL base_x = extract(x, pow);//對x開pow次方，作為基數，去嘗試LL base_y = extract(y, pow);//對y開pow次方，作為基數，去嘗試if (base_x == -1 || base_y == -1)continue;//開不出，continue//能開：就要去確認所有比值的分子是fx的整數次方，所有比值的分母是fy的整數次方//計px=getPow(xx,base_x),py=getPow(yy,base_y)，要求必須是整數且px==pybool all_match = true;for (int i = 1; i < ratios.size(); ++i) {LL xx = ratios[i].x;LL yy = ratios[i].y;LL log_x = log(base_x,xx);LL log_y = log(base_y,yy);if(base_y==1&&yy==1)log_y=log_x;if (log_x == -1 || log_y == -1 || log_x != log_y) {all_match = false;break;}}if (all_match) {Ratio ans = Ratio(base_x, base_y);cout << ans.x << "/" << ans.y << endl;return 0;}}return 0; }//【2016年B組C++小結】 /*********************************************************** 01【結果填空】煤球數目 ：枚舉+簡單計算* 02【結果填空】生日蠟燭 ：等差數列求和* 03【結果填空】湊算式 ：全排列* 04【代碼填空】快速排序 ：裸題* 05【代碼填空】抽簽 ：遞歸，明確參數的含義及參數的變化方向* 06【填空填空】方格填數 ：全排列 + check* 07【結果填空】剪郵票(**) ：dfs解決不了T型組合，全排列+dfs求矩陣中的連通塊* 08【編程題】四平方和 ：枚舉+優化* 09【編程題】交換瓶子(**) ：貪心* 10【編程題】最大比例(***) ：數論、等比數列、預處理**********************************************************/

?

轉載于:https://www.cnblogs.com/lx17746071609/p/10565609.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的[蓝桥杯]2016蓝桥省赛B组题目及详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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