2018年蓝桥杯A组C/C++决赛题解

2018年第九届蓝桥杯A组C/C++决赛题解

2018年蓝桥杯A组C/C++决赛题目(不含答案)

1：三角形面积

画个图，求三角形面积，可以用外接长方形 - 其他多余区域面积

当然网上很多用海伦公式啊什么的都可以的

#include<bits/stdc++.h> using namespace std; double x1 = 2.3; double yy1 = 2.5; double x2 = 6.4,y2 = 3.1; double x3 = 5.1,y3 = 7.2; int main(){ double a = x2 - x1; double b = y3 - yy1; double c = x3 - x1; double d = x2 - x3; double e = y2 - yy1; double f = y3 - y2; cout<<a*b<<endl; double s = a * b - a * e * 0.5 - b * c * 0.5 - d * f * 0.5; cout<<s<<endl; return 0; } //8.795

 
 

2：阅兵方阵

枚举
题意是：将一个数分成两个平方数相加，求自然数中一共能分12组的最小值
预处理所以平方数，枚举就可以了，还要注意，这里要分解成12组不同的数，我们枚举时会计算两个平方数交换的次数，所以算成12*2组就可以了。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 1e7+10; ll can[maxn]; void init(){ for(ll i=1;i<=1e6;i++){ if(i * i > maxn) break; can[i*i] = 1; } } int main(){ init(); //能组成12个 for(int k = 1105;k<=200000;k++){ int ans = 0; for(int a=1;a<=k;a++){ if(!can[a]) continue; if(!can[k - a]) continue; ans++; } if(ans == 12*2){ cout<<k<<endl; break; } } return 0; } //5525 a 和 k-a 交换 //160225 不能交换

 
 

3：找假币

我做的答案肯定出错了，我懒得分析了
网上也都是这个答案，但是答案确实是错的啊：balance(data[0] + data[1] + data[2] , data[3] + data[4] + data[5])
反例：11111121

 
 

4：约瑟夫环

30% - 80%数据点可以用队列暴力做的

设置变量计数器t
如果t == k：队头出队, t赋值为1
否则t++,对头出队再进队尾

100%转换成约瑟夫数学问题了，见题解：https://blog.csdn.net/u011500062/article/details/72855826

30%暴力做法代码：

#include<bits/stdc++.h> using namespace std; /* 使用队列模拟 能过部分数据 设置变量计数器t 如果t == k：队头出队, t赋值为1 否则t++,对头出队再进队尾 */ queue<int> q; int n,k; int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ q.push(i); } int t = 1; while(q.size() > 1){ int front = q.front(); if(t == k){ q.pop(); t = 1; }else{ q.pop(); q.push(front); t++; } } cout<<q.front()<<endl; return 0; }

 
 

5：自描述序列

30%数据点暴力
100%递推 见题解：https://blog.csdn.net/metaphysis/article/details/6532638

30%暴力做法代码：

#include<bits/stdc++.h> using namespace std; //模拟 30%数据 int n; vector<int> v; void init(){ v.push_back(1); v.push_back(1); v.push_back(2); v.push_back(2); } int main(){ cin>>n; init(); int ans = 4; for(int i=3;i<=n;i++){ int t = v[i]; if(ans < n){ for(int j=1;j<=t;j++){ v.push_back(i); } ans += t; }else{ break; } } cout<<v[n]<<endl; return 0; }