C++省赛B组个人题解（部分）
试题A：空间
题目
答案：67108864
分析
计算机组成原理题，一上来就栽跟头了。。。
1byte=8bits,Bit意为"位"或"比特"，是计算机运算的基础；
Byte意为"字节"，是计算机文件大小的基本计算单位；
8个二进制位构成1个"字节(Byte)"，即1Byte=8bit
所以1个32位二进制数占4个Byte。
答案为
试题B：卡片
题目
答案：3181
分析
打卡题
#include <bits/stdc++.h>
using namespace std;
int a[10];
bool ok(int x) //每个数消耗卡片
{
while(x)
{
int temp = x % 10;
if(a[temp])
{
a[temp]--;
x /= 10;
}
else
return 0;
}
return 1;
}
int main()
{
fill(a, a + 10, 2021); //总共的卡片数
for (int i = 1;; i++)
{
if(ok(i))
continue;
else
{
cout << i - 1;
break;
}
}
return 0;
}
试题C：直线
题目
答案：41255（不确定）
分析
一看像个数学题，可是又推不出数学公式，然后就分三种情况讨论，哈希统计个数，测试样例和自己测试的小样例都过了，不过好像数据大了，double精度不够用，不知道对不对
1.平行于y轴 直线表达式为x=？？？
2.平行于x轴 直线表达式为y=？？？
3.普通一次函数 直线表达式为y=kx+b
#include <bits/stdc++.h>
using namespace std;
set<pair<double, double> > ss;//普通的直线
set<double> dx,dy;//两种特殊的直线
struct point
{
double x, y;
};
void solve(point a,point b)
{
if(a.x==b.x) //平行于y轴
dx.insert(a.x);
else if(a.y==b.y) //平行于x轴
dy.insert(a.y);
else //计算表达式y=kx+bb
{
double k = (b.y - a.y) / (b.x - a.x);
double bb = a.y - k * a.x;
ss.insert(pair<double, double>(k, bb));
}
}
int main()
{
vector<point> v;
for (int i = 0; i <= 19;i++)
{
for (int j = 0; j <= 20;j++)
{
point temp = {
i * 1.0, j * 1.0};//转换为double
v.push_back(temp);
}
}
int len = v.size();
for (int i = 0; i < len;i++) //枚举所有的直线
{
for (int j = i + 1; j < len;j++)
{
solve(v[i], v[j]);
}
}
cout << dx.size() + dy.size() + ss.size(); //三种直线集合个数求和
return 0;
}
试题D：货物摆放
题目
答案：2430
分析
首先，这个数非常大，达到了1e16级别，所以直接枚举，是不可能的
题目要求3个数相乘，得到这个数，因此，这三个数必定是这个数的因子，所以我想到了首先求出这个数的所有因子。因子数求法可以参考我的文章求因子数
然后求因子复杂度只需要sqrt（n）级别，也就是1e8，这个复杂度是可以接受的，最后在求到的因字数中，枚举三个数的乘积是否等于这个数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll n = 2021041820210418;
int main()
{
set<ll> fac; //存放因子
for (int i = 1; i <= sqrt(n);i++)
{
if(n%i==0)
{
fac.insert(i);
fac.insert(n / i);
}
}
vector<ll> v; // 转存到数组里面，方便操作
for(ll e:fac) //foreach遍历
v.push_back(e);
int len = v.size();
int cnt = 0;
for (int i = 0; i < len;i++) //三重循环，枚举因子数乘积
for (int j = 0; j < len;j++)
for (int k = 0; k < len;k++)
{
if(v[i]*v[j]*v[k]==n)
cnt++;
}
cout << cnt;
return 0;
}
试题E：路径
题目
答案：10266837
分析
一开始没看懂题，跳过去了，最后20分钟才想起思路，寒假刷pat的题库终于在蓝桥起作用了，有惊无险。。。
考点就是求最小公倍数和最短路径算法dijstra
推荐柳神的最短路径算法模板dfs最短路径
不过此题也可以用dp做，过程貌似更简洁
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e12;
int vis[2050];
ll e[2050][2050], dis[2050];
ll gcd(ll a,ll b) //求最大公因数
{
return a % b == 0 ? b : gcd(b, a % b);
}
ll lcm(ll a,ll b) //求最小公倍数
{
return a * b / gcd(a, b);
}
int main()
{
fill(dis, dis + 2050, inf);
fill(e[0], e[0] + 2050 * 2050, inf);
for (int i = 1; i <= 2021;i++)
{
for (int j = 1; j <= 21;j++) //21步以内有效
{
int k = i + j; //i为起点，k为终点
if(k>2021)
break;
e[i][k] = e[k][i] = lcm(i, k);
}
}
dis[1] = 0;
//最短路径模板 dijstra算法
for (int i = 1; i <= 2021;i++)
{
ll u = -1, minn = inf;
for (int j = 1; j <= 2021;j++)//找到起点
{
if(!vis[j]&&dis[j]<minn)
{
minn = dis[j];
u = j;
}
}
if(u==-1)
break;
vis[u] = 1;
for (int v = 1; v <= 2021;v++)
{
if(!vis[v])
dis[v] = min(dis[v], e[u][v] + dis[u]);
}
}
cout << dis[2021];
return 0;
}
试题F：时间显示
题目
分析
打卡题，注意题目说法，毫秒直接舍去
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
ll n;
int mod = 3600 * 24;//一天的秒数
cin >> n;
n /= 1000; //舍去毫秒
n %= mod;
int h = (n / 3600) % 24;
int m = ((n % 3600)/60)%60;
int s = n % 60;
printf("%02d:%02d:%02d", h, m, s);
return 0;
}
试题G：砝码称重
题目
分析
dp题，看了5分钟没思路，跑路了
试题H：杨辉三角形
题目
分析
看到这题心就凉了，可能有数学公式，但是考试时我肯定推不出来，就直接暴力模拟了，只开了一维数组，每开辟新的一行，就复制一份，判断每个元素是否等于n
（大数据超时）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a;
int main()
{
ll n;
cin >> n;
ll cnt = 2;
if (n == 1)
cout << 1;
else
{
a.push_back(1); //第二层
a.push_back(1);
while (1)
{
cnt++; //第cnt层
vector<ll> temp(a); //复制上一份
for (ll i = 1; i < cnt - 1; i++)
{
temp[i] = a[i] + a[i - 1];
if (temp[i] == n) //找到了这个数
{
ll ans = cnt* (cnt - 1) / 2;
ans += (1 + i);
cout << ans;
return 0;
}
}
temp.push_back(1); //末尾元素
a = temp;
}
}
return 0;
}
试题I：双向排序
题目
分析
直接一步步排序的，看上去太简单了，希望没有坑。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool cmp(int a,int b)
{
return a > b;
}
int main()
{
int n, m;
cin >> n >> m;
int a[n];
for (int i = 0; i < n;i++)
a[i] = i + 1;
for (int i = 0; i < m;i++)
{
int p, q;
scanf("%d %d", &p, &q);
if(p==0)
sort(a, a + q,cmp);
else
sort(a + q - 1, a + n);
}
for (int i = 0; i < n;i++)
{
printf("%d", a[i]);
if(i!=n-1)
printf(" ");
}
return 0;
}
试题J：括号序列
题目
分析
dp，白给。输出了s长度等于1~3的答案，希望能混到测试样例。
个人总结：
第二次参加蓝桥杯（B组省赛），今年题明显比往年难了很多，考的知识面也覆盖广了。难道是蓝桥杯排名不断上升，题也跟着变了味？不过省赛总体思路还是暴力加一些基本的数学知识。这次第一题完全就是考概念。。。第一题就白给了，确实蛮打击人的。最后一次参加蓝桥了，希望不会白给。
转载：https://blog.csdn.net/qq_44577309/article/details/115834519