2024第十五届蓝桥杯 C/C++ B组参赛经历分享（以及部分题解）

前言

emmmmmm，dp杯居然不考dp了，蓝桥一直没怎么出过的高精度居然也考了（当时居然因为没太复习那块知识直接模拟混分了），题量也改了，总的来说反而简单了？。。。还好天津竞赛弱省，但愿能够省一吧。。。（图灵保佑）

好那么进入正题

第一题

好那么好，小水题一道(50 * 49 / 2)- (7 * 6 / 2)=1204,cout 出去,过啦！！（此处配有英雄哥圣音）

第二题

好，过过过过过过(卡壳)，过不了一点啊啊啊啊啊啊啊，很数学的一道题，原谅我这烂数学，此处只能引用某乎大佬的推理过程

大佬的思路真是清清又晰晰啊。。。。我的烂代码写的判断四个方向，转来转去转来转去，也没能得出答案

第三题

好那么好，蓝桥总是能在我快要崩溃的时候让我找回自信，很简单的一个模拟题，1e7的数据压根爆不了一点，吐槽一嘴：蓝桥正赛居然能遇见这么好写的题目了吗。。。

#include<iostream>
using namespace std;
bool is_good(int n){
	int flag = 1;
	while(n){
		if((n%10)%2 != flag++ %2){
			return false;
		}
		n /= 10;
	}
	return true;
}
int n,res;
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++){
		if(is_good(i))
			res++;
	}
	
	cout << res;
	return 0;
}

第四题

嘿，不看数据量还真以为蓝桥要沦落为水赛了嘿，这刚一看不来个小白都会写吗，转头就是个暴击

高精度还忘了，但愿前50%错不了

第五题

很好的数论，使我的大脑旋转，爱来自蓝桥。很想知道大佬们怎么一眼就看出这个式子等于gcd(a,b,c)的，我赛场上直接暴力了，不过就这个数据量来看，数据量再大一点就会爆炸，（再近一点靠近点快被融化）(bushi)愿kunkun保佑我骗分

第六题

好，我真是太喜欢这种不在题目里玩一点心眼子，直接告诉你该干嘛的搜索题目了，数据量N小于等于10，那么我们直接上dfs ，走起

#include <iostream>
#include<set>
#include<vector>
using namespace std;
int f[8][2] = {
    {-1, 0} ,
    {-1, 1} ,
    {0 , 1} ,
    {1 , 1} ,
    {1 , 0} ,
    {1 ,-1} ,
    {0 ,-1} ,
    {-1,-1}
};
vector<int> ans;
set<pair<int, int>> se;
int a[12][12], flag = 1;
bool vis[12][12];
int n, k;
void dfs(int x, int y) {
    if (flag == 0) {
        return;
    }
    if (x == n && y == n && ans.size() == n * n - 1) {
        flag = 0;
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i];
        }
        return;
    }
    if (x == 0 || y == 0 || x > n || y > n) {
        return;
    }
    for (int i = 0; i < 8; i++)
    {
        int gox = x + f[i][0];
        int goy = y + f[i][1];
        int t = (x - 1) * n + y, to = (gox - 1) * n + goy;
        pair<int, int> road({ t,to });
        if (vis[gox][goy] == false && (a[x][y] + 1) % k == a[gox][goy] && se.find(road) == se.end()) {
            vis[gox][goy] = true;
            ans.push_back(i);
            if (i == 1) {
                se.insert({ t + 1,t - n });
                se.insert({ t - n,t + 1 });
            }
            else if (i == 3) {
                se.insert({ t + 1,t + n });
                se.insert({ t + n,t + 1 });
            }
            else if (i == 5) {
                se.insert({ t - 1 ,t + n });
                se.insert({ t + n,t - 1 });
            }
            else if (i == 7) {
                se.insert({ t - 1,t - n });
                se.insert({ t - n,t - 1 });
            }

            dfs(gox, goy);

            if (i == 1) {
                se.erase({ t + 1,t - n });
                se.erase({ t - n,t + 1 });
            }
            else if (i == 3) {
                se.erase({ t + 1,t + n });
                se.erase({ t + n,t + 1 });
            }
            else if (i == 5) {
                se.erase({ t - 1 ,t + n });
                se.erase({ t + n,t - 1 });
            }
            else if (i == 7) {
                se.erase({ t - 1,t - n });
                se.erase({ t - n,t - 1 });
            }
            vis[gox][goy] = false;
            ans.pop_back();
        }
    }
    return;
}
int main()
{
    cin >> n >> k;
    vis[1][1] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    dfs(1, 1);
    if (flag) {
        cout << -1;
    }
    return 0;
}

我的acmer学长告诉我这样写常数太大了，容易炸，但愿还能混过前80%。。但是dotcpp上的民间数据倒是确确实实ac过去了，又是听天由命的一集，提一嘴，路径不让交叉的存储方法我看有大佬写的四维数组来标记，也就是记录起点(x0,y0)以及终点(x1,y1) 我更倾向于用(x-1) * n + y把他们弄成编号 ,虽然当时没想到数组去记录就好(会比set的插入删除操作更快，可能当时脑抽了吧，临场的时候就是想到啥直接用了，没有啥时间去做更多的考虑)

第七题

对于任意一个大于等于2的数来说，开根号并向下取整肯定是优于（或等于）减半的，所以我们利用优先队列(堆)每次对最大数进行开根号操作（P次以后变成减半操作），然后弹出并把操作后得到的新数放回去就行了，也就是堆+贪心，但有大佬把出题人hack了

恕我太菜没想到这种数据的解决办法，而且赛场上这个题我压根就没写。。。(调暴搜花了1.5h给自己整累了，觉得反正后面更难懒得写了)

附代码（非本人手写）

#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int n,P,Q;
int a[100010];
 
int main()
{
    priority_queue<int> heap;
    scanf("%d%d%d",&n,&P,&Q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),heap.push(a[i]);
     
    while(P||Q)
    {
        auto x=heap.top();
        heap.pop();
         
        if(P&&Q)
        {
            int yl=sqrt(x);
            int y2=x/2;
            if(y2<=yl)
            {
                Q--;
                heap.push(y2);
            }
            else
            {
                P--;
                heap.push(yl);
            }
        }
        else if(P)
        {
            int yl=sqrt(x);
            P--;
            heap.push(yl);
        }
        else
        {
            int y2=x/2;
            Q--;
            heap.push(y2);
        }
    }
     
    ll res=0;
    while(!heap.empty())
    {
        int x=heap.top();
        heap.pop();
        res+=x;
    }
    printf("%lld\n",res);
    return 0;
}