第七届蓝桥杯C++B组省赛
1.煤球数目
有一堆煤球，堆成三角棱锥形。具体：
第一层放1个，
第二层3个（排列成三角形），
第三层6个（排列成三角形），
第四层10个（排列成三角形），
….
如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路
这个题目说是三角形，那么我们就不难找出规律了。具体看代码
代码
#include<iostream>
using namespace std;
const int N = 110;
int a[N];
int ans;
int main()
{
int n;
cin>>n;
for(int i=0;i<=n;++i)
{
a[i]=a[i-1]+i;
ans+=a[i];
}
cout<<ans<<endl;
return 0;
}
答案
171700
2.生日蜡烛
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？
请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路
暴力枚举开始年龄和结束年龄。
#include<iostream>
using namespace std;
const int N = 110;
int main()
{
for(int i=1;i<=N;++i)
{
int t = 0;
for(int j=i;;j++)
{
t+=j;
if(t==236)
{
cout<<i<<endl;
return 0;
}
if(t>236)
{
break;
}
}
}
return 0;
}
答案
26
3.凑算式
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。
思路
全排列+简单的判断
#include<iostream>
#include<vector>
using namespace std;
bool st[15];
vector<int> vec;
int ans;
double get(int l,int r)
{
int res = 0;
for(int i=l;i<=r;++i)
{
res = res*10+vec[i];
}
return res;
}
bool check()
{
double A = get(0,0);
double B = get(1,1);
double C = get(2,2);
double DEF = get(3,5);
double GHI = get(6,8);
if(A+B/C+DEF/GHI==10)
return true;
return false;
}
void dfs(int n)
{
if(n==9)
{
if(check())
ans++;
return;
}
for(int i=1;i<=9;++i)
{
if(!st[i])
{
vec.push_back(i);
st[i]=true;
dfs(n+1);
st[i]=false;
vec.pop_back();
}
}
}
int main()
{
dfs(0);
cout<<ans<<endl;
return 0;
}
答案
29
4. 快速排序
没什么说的
答案
swap(a,j,p);
5.抽签
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
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);
return;
}
for(i=0; i<=a[k]; i++){
for(j=0; j<i; j++) b[M-m+j] = k+'A';
______________________; //填空位置
}
}
int main()
{
int a[N] = {4,2,2,1,1,3};
char b[BUF];
f(a,0,M,b);
return 0;
}
思路
补全代码题：先复制粘贴到编辑器上再说。然后读一下代码。然后就做出来结束了
解释一下这个函数的参数：第一个参数不用说了；第二个参数表示的是第几个国家的代表团；第三个参数是说明还有多少个空缺席位；第四个也不用说了。
然后把代码补全，运行验证一下即可。
答案
#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
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);
return;
}
for(i=0; i<=a[k]; i++){
for(j=0; j<i; j++) b[M-m+j] = k+'A';
f(a,k+1,m-j,b); //填空位置
}
}
int main()
{
int a[N] = {4,2,2,1,1,3};
char b[BUF];
f(a,0,M,b);
return 0;
}
6.方格填数
如图，如下的10个格子，填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）一共有多少种可能的填数方案？
请填写表示方案数目的整数。
思路
全排列+简单的判断即可
代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[10];
int b[3][4];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
bool check()
{
//填入数字
int k=0;
for(int i=0;i<3;++i)
{
for(int j=0;j<4;++j)
{
if((i==0&&j==0)||(i==2&&j==3))continue;
b[i][j]=a[k++];
}
}
//开始判断
for(int i=0;i<3;++i)
{
for(int j=0;j<4;++j)
{
if((i==0&&j==0)||(i==2&&j==3))continue;//注意这里，这两个不需要判断
for(int d=0;d<8;++d)
{
int x = i+dx[d];
int y = j+dy[d];
if(x<0||x>=3||y<0||y>=4)continue;
if((x==0&&y==0)||(x==2&&y==3))continue;//谨记那两个空位也是不合法位置
if(b[x][y]==b[i][j]+1)return false;
}
}
}
return true;
}
int main()
{
int ans = 0;
for(int i=0;i<10;++i)a[i]=i;
do{
if(check())
ans++;
}while(next_permutation(a,a+10));
cout<<ans<<endl;
return 0;
}
答案
1580
7.剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合> 格的剪取。
思路
全排列+floodfill
代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
int a[3][4]={0,0,0,0,0,0,0,1,1,1,1,1};
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool st[3][4];
bool bfs()
{
queue<PII> q;
memset(st,0,sizeof st);
for(int i=0;i<3;++i)
{
for(int j=0;j<4;++j)
{
if(a[i][j]==1)
{
q.push(make_pair(i,j));
st[i][j]=true;
i=100;
break;
}
}
}
int res = 0;
while(q.size())
{
PII t = q.front();
q.pop();
res++;
for(int i=0;i<4;++i)
{
int aa = dx[i]+t.x;
int bb = dy[i]+t.y;
if(aa<0||aa>=3||bb<0||bb>=4)continue;
if(st[aa][bb])continue;
if(a[aa][bb]==0)continue;
q.push(make_pair(aa,bb));
st[aa][bb]=true;
}
}
return res==5;
}
int main()
{
int ans = 0;
do{
if(bfs())
ans++;
}while(next_permutation(a[0],a[0]+12));
cout<<ans<<endl;
return 0;
}
答案
116
8.四平方和定理
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多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 为联合主键升序排列，最后输出第一个表示法
思路
二分 二分一定要记得排序hh
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2500010;
struct Node{
int l,r,w;
bool operator<(const Node& W)const
{
if(W.w!=w)return w<W.w;
if(W.l!=l)return l<W.l;
return r<W.r;
}
}sum[N];
int main()
{
int n;
cin>>n;
int k=0;
for(int c=0;c*c<=n;++c)
{
for(int d=c;c*c+d*d<=n;++d)
{
sum[k].w=c*c+d*d;
sum[k].l=c;
sum[k].r=d;
k++;
}
}
sort(sum,sum+k);
for(int a=0;a*a<=n;++a)
{
for(int b=a;b*b+a*a<=n;++b)
{
int t = n-a*a-b*b;
int l=0,r=k-1;
while(l<r)
{
int mid = l+r >>1;
if(sum[mid].w<t)l=mid+1;
else r=mid;
}
if(sum[l].w==t)
{
cout<<a<<" "<<b<<" "<<sum[l].l<<" "<<sum[l].r<<endl;
return 0;
}
}
}
return 0;
}
9.交换瓶子
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：
2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
思路
如果把至少去掉，可能大多数人就都会做了，我也被至少困扰了很久，但是其实对于我们菜鸡来说，能有一种方法算出来交换多少次就很好了，作对血赚。不过我感觉不做无效操作的话，求出来的一般都是至少的情况。
代码
#include<iostream>
using namespace std;
const int N = 10010;
int a[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
int ans = 0;
for(int i=1;i<=n;++i)
{
while(a[i]!=i)
{
swap(a[a[i]],a[i]);
ans++;
}
}
cout<<ans<<endl;
return 0;
}
10.最大比例
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互质。表示可能的最大比例系数
测试数据保证了输入格式正确，并且最大比例是存在的。
思路
思路其实很简单，关键是代码对分数的处理。
思路：求出相邻的数字之间的比例，然后取共同的q就行。（共同的q,就是假如有两个数x=q^a, y=q^b，那么求出这个q）。至于分数的处理，看代码。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
typedef long long LL;
LL up[N],down[N];
LL a[N];
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
LL qgcd(LL a,LL b)
{
if(a<b)swap(a,b);
if(b==1)return a;
return qgcd(b,a/b);
}
int n;
int len;
int main()
{
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
sort(a,a+n);
for(int i=1;i<n;++i)
{
LL d = gcd(a[i],a[i-1]);
up[len]=a[i]/d;
down[len]=a[i-1]/d;
len++;
}
LL u = 1,d=1;
for(int i=0;i<len;++i)
{
u = qgcd(u,up[i]);
d = qgcd(d,down[i]);
}
cout<<u<<"/"<<d<<endl;
return 0;
}
剪邮票那题为啥不用判断只连一个角的情况