第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

注意！！！！！！！！！！这篇题解为赛时的个人做法，不代表是正确的，仅供参考。
更新：思路上应该都对，很多题都有细节错误，代码不用看了,太久没敲代码了(- -)
更新2：代码除了岛屿的都改好了，整数删除常数有点大，可能会t，赛时的代码一堆错误，还是对自己的文章负责，省赛打的太放松了，应该多自己造几组样例测得。最后两题lca，板子有一行脑抽了写错了居然没发现，然后求lca我是前一题复制到后一题，两题的样例都能过，结果两题都错了，把那一行代码改完就都a了，蓝桥杯给的样例是在是太水了。。。。。自己还是太久没敲代码，变菜了。(T . T)

试题 A: 日期统计

dfs+剪枝即可，因为前四位一定是2023，五六位一定是1-12月，七八为也要满足条件，所以实际上搜索的范围比较少

最终答案:235

#include<bits/stdc++.h>using namespace std;const int N = 2e6+9;typedef long long ll;int a[N];int mon[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};vector<int> now;map<int,int> mp;int ans = 0;void dfs(int len,int dep){    if(len == 8){        int sum = 0;        int m = now[4]*10 + now[5];        int d = now[6]*10 + now[7];        if(m < 1 || m > 12) return ;        if(d < 1 || d > mon[m]) return ;        for(int i = 0;i < 8;i++){            sum *= 10;            sum += now[i];        }        if(!mp[sum]){            ans++;            mp[sum] = 1;        }        return ;    }    for(int i = dep;i <= 100;i++){        if(len == 0){            if(a[i] == 2){                now.push_back(a[i]);                dfs(len+1,i+1);                now.pop_back();            }        }else if(len == 1){            if(a[i] == 0){                now.push_back(a[i]);                dfs(len+1,i+1);                now.pop_back();            }        }else if(len == 2){            if(a[i] == 2){                now.push_back(a[i]);                dfs(len+1,i+1);                now.pop_back();            }        }else if(len == 3){            if(a[i] == 3){                now.push_back(a[i]);                dfs(len+1,i+1);                now.pop_back();            }        }else{            now.push_back(a[i]);            dfs(len+1,i+1);            now.pop_back();        }    }}void sol(){    for(int i = 1;i <= 100;i++){        scanf("%d",&a[i]);    }    dfs(0,1);    printf("%d",ans);}int main(){        sol();    return 0;}

试题 B: 01 串的熵

枚举0的个数,因为0个数比1小，所以遍历到23333333/2即可

最终答案：11027421

#include<bits/stdc++.h>using namespace std;const int N = 2e6+9;typedef long long ll;void sol(){    int n = 23333333;    for(int i = 0;i <= n/2;i++){        double ans = -1.0*i*i/n*log2(1.0*i/n)-1.0*(n-i)*(n-i)/n*log2(1.0*(n-i)/n);        if(abs(ans - 11625907.5798) <= 0.0001){            printf("%d",i);        }    }}int main(){        sol();    return 0;}

试题 C: 冶炼金属

数论分块知识，用二分也可以

#include<bits/stdc++.h>using namespace std;const int N = 2e6+9;typedef long long ll;int main(){    int n;    scanf("%d",&n);    int maxx = 1000000000,minn = 0;    for(int i = 1;i <= n;i++){        int a,b;        scanf("%d %d",&a,&b);        maxx = min(maxx,a/b);        minn = max(minn,(a+b+1)/(b+1));//比赛时手快分子少加了个1，麻了(代码已改过)    }    printf("%d %d",minn,maxx);    return 0;}

试题 D: 飞机降落

因为N最多10，所以把所有飞机可能到达的顺序都检查一遍看看是否可行即可。复杂度O(T10!)

#include<bits/stdc++.h>using namespace std;const int N = 2e6+9;typedef long long ll;struct node{    int t,d,l;}p[N];int a[20];void sol(){    int n;    scanf("%d",&n);    for(int i = 1;i <= n;i++){        scanf("%d %d %d",&p[i].t,&p[i].d,&p[i].l);        a[i] = i;    }        do{        int now = 0;        int flag = 1;        for(int i = 1;i <= n;i++){            int t = p[a[i]].t,d = p[a[i]].d,l = p[a[i]].l;            if(now > t + d){                flag = 0;                break;            }else{                if(t > now) now = t + l;                else now = now + l;            }        }        if(flag){            printf("YES\n");            return;        }    }while(next_permutation(a+1,a+1+n));    printf("NO\n");}int main(){    int t;    scanf("%d",&t);    while(t--){        sol();    }    return 0;}

试题 E: 接龙数列

dp,dp[i]表示以i为结尾最长可以组成多长，那么答案就是n-max(dp[0-9])

复杂度O(n)

#include<bits/stdc++.h>using namespace std;const int N = 2e6+9;typedef long long ll;struct node{    int t,w;}p[N];int dp[20];void sol(){    int n;    scanf("%d",&n);    for(int i = 1;i <= n;i++){        int x;        scanf("%d",&x);        p[i].w = x % 10;        while(x >= 10){            x/=10;        }        p[i].t = x;    }    // for(int i = 1;i <= n;i++){    //     printf("%d %d\n",p[i].t,p[i].w);    // }    for(int i = 1;i <= n;i++){        dp[p[i].w] = max(dp[p[i].w],dp[p[i].t] + 1);    }    int ans = 1000000000;    for(int i = 0;i <= 9;i++){        ans = min(ans,n-dp[i]);    }    printf("%d",ans);}int main(){        sol();    return 0;}

试题 F: 岛屿个数

首先dfs一次，把所有相连的岛屿都标上号。

一个个判断某一个岛屿是否被围住，如何判断，枚举所有的岛屿作为墙，当你从一个岛屿存在一个点，可以搜索走出n*m的棋盘就证明没有被围住，当所有其他岛屿作为墙，你都可以走出地图，那么这个岛屿就没有被围住。

复杂度O(n^4)

#include<bits/stdc++.h>using namespace std;const int N = 2e3+9;typedef long long ll;int a[59][59];int vis[59][59];int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};int fobid = 0;int n,m;int ans[N];int nc = 0;void dfs(int x,int y,int co){    vis[x][y] = co;    for(int i = 0;i <= 3;i++){        int xx = x + dx[i];        int yy = y + dy[i];        if(xx < 1 || xx > n || yy < 1 || yy > m) continue;        if(vis[xx][yy]||a[xx][yy] == 0){            continue;        }        dfs(xx,yy,co);    }}int v[59][59];void dfs2(int x,int y,int co){    v[x][y] = 1;    for(int i = 0;i <= 3;i++){        int xx = x + dx[i];        int yy = y + dy[i];        if(xx < 1 || xx > n || yy < 1 || yy > m){            ans[co] = 1;            continue;        }         if(v[xx][yy] || vis[xx][yy] == fobid){            continue;        }        dfs2(xx,yy,co);    }}void sol(){    memset(vis,0,sizeof(vis));    memset(ans,0,sizeof(ans));    nc = 0;    scanf("%d %d",&n,&m);    for(int i = 1;i <= n;i++){        for(int j = 1;j <= m;j++){            scanf("%1d",&a[i][j]);        }    }    for(int i = 1;i <= n;i++){        for(int j = 1;j <= m;j++){            if(a[i][j]){                if(!vis[i][j]){                    dfs(i,j,++nc);                }            }        }    }    for(fobid = 1;fobid <= nc;fobid++){        for(int i = 1;i <= n;i++){            for(int j = 1;j <= m;j++){                if(vis[i][j] && fobid != vis[i][j]){                    if(ans[vis[i][j]]) continue;                    memset(v,0,sizeof(v));                    dfs2(i,j,vis[i][j]);                }            }        }    }        int num = 0;    for(int i = 1;i <= nc;i++){        num += ans[i];    }    printf("%d\n",num);}int main(){    int t;    scanf("%d",&t);    while(t--)        sol();    return 0;}

试题 G: 子串简写

对结尾字符出现次数做前缀和，枚举a字符开头的位置，假设s[i]是a字符，那么i+k-1以后的出现的b都可以作为答案。

复杂度O(n)

#include<bits/stdc++.h>using namespace std;const int N = 2e6+9;typedef long long ll;char s[N];char a,b;ll sum[N];void sol(){    int k,n;    scanf("%d",&k);    scanf("%s",s+1);    n = strlen(s+1);    scanf(" %c",&a);    scanf(" %c",&b);    for(int i = 1;i <= n;i++){        if(s[i] == b) sum[i] = sum[i-1]+1;        else sum[i] = sum[i-1];    }    ll ans = 0;    for(int i = 1;i <= n;i++){        if(s[i] == a && i + k - 2 <= n){            ans += (sum[n] - sum[i+k-2]);        }    }    printf("%lld",ans);}int main(){        sol();    return 0;}

试题 H: 整数删除

维护两个set，一个set先对值再对位置大小排序，另一个则相反。然后模拟即可。

复杂度O(nlogn+klogn)

#include<bits/stdc++.h>using namespace std;const int N = 2e6+9;typedef long long ll;struct nodevp{    int pos;    ll val;    bool operator < (const nodevp &p) const{        if(val == p.val) return pos < p.pos;        else return val < p.val;    }    bool operator == (const nodevp &p) const{        return pos == p.pos && val == p.val;    }};struct nodepv{    int pos;    ll val;    bool operator < (const nodepv &p) const{        if(pos == p.pos) return val < p.val;        else return pos < p.pos;    }    bool operator == (const nodepv &p) const{        return pos == p.pos && val == p.val;    }};ll a[N];set<nodevp> svp;set<nodepv> spv;int n,k;void changepv(nodepv a,nodepv b){    spv.erase(a);    spv.insert(b);}void changevp(nodevp a,nodevp b){    svp.erase(a);    svp.insert(b);}void sol(){    scanf("%d %d",&n,&k);    for(int i = 1;i <= n;i++){        scanf("%d",&a[i]);        nodevp v;        v.val = a[i];        v.pos = i;        svp.insert(v);        nodepv p;        p.val = a[i];        p.pos = i;        spv.insert(p);    }    for(int i = 1;i <= k;i++){        nodevp v = *svp.begin();        // svp.erase(v);        ll add = v.val;        nodepv p;        p.val = v.val;        p.pos = v.pos;        auto apv = spv.find(p);        if(apv != spv.begin()){            apv--;            nodepv temp,nex;            temp.pos = apv->pos;            temp.val = apv->val;            nex.pos = temp.pos;            nex.val = temp.val + add;            nodevp temp2,nex2;            temp2.pos = apv->pos;            temp2.val = apv->val;            nex2.pos = temp2.pos;            nex2.val = temp2.val + add;            changepv(temp,nex);            changevp(temp2,nex2);            // apv++;        }        apv = spv.find(p);        apv++;        if(apv == spv.end()){            spv.erase(p);            svp.erase(v);            continue;        }        nodepv temp,nex;        temp.pos = apv->pos;        temp.val = apv->val;        nex.pos = temp.pos;        nex.val = temp.val + add;        nodevp temp2,nex2;        temp2.pos = apv->pos;        temp2.val = apv->val;        nex2.pos = temp2.pos;        nex2.val = temp2.val + add;        changepv(temp,nex);        changevp(temp2,nex2);        spv.erase(p);        svp.erase(v);    }    while(spv.size()){        nodepv p = *spv.begin();        printf("%lld ",p.val);        spv.erase(p);    }}int main(){        sol();    return 0;}// 5 3// 4 1 2 8 7// 5 4// 1 4 2 8 7

试题 I: 景区导游

树上前缀和+lca。先算出不删除走完全称所需要的时间假设为asum。如何算，sum[i]代表从根走到i节点需要花多少时间，那么从u到v(后文表示为dis(u,v))则需要花sum[u]+sum[v]-sum[lca(u,v)]*2这么多时间，如果删去一个点i后，全程答案为 asum - dis(a[i],a[i+1]) - dis(a[i],a[i-1]) + dis(a[i-1],a[i+1]),删掉开头和结尾特判，入代码所示。

复杂度:O(nlogn)

#include<bits/stdc++.h>using namespace std;const int N = 2e5+9;typedef long long ll;int n,k;int f[N][29];int dep[N];int a[N];ll sum[N];ll ans[N];struct edge{    ll dis;    int to;};vector<edge> g[N];int lca(int u,int v){    if(dep[u] < dep[v]) swap(u,v);    for(int i = 20;i >= 0;i--){        if(dep[f[u][i]] >= dep[v]) u = f[u][i];    }    if(u == v) return u;    for(int i = 20;i >= 0;i--){        if(f[u][i] != f[v][i]){            u = f[u][i];            v = f[v][i];        }    }    return f[u][0];}ll dis(int u,int v){    return (sum[u] + sum[v] - sum[lca(u,v)]*2);}void dfs(int now,int fa){    // sum[now] = sum[now] + sum[fa];    f[now][0] = fa;    dep[now] = dep[fa] + 1;    for(int i = 1;i <= 20;i++){        if(f[now][i-1]) f[now][i] = f[f[now][i-1]][i-1];        else break;    }    for(auto j : g[now]){        if(j.to == fa) continue;        sum[j.to] += sum[now] + j.dis;        dfs(j.to,now);    }}void sol(){    scanf("%d %d",&n,&k);    for(int i = 1;i <= n-1;i++){        int u,v;        ll dis;        scanf("%d %d %lld",&u,&v,&dis);        edge p;        p.dis = dis;p.to = v;        g[u].push_back(p);        p.to = u;        g[v].push_back(p);    }    dfs(1,0);    ll asum = 0;    for(int i = 1;i <= k;i++){        scanf("%d",&a[i]);    }    for(int i = 2;i <= k;i++){        asum += (sum[a[i-1]] + sum[a[i]] - sum[lca(a[i-1],a[i])]*2);    }    for(int i = 1;i <= k;i++){        if(i == 1){            ans[i] = asum - dis(a[i],a[i+1]);        }else if(i == k){            ans[i] = asum - dis(a[i],a[i-1]);        }else{            ans[i] = asum - dis(a[i],a[i+1]) - dis(a[i],a[i-1]) + dis(a[i-1],a[i+1]);        }    }    for(int i = 1;i <= k;i++){        printf("%lld ",ans[i]);    }}int main(){        sol();    return 0;}

试题 J: 砍树

树上差分+lca。如果u到v想要断开，那么u到v路径上的任何一条边断开都可以，所以把u到v所经过的边权值加1，最后看那一条边的权值等于给出的无序对的个数，输出序号最大的那条边即可。

#include<bits/stdc++.h>using namespace std;const int N = 2e5+9;typedef long long ll;int n,m;int f[N][29];int dep[N];ll sum[N];int ans = -1;int fnum[N];struct edge{    ll dis;    int to;};vector<edge> g[N];int lca(int u,int v){    if(dep[u] < dep[v]) swap(u,v);    for(int i = 20;i >= 0;i--){        if(dep[f[u][i]] >= dep[v]) u = f[u][i];    }    if(u == v) return u;    for(int i = 20;i >= 0;i--){        if(f[u][i] != f[v][i]){            u = f[u][i];            v = f[v][i];        }    }    return f[u][0];}void dfs(int now,int fa){    // sum[now] = sum[now] + sum[fa];    f[now][0] = fa;    dep[now] = dep[fa] + 1;    for(int i = 1;i <= 20;i++){        if(f[now][i-1]) f[now][i] = f[f[now][i-1]][i-1];        else break;    }    for(auto j : g[now]){        if(j.to == fa) continue;        fnum[j.to] = j.dis;        dfs(j.to,now);    }}void dfs2(int now,int fa){    for(auto j : g[now]){        if(j.to == fa) continue;        dfs2(j.to,now);        sum[now] += sum[j.to];    }    if(sum[now] == m){        ans = max(ans,fnum[now]);    }}void sol(){    scanf("%d %d",&n,&m);    for(int i = 1;i <= n-1;i++){        int u,v;        scanf("%d %d",&u,&v);        edge p;        p.dis = i;p.to = v;        g[u].push_back(p);        p.to = u;        g[v].push_back(p);    }    dfs(1,0);    for(int i = 1;i <= m;i++){        int u,v;        scanf("%d %d",&u,&v);        sum[u]++;        sum[v]++;        sum[lca(u,v)]-=2;    }    dfs2(1,0);    printf("%d",ans);}int main(){        sol();    return 0;}