第十届蓝桥杯B组C++赛题复盘总结

我会带着你远行 2022-02-26 12:10 198阅读 0赞

其实今年的赛题算简单的，奈何我编程基础实在太差，端正态度好好补补吧，未来算法的路还太长。  
1 组队 这题手算就ok  
2 年号字串 找规律手算  
3 数列求值 很明显看出来是斐波那契数列变形，也知道精度一定超过long long 但是就是每想到怎么保存那么大的数字，赛后看到别的大神的题解才捶胸顿足：将每次得出的答案mod10000，每次只保存后四位即可（每次mod10000和最后全部加起来mod10000答案是一样的）

#inclue<iostream>
    using namespace std;
    typedef long long LL;
    const int mod=1e4;
    
    LL dp[2019325];
    
    int main(){
    	dp[1]=dp[2]=dp[3]=1;
    	for(int i=4;i<=20190324;i++)
    	{
    	dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%mod;
    	}
    	cout<<dp[20190324]<<endl;
    	return 0;
    }

4 数的分解 暴力枚举 当时代码写出来了但是运行好几十秒都没出结果，，哭死我。

#include <bits/stdc++.h>
    using namespace std;
    
    bool check(int x, int y, int z) {	//判断三个正整数中是否含2或4 
    	int res = 0;
    	while (x) {
    		res = x % 10;
    		if (res == 2 || res == 4) return false;
    		x /= 10;
    	} 
    	while (y) {
    		res = y % 10;
    		if (res == 2 || res == 4) return false;
    		y /= 10;
    	}
    	while (z) {
    		res = z % 10;
    		if (res == 2 || res == 4) return false;
    		z /= 10;
    	}
    	return true;
    }
    
    int main() {
    	int ans = 0;
    	for (int a = 1; a < 2019; a++) {
    		for (int b = 1; b < 2019; b++) {
    			if (b == a) continue;		//a,b,c三个数不相同
    			for (int c = 1; c < 2019; c++) {
    				if (b == c || a == c) continue;
    				if (a + b + c == 2019 && check(a, b, c)) ans++;
    			} 
    		}
    	}
    	cout << ans / 6 << endl;
    	return 0;
    }

5 迷宫 这题确实不会做 贴一下大神的代码

#include <bits/stdc++.h>
    using namespace std;
    
    char mp[30][50];	//地图
    bool vis[30][50];	//标记该点是否走过
    int dir[4][2] = {
       {1,0},{0,-1},{0,1},{-1,0}};	//方向数组按照下，左，右，上的顺序走
    char dirc[4] = {'D','L','R','U'}; 
    int n,m;  	//迷宫的行列
    
    struct node{
    	int x;	//横坐标 
    	int y;	//纵坐标 
    	int step;	//步数 
    	string str;	//路径 
    	node(int xx, int yy, int ss, string s) {	//构造函数 
    		x = xx;
    		y = yy;
    		step = ss;
    		str = s;
    	}
    }; 
    
    queue<node> q; //创建队列
    
    bool check(int x, int y) {	//判断是否越界以及是否是墙以及是否访问过了 
    	if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '1') {
    		return false;
    	}
    	return true;
    }
    
    void bfs(int x, int y) {
    	q.push(node(x, y, 0, ""));
    	vis[x][y] = true;
    	while (!q.empty()) {
    		node now = q.front();
    		if (now.x == n - 1 && now.y == m - 1) {	//到达终点了 
    			cout << now.str << endl;
    			cout << now.step << endl;
    			break;
    		}
    		q.pop();
    		for (int i = 0; i < 4; i++) {
    			int nx = now.x + dir[i][0];
    			int ny = now.y + dir[i][1];
    			if (check(nx, ny)) {
    				q.push(node(nx, ny, now.step + 1, now.str + dirc[i]));
    				vis[nx][ny] = true;
    			}
    		}
    	}
    } 
    
    int main() {
    	scanf("%d%d", &n, &m);
    	for (int i = 0; i < n; i++) {
    		scanf("%s", mp[i]);
    	}
    	bfs(0, 0);
    	return 0;
    }

6 特别数的和 这题比较简单也做出来了

#include <bits/stdc++.h>
    using namespace std;
    
    bool check(int x) {
    	int res = 0;
    	while (x) {
    		res = x % 10;
    		if (res == 0 || res == 1 || res == 2 || res == 9) return true;
    		x /= 10;
    	}
    	return false;
    }
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	int ans = 0;
    	for (int i = 1; i <= n; i++) {
    		if (check(i)) {
    			ans += i;
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }

7 完全二叉树的值 这题样例跑对了 但是可能其他的测试点没有过 因为直接把题目中“权值同为最大就输出最小深度的”这个忽略了，，

#include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    int main()
    {
        int n;
        cin >> n;
        LL maxv = INT_MIN;	//INT_MIN是在limits.h头文件中,代表INT型最小值 ,这里记录权值和最大 
    	LL maxv_d = 0;	//最大的权值和的层数 
        for (int i = 0, length = 1, depth = 1; i < n; depth++, length *= 2)
        {
            LL sum = 0;	//每一层的和 
            for (int j = 0; j < length && i < n; j++, i++ )
            {
                int x;
                cin >> x;
                sum += x;
            }
    
            if (sum > maxv)
            {
                maxv = sum;
                maxv_d = depth;
            }
        }
    
        cout << maxv_d << endl;
        return 0;
    }

8 等差数列 这题也跑对了样例貌似 但是可能还是其他某个地方不对。

#include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int maxn = 1e5 + 5;
    
    LL a[maxn];
    
    int gcd(int a, int b) {
    	return b == 0 ? a : gcd(b, a % b);
    }
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i++) {
    		scanf("%d", &a[i]);
    	}
    	sort(a + 1, a + n + 1);
    	for (int i = 2; i <= n; i++) {
    		a[i] -= a[1];
    	}
    	int d = a[2];
    	for (int i = 3; i <= n; i++) {
    		d = gcd(d, a[i]);
    	}
    	if (d == 0) {
    		cout << n << endl;
    	} else {
    		cout << a[n] / d + 1 << endl;
    	}
    	return 0;
    }

9 后缀表达式 这个做出来了

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int maxn = 200010;
    
    int n, m;
    int a[maxn];
    
    int main()
    {
        scanf("%d%d", &n, &m);
        int k = n + m + 1;
        LL sum = 0;
        for (int i = 0; i < k; i++)
        {
            scanf("%d", &a[i]);
            sum += a[i];	//求这些数的和 
        }
        sort(a, a + k);
    
        if (a[0] >= 0)	//第一个数大于0，说明没有负数，因为之前加过一次a[0]，然后我们本来就需要减掉a[0]，所以减掉2*a[0] 
        {
            if (m) sum -= 2 * a[0];
        }
        else		//如果是负数的那么我们需要加上，因为之前是负数，加上去也就相当于减掉,所以-=2*a[i](a[i]<0) 
        {
            for (int i = 0; i < k && a[i] < 0 && m > 0; i++ )
            {
                sum -= a[i] * 2;
                m-- ;
            }
        }
        cout << sum << endl;
        return 0;
    }

10 灵能传输 我知道题目不难，但是题目真心太长了我考场上就放弃了

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <limits.h>
    
    using namespace std;
    
    typedef long long LL;
    const int N = 300010;
    
    int n;
    LL sum[N], a[N], s0, sn;
    bool st[N];
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T -- )
        {
            scanf("%d", &n);
            for (int i = 1; i <= n; i ++ )
            {
                scanf("%lld", &sum[i]);
                sum[i] += sum[i - 1];
            }
    
            s0 = sum[0], sn = sum[n];
            if (s0 > sn) swap(s0, sn);
    
            sort(sum, sum + n + 1);
    
            for (int i = 0; i <= n; i ++ )
                if (s0 == sum[i])
                {
                    s0 = i;
                    break;
                }
            for (int i = n; i >= 0; i -- )
                if (sn == sum[i])
                {
                    sn = i;
                    break;
                }
    
            memset(st, 0, sizeof st);
            int l = 0, r = n;
            for (int i = s0; i >= 0; i -= 2)
            {
                a[l ++ ] = sum[i];
                st[i] = true;
            }
            for (int i = sn; i <= n; i += 2)
            {
                a[r -- ] = sum[i];
                st[i] = true;
            }
            for (int i = 0; i <= n; i ++ )
                if (!st[i])
                {
                    a[l ++ ] = sum[i];
                }
    
            LL res = 0;
            for (int i = 1; i <= n; i ++ ) res = max(res, abs(a[i] - a[i - 1]));
            cout << res << endl;
        }
        return 0;
    }

（以上代码都来自于 [https://blog.csdn.net/lytwy123/article/details/88826385）][https_blog.csdn.net_lytwy123_article_details_88826385]  
总结：题目不难，看上去都会，下手都出错——基础不扎实。  
其实是有点不甘心的，意识到差距只是第一步，最重要的还是踏踏实实地去学和补，立一个flag：明年2020我会再参加一次并进入国赛，嗯。

[https_blog.csdn.net_lytwy123_article_details_88826385]: https://blog.csdn.net/lytwy123/article/details/88826385%EF%BC%89