第十二届蓝桥杯省赛第一场 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。

状态表示：

$d p [i] [j]$ 表示从前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;
}

第十二届蓝桥杯省赛 第一场 C++ B组 题解 （全）

A 空间

B 卡片

C 直线

D 货物摆放

E 路径

F 时间显示

G 砝码称重

H 杨辉三角形

I 双向排序

第十二届蓝桥杯省赛第一场 C++ B组题解（全）