[数据结构与算法] 2022蓝桥杯C++B组省赛题解

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2022蓝桥杯C++B组省赛题解 -> 正文阅读

[数据结构与算法]2022蓝桥杯C++B组省赛题解

大家可以去这个网站测试代码
有啥问题可以在下评论, 我就懒得写注解哪些啦(真是个懒人)

A：

//2 * 1 + 2 * 9 + 2 * 9 * 9 * 9

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int a[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int b[5];

int main(){
    
    int cnt = 0;
    
    for(int i = 1; i <= 12; ++ i)
        for(int j = 1; j <= a[i]; ++ j){
            b[0] = i / 10;
            b[1] = i % 10;
            b[2] = j / 10;
            b[3] = j % 10;
            
            for(int k = 0; k <= 1; ++ k)
                if(b[k] != 0 && b[k] - b[k + 1] == -1 && b[k + 2] - b[k + 1] == 1){
                    cnt ++;
                    break;
                }
            
        }
    
    cout << cnt;
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long LL;

// LL_Max 大于9e19

LL a, b, n;

int main(){
    
    cin >> a >> b >> n;
    
    LL m = a * 5 + b * 2;
    
    LL k = n / m;
    LL r = n % m;
    
    LL s[8] = {0, a, a, a, a, a, b, b};
    
    int i;
    
    for(i = 1; i <= 7 && r > 0; ++ i){
        r -= s[i];
    }
    
    cout << k * 7 + i - 1;
    
    return 0;
}

D：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long LL;

// 1 ~ n 考虑第i颗树 向右剪枝的时候 n - i + (n - i - 1) + 1 回到本点 向左剪枝的时候 i - 1 + (i - 1 - 1) + 1 回到本点 就两种情况 取最大值
//注意要是n - i || i - 1为0时 则不能考虑(n - i - 1)了, 因为不可能比存在中间点了

int n;

int main(){
    
    cin >> n;
    
    
    for(int i = 1; i <= n; ++ i){
        int x = max(n - i, i - 1);
        if(x > 0) x += x;
        else x ++;
        cout << x << endl;
    }
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;

int n, na, nb;
LL a[N], b[N];

int main(){
    
    cin >> n >> na;    
    
    for(int i = 1; i <= na; ++ i) cin >> a[i];
    
    cin >> nb;
    
    for(int j = 1; j <= nb; ++ j) cin >> b[j];
    
    LL res = 0;
    LL now = 1;
    for(int i = na, j = nb; i >= 1 || j >= 1; -- i, -- j){
        
        LL aa = 0, bb = 0;
        if(i >= 1) aa = a[i];
        if(j >= 1) bb = b[j];
        
        res = (res + ((aa - bb) % mod) * now % mod) % mod;
        now = now * max(max(aa + 1, bb + 1), 2ll) % mod;
        
    }
    
    cout << (res % mod + mod) % mod;
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 510;

int n, m, k;

int a[N][N];
int s[N];

int main(){
    
    cin >> n >> m >> k;
    
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            cin >> a[i][j], a[i][j] += a[i][j - 1];
    
    LL res = 0;
    for(int i = 1; i <= m; ++ i){
        for(int j = i; j <= m; ++ j){
            
            int cnt = 0;
            for(int p = 1; p <= n; ++ p)
            s[cnt ++] = a[p][j] - a[p][i - 1];
            
            int sum = 0;
            int p, q;
            for(q = 0, p = 0; p < cnt; ++ p){
                while(sum + s[p] > k){
                    res += p - q;
                    sum -= s[q++];
                }
                sum += s[p];
            }
            
            while(q < p){
                res += p - q;
                q ++;
            }
            
        }
        
    }
    
    cout  << res;
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int mod = 1e9 + 7, N = 1e7 + 10;
int n;
int f[N][4];
int main(){
    cin >> n;
    f[0][3] = 1;

        for(int i = 1; i <= n; ++ i){
            f[i][3] += ((f[i - 1][1] + f[i - 1][2]) % mod+ (f[i - 1][3] + f[i - 1][0]) % mod) % mod;
	        f[i][2] += (f[i - 1][0] + f[i - 1][1]) % mod;
	        f[i][1] += (f[i - 1][0] + f[i - 1][2]) % mod;
	        f[i][0] += f[i - 1][3];
        }

    cout << f[n][3];
    return 0;
}

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node{
    int x, y, r, s;
}tr[50010];

int n, m, cnt;
int ans;
bool st[50010];
unordered_map<long long, int> p;

long long calc(int x, int y){
    return 1LL * x * (1e9 + 1) + y;
}

inline void dfs(int i){
    st[i] = true;
    ans += tr[i].s;
    int r = tr[i].r;
    for(int x = tr[i].x - r; x <= tr[i].x + r; ++ x)
        for(int y = tr[i].y - r; y <= tr[i].y + r; ++ y){
            long long k = calc(x, y);
            if(x >= 0 && y <= 1e9 && y >= 0 && x <= 1e9 && p.find(k) != p.end() && !st[p[k]] && 1LL * (tr[i].x - x) * (tr[i].x - x) + 1LL * (tr[i].y - y) * (tr[i].y - y) <= r * r)
                dfs(p[k]);
        }
    
} 

int main(){
    
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; ++ i){
        int x, y, r;
        scanf("%d%d%d", &x, &y, &r);
        long long k = calc(x, y);
        if(p.find(k) == p.end()){
            p[k] = ++ cnt;
            tr[cnt].x = x;
            tr[cnt].y = y;
            tr[cnt].r = r;
        }
        int v = p[k];
        tr[v].s ++;
        tr[v].r = max(r, tr[v].r);
    }
    
    for(int i = 1; i <= m; ++ i){
        int x, y, r;
        scanf("%d%d%d", &x, &y, &r);
        tr[cnt + 1].x = x, tr[cnt + 1].y = y, tr[cnt + 1].r = r;
        dfs(cnt + 1);
    }
    
    printf("%d", ans);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long LL;
const int mod = 1e9 + 7, N = 105;
int n, m;

int f[N << 1][N][N];

// f[i][j][k]：共经过j处酒店, i - j处花店, 剩余酒为k斗的方案数, 转移方程: f[i][j][k] = k & 1 == 0 : f[i - 1][j - 1][k / 2] +  f[i - 1][j][k++];

int main(){
    
    cin >> n >> m;
    
    f[0][0][2] = 1;
    
    for(int i = 1; i <= n + m; ++ i)
        for(int j = 0; j <= min(i, n); ++ j)
            for(int k = 0; k <= m - (i - j); ++ k){
                if(!(k & 1) && j) f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k / 2]) % mod;
                if(i - 1 >= j) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % mod;
            }

    
    cout << f[n + m - 1][n][1];
    return 0;
}

J：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int l[N], r[N];
int n;
LL a[N];
priority_queue< pair<LL, int> > heap;
int ans;

int find(int f[], int x){
    if(x != f[x]) f[x] = find(f, f[x]);
    return f[x];
}

int main(){
    ios::sync_with_stdio(false);
    
    cin >> n;
    for(int i = 1; i <= n; ++ i){
        cin >> a[i];
        heap.push({a[i], i});
        l[i] = r[i] = i;
    }
    //int cnt = 0;
    while(1){
        LL x, y;
        
        //cout << heap.size() << " " << heap.top().first << " " << heap.top().second << endl;
        
        if(heap.top().first == 1) break;
        
        x = heap.top().first;
        y = heap.top().second;
        
        heap.pop();
        
        int q = find(l, y);
        
        if(q != y) continue;
        
        ++ ans;
        
        x = sqrt(x / 2 + 1 + 1e-9);
        
        if(y != 1){
            int k = find(l, y - 1);
            if(a[k] != x){
                a[y] = x;
                heap.push({a[y], y});
            }
            else{
                l[y] = y - 1;
                r[y - 1] = y;
            }
        }
        else heap.push({x, y}), a[y] = x;
        
        if(find(r, y) != n){
            int k = find(r, y) + 1;
            if(a[k] == x){
                l[k] = k - 1;
                r[k - 1] = k;
            }
        }
        
    }
    
    cout << ans;
    
    return 0;
}