[蓝桥杯]2016蓝桥省赛B组题目及详解

[蓝桥杯]2016蓝桥省赛B组题目及详解

/*———————————————————————————————————————————————————————————【结果填空题】T1 (分值：3)题目：煤球数目有一堆煤球，堆成三角棱锥形。具体：第一层放1个，第二层3个（排列成三角形）,第三层6个（排列成三角形）,第四层10个（排列成三角形）,....如果一共有100层，共有多少个煤球？请填表示煤球总数目的数字。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。1 * (1)2 *** (3)3 ****** (6)4 ********** (10)5 ..............(15)————————————————————————————————————————————————————————————*////** * pre 定义上一层 * plus 定义增量差值 */#includeusing 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+=pre plus++ ; } cout << sum << endl ; return 0;}//结果：171700/*———————————————————————————————————————————————————————————【结果填空题】T2 (分值：5)题目：生日蜡烛某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了236根蜡烛。请问，他从多少岁开始过生日party的？请填写他开始过生日party的年龄数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。————————————————————————————————————————————————————————————*////*思路：236 i ~ jfor(i:100)for(j:100)等差数列求和：(i+j)/2*(j-i-1)(a0+a0*(n-1)*d/2)*n*/#includeusing 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 DEFA + --- + ------- = 10 C GHI （如果显示有问题，可以参见【图1.jpg】） 这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。比如：6+8/3+952/714 就是一种解法，5+3/1+972/486 是另一种解法。这个算式一共有多少种解法？注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。————————————————————————————————————————————————————————————*/////全排列#include#includeusing 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#includeusing 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 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(ix); if(i>=j) break; swap(a,i,j); } /*代码填空处 swap(a,p,j) ; // ______________________; */ return j;}void quicksort(int a[], int p, int r){ if(p#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; jusing 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*/#includeusing 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 <结果思路2：暴力枚举，所有的五张组合，检查它们是不是一个连通块。 */// 12/13 寒假作业 12/5 dfs/*思路1： 生成的方法有太多的重复，效率低下//此题和13年剪格子有相似之处，但是那个题的限制条件是格子数值之和为总和的一半，此题则限制只能是5个格子//单纯的dfs无法解决T字型连通方案//本题的解决办法是，找出任意5个格子，判断是否连通*/#include #include 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));//将相应位置标注为1 for (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 #include #include 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 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; } else return 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<#include 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]){//没有被用过的元素可以抓入到path vis[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^27 = 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资源约定：峰值内存消耗 < 256MCPU消耗 < 3000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。提交时，注意选择所期望的编译器类型。————————————————————————————————————————————————————————————*///枚举+优化 //优化：采用缓存来空间换时间/*思路1：枚举abcd for(a) 0~a^2 for(b) 0~b^2 for(c) 0~c^2 for(d) 0~d^2 */#include#include#include

Talk is cheap. Show me the code

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。