第十二届蓝桥杯省赛 第一场 C++ B组 题解 （全）
第十二届蓝桥杯
A 空间
int，四个字节，不知道可以用sizeof，
1MB=1024KB，1KB=1024B；
code：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
signed main() {
cout << 256 * 1024 * 1024 / 4 << endl;
return 0;
}
//答案：67108864
B 卡片
循环暴力，如果当前数不能构成，就结束。
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
int a[11];
void solve() {
for (int i = 0; i < 10; i++) {
a[i] = 2021;
}
for (int i = 1; i; i++) {
int tmp = i;
while (tmp) {
if (a[tmp % 10] > 0)
a[tmp % 10]--;
else {
cout << i - 1 << endl;
return;
}
tmp /= 10;
}
}
}
signed main() {
solve();
return 0;
}
//3181
C 直线
一条直线，由斜率和一点就能确定。所以，暴力枚举每两个点算斜率和直线。但是double精度不够导致算得不太一样。
#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; //错误解 double精度丢失
//正解 运用两个点的坐标提升精度
double bb = (a.y * b.x - a.x * b.y) / (b.x - 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;
}
//答案：40257
D 货物摆放
就是找三个因子相乘会等于 给定的数，先预处理所有的因子，然后枚举所有因子，满足则ans++。
code：
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
#define int long long
signed main() {
vector<ll> arr;
ll n=2021041820210418;
for(ll i=1;i<=n/i;i++){
if(n%i==0){
if(i*i!=n) arr.push_back(i),arr.push_back(n/i);
else arr.push_back(i);
}
}
cout<<arr.size()<<endl;
int len=arr.size();
int ans=0;
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
for(int k=0;k<len;k++){
if(arr[i]*arr[j]*arr[k]==n) ans++;
}
}
}
cout<<ans<<endl;
}//2430
E 路径
这个题目采用的Dijkstra算法求最短路的问题。2021个节点，边权为最小公倍数。
最小公倍数：
a 和 b 的最小公倍数 lcm(a,b)=a*b/gcd(a,b);
Dijkstra算法采用邻接矩阵的方式存图，dist[i] 表示 1 节点到 i 节点的最短路距离。
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 将 1 号点的距离初始化为 0
for (int i = 0; i < n; i++) {
int t = -1; // t = -1 表示还没有确定
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
}
st[t] = true; // 将 t 加入到当前已确定最短距离的点的集合中
// 用 t 更新其出边所到达的点到源点的最短距离
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Code:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2030;
int g[N][N];
int dist[N];
bool st[N];
int gcd(int m, int n) {
return n ? gcd(n, m % n) : m;
}
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < 2021; i++) {
int t = -1;
// 找出距离源点最近的点
for (int j = 1; j <= 2021; j++) {
if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
}
st[t] = true;
// 遍历 t 的所有出边
for (int j = 1; j <= 2021; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
return dist[2021];
}
int main() {
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= 2021; i++) {
for (int j = 1; j <= 2021; j++) {
if (i != j && j - i <= 21) g[i][j] = i * j / gcd(i, j);
}
}
cout << dijkstra() << endl;
return 0;
}
//答案：10266837
F 时间显示
水题，随便写写就行了。1s=1000ms;
对3600取模，对60取模。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
LL n;
cin >> n;
n /= 1000;
n %= 86400;
int h = n / 3600;
n %= 3600;
int m = n / 60;
int s = n % 60;
printf("%02d:%02d:%02d\n", h, m, s);
return 0;
}
G 砝码称重
动态规划，线性DP。
状态表示：
表示从前i个中选，称出重量为 j 的方案数。
递推方程：
第 j 个物品有三种选择，不选，选择放入左边，选择放入右边。
dp[i][j]=dp[i-1][j]||dp[i-1][abs(j-w)]||dp[i-1][j+w];
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 2e5 + 10;
int sum;
int n;
int w[N];
bool f[N][M];
int main() {
cin>>n;
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
sum+=w[i];
}
f[0][0]=true;
for (int i = 1; i <= n;i++)
for (int j = 0; j <=sum;j++)
f[i][j]=f[i-1][j]||f[i-1][j+w[i]]||f[i-1][abs(j-w[i])];
//只要有一个非空,f[i][j]就非空
int ans = 0;
for (int i = 1; i <=sum;i++)
if(f[n][i])ans++;//不为零说明可以选出这个质量的砝码
cout << ans;
return 0;
}
H 杨辉三角形
找规律题。
组合数和杨辉三角：第i行第j列的数都是组合数C(i, j) （i，j从0开始）
C(n, 1) = n --> 对应从左向右看斜着的第二列！ ---> 一定有解
由于杨辉三角左右对称（C(a, b) == C(a, a-b)），又由于找第一次出现，因此一定在左边，右边可以直接删掉！
1 ---> C(0, 0)
1
1 2 ---> C(2, 1)
1 3 ---> C(2n, n)
1 4 6 ---> C(4, 2)
1 5 10
1 6 15 20 ---> C(6, 3)
n最大1e9，C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行即可！
性质：
每一斜行从上到下递增
每一横行从中间到两边依次递减
因此我们直接从中间对称轴倒序二分找起即可!
C(r, k)对应第 (r + 1) * r / 2 + k + 1 个数
code:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
LL C(int a, int b)//暴力计算组合数
{
LL res = 1;
for (int i = a, j = 1; j <= b; i --, j ++ )
{
res = res * i / j;
if (res > n) return res;
}
return res;
}
bool check(int k)
{
LL l = k * 2, r = max((LL)n, l);
while (l < r)//斜行二分，
{
LL mid = l + r >> 1;
if (C(mid, k) >= n) r = mid;
else l = mid + 1;
}
if (C(r, k) != n) return false;//找不到下一行
cout << r * (r + 1) / 2 + k + 1 << endl;//找到输出
return true;
}
int main()
{
cin >> n;
//枚举每一斜行
for (int k = 16; ; k -- )
if (check(k)) break;
return 0;
}
I 双向排序
算法:栈 + 找规律 这题也是思维题，赛后找规律才找出来，不需要用线段树或者 SplaySplay，只用一个栈也可以写 如果暴力用 sortsort 的话会超时 假设这是我们的原序列
优化一： 由于一开始的序列是升序的，所以如果一开始的操作是后缀操作的话是没有意义的，序列是不会改变的，所以我们从前缀操作开始看，红色为将要操作的前缀序列
如果有连续的前缀操作，我们发现只需要进行最长的一个前缀操作即可，因为短的前缀操作后，长的还是要进行操作，为何不直接进行最长的前缀操作呢，后缀操作同理，我们把所有的操作节点存进栈，有两个成员变量，一个是当前操作是前缀操作还是后缀操作，另一个是操作的边界
优化二： 若进行到下图这种情况时
蓝色为原序列，红色为最长连续前缀，橙色为最长连续后缀
从下图我们发现
- 原序列 A 段严格大于 B 段
- A 段 == A1 段， B 段 == B1 段
- 所以 A1 段严格大于 B1 段
- A2段 == A1 段
- 所以 A2 段严格大于 C 段，所以后缀升序操作（橙色）只需要操作 C 段即可
对于前缀操作同理 ，只需要操作 C 段即可
优化三： 当出现下面这种情况时
也就是在进行一次前缀操作和后缀操作后，下一次的前缀操作在上一次的前缀操作的节点后，这个时候我们可以把前两次操作给删去，直接进行这一次的前缀操作，因为上一次的后缀操作和前缀操作都包含在了这一次的前缀操作内，前两次操作等于是没用的，所以我们只需要保留当前操作即可
另外，我们可以发现在我们一次次操作的过程中，操作的区间是在慢慢变小的，每次操作的时候，序列总有一部分是不需要进行操作的，我们也就可以用一个变量来递减的填入数组中
暂时还没理解透，存一个代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
PII stk[N];
int ans[N];
int main()
{
scanf("%d%d", &n, &m);
int top = 0;
while (m -- )
{
int p, q;
scanf("%d%d", &p, &q);
if (!p)
{
while (top && stk[top].x == 0) q = max(q, stk[top -- ].y);
while (top >= 2 && stk[top - 1].y <= q) top -= 2;
stk[ ++ top] = {0, q};
}
else if (top)
{
while (top && stk[top].x == 1) q = min(q, stk[top -- ].y);
while (top >= 2 && stk[top - 1].y >= q) top -= 2;
stk[ ++ top] = {1, q};
}
}
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i ++ )
{
if (stk[i].x == 0)
while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;
else
while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ;
if (l > r) break;
}
if (top % 2)
while (l <= r) ans[l ++ ] = k -- ;
else
while (l <= r) ans[r -- ] = k -- ;
for (int i = 1; i <= n; i ++ )
printf("%d ", ans[i]);
return 0;
}
算法专题 文章被收录于专栏
怕忘记，好复习
美团公司氛围 1837人发布