第七题：剪邮票
题目描述
如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
题目分析
直接搜索感觉很难实现,还要考虑去重和回溯的问题. 我们采用的方式是 全排列+深搜
可以创建一个数组,存放5个1,7个0,然后我们对其进行全排列(next_permutation()),判断该情况是否成立
如何判断:将一维数组转变成二维数组,然后进行深搜,最后统计连通块的个数.
如果只有一个连通块,说明该情况成立,否则循环判断下一个排列数.
题目代码
#include<bits/stdc++.h> using namespace std; int stamp[12] = { 0,0,0,0,0,0,0,1,1,1,1,1 }, map1[4][5];//一共12张邮票,需要剪下来五张 int NEXT[4][2] = { -1,0,//上 1,0,//下 0,-1,//左 0,1//右 }; int ans = 0;//方案数 int book[4][5];//标记是否访问过 void dfs(int x, int y) { //结束条件 if (map1[x][y] == 0) { return;//结束 } for (int i = 0; i < 4; i++) { int tx = x + NEXT[i][0]; int ty = y + NEXT[i][1]; if (tx < 1 || tx>3 || ty < 1 || ty>4) { //判断是否越界 continue; } if (!book[tx][ty]) { book[tx][ty] = 1;//进行标记 dfs(tx, ty);//继续深搜 } } } bool check() { //数据的初始化 memset(book, 0, sizeof(book)); int cnt = 0;//邮票连通块的个数 int w = 0; //将一维数组转成二维 for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 4; j++) { map1[i][j] = stamp[w++]; } } for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 4; j++) { if (map1[i][j] == 1 && !book[i][j]) { book[i][j] = 1;//这里一定要注意,先标记后深搜,不然会陷入死循环呢. dfs(i, j);//进行深搜 // book[i][j] = 1; cnt++; } } } return cnt == 1;//如果只有一个连通块则返回true,否则返回false } int main() { do { if (check()) { ans++; } } while (next_permutation(stamp, stamp + 12)); cout << ans << endl; return 0; }
参考答案
116
第八题：四平方和
题目描述
四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多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
题目分析
暴力枚举+剪枝
数据量是 5*10^6,直接暴力枚举必定爆!可以采用以下剪枝
根据四平方和定理, 数据a,b,c,d范围都是 <= sqrt(n)
写四层for必定超时,最后一层可以用 n - (a*a + b*b + c*c) 表示,这样就少了一个循环.
第二、三层开始进行剪枝约束。只要值超过 n,则直接break.
最后一个循环中判断a,b,c确定后的d是不是整数.需要用到强制转换.
注意:
double类型的数据强制转换没有误差,但运行运算时可能出现误差.
sqrt()的返回值是double类型
计算机1s大约运行10^8次,可以根据这个简单判断程序是否超时.
题目代码
#include<bits/stdc++.h> using namespace std; int main(){ int n;//最多三个循环+剪枝操作 cin>>n; int q = (int)sqrt(n);//sqrt的返回值是double类型 for(int a = 0;a<=q;a++){ for(int b = 0; b<=q;b++){ //开始第一轮剪枝 if(a*a+b*b>n) {//直接结束循环,因为后面的数更大 break; } for(int c = 0; c <=q;c++) { //开始第二轮剪枝 if(a*a+b*b+c*c > n){ break; } double d = sqrt(n - (a*a+b*b+c*c)) ;//判断d是否可以分解成两个整数的平方 if(d==(int)d){ cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl; return 0; } } } } return 0; }
第九题：交换瓶子
题目描述
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。经过若干次后，使得瓶子的序号为：1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
输入样例
样例1
5 3 1 2 5 4 3
样例2
5 5 4 3 2 1 2
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
题目分析
使用一个标记数组,在输入元素时,记录元素的位置.之后遍历排序时,如果元素和该位置A应该放置的元素B不同时,根据标记数组找到元素B位置,和当前元素A进行交换. 时间复杂度为 O ( n ) O(n)O(n).
题目代码
#include<bits/stdc++.h> using namespace std; const int M = 10000+5; int arr[M],book[M];//book:标记数组,记录元素的所在. arr:原始数组 int main(){ int n,ans; ans = 0; cin>>n; for(int i = 1; i <= n;i++){ cin>>arr[i]; book[arr[i]] = i; } for(int i = 1; i<= n;i++) { if(arr[i]!=i){ swap(arr[i],arr[book[i]]); ans++; } } cout<<ans<<endl; return 0; }
第十题：最大比例
题目描述
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：16,24,36,54 其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。
输入格式：
第一行为数字N，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额
要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数
测试数据保证了输入格式正确，并且最大比例是存在的。
输入样例
样例1
3 1250 200 32 25/4
样例2
4 3125 32 32 200 5/2
样例3
3 549755813888 524288 2 4/1
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
题目分析
题目代码
待续...
备注:由于蓝桥杯不再考察补全代码题型，所以未整理总结其思路
如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客
