第十四屆藍(lán)橋杯大賽軟件賽省賽 C/C++ 大學(xué) B 組

注意！?。。。。。。。?！這篇題解為賽時(shí)的個(gè)人做法，不代表是正確的，僅供參考。
更新：思路上應(yīng)該都對，很多題都有細(xì)節(jié)錯(cuò)誤，代碼不用看了,太久沒敲代碼了(- -)
更新2：代碼除了島嶼的都改好了，整數(shù)刪除常數(shù)有點(diǎn)大，可能會(huì)t，賽時(shí)的代碼一堆錯(cuò)誤，還是對自己的文章負(fù)責(zé)，省賽打的太放松了，應(yīng)該多自己造幾組樣例測得。最后兩題lca，板子有一行腦抽了寫錯(cuò)了居然沒發(fā)現(xiàn)，然后求lca我是前一題復(fù)制到后一題，兩題的樣例都能過，結(jié)果兩題都錯(cuò)了，把那一行代碼改完就都a了，藍(lán)橋杯給的樣例是在是太水了。。。。。自己還是太久沒敲代碼，變菜了。(T . T)

試題 A: 日期統(tǒng)計(jì)

dfs+剪枝即可，因?yàn)榍八奈灰欢ㄊ?023，五六位一定是1-12月，七八為也要滿足條件，所以實(shí)際上搜索的范圍比較少

最終答案: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的個(gè)數(shù),因?yàn)?個(gè)數(shù)比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: 冶煉金屬

數(shù)論分塊知識(shí)，用二分也可以

#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));//比賽時(shí)手快分子少加了個(gè)1，麻了(代碼已改過)
    }
    printf("%d %d",minn,maxx);
    return 0;
}

試題 D: 飛機(jī)降落

因?yàn)镹最多10，所以把所有飛機(jī)可能到達(dá)的順序都檢查一遍看看是否可行即可。復(fù)雜度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: 接龍數(shù)列

dp,dp[i]表示以i為結(jié)尾最長可以組成多長，那么答案就是n-max(dp[0-9])

復(fù)雜度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: 島嶼個(gè)數(shù)

首先dfs一次，把所有相連的島嶼都標(biāo)上號(hào)。

一個(gè)個(gè)判斷某一個(gè)島嶼是否被圍住，如何判斷，枚舉所有的島嶼作為墻，當(dāng)你從一個(gè)島嶼存在一個(gè)點(diǎn)，可以搜索走出n*m的棋盤就證明沒有被圍住，當(dāng)所有其他島嶼作為墻，你都可以走出地圖，那么這個(gè)島嶼就沒有被圍住。

復(fù)雜度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: 子串簡寫

對結(jié)尾字符出現(xiàn)次數(shù)做前綴和，枚舉a字符開頭的位置，假設(shè)s[i]是a字符，那么i+k-1以后的出現(xiàn)的b都可以作為答案。

復(fù)雜度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: 整數(shù)刪除

維護(hù)兩個(gè)set，一個(gè)set先對值再對位置大小排序，另一個(gè)則相反。然后模擬即可。

復(fù)雜度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: 景區(qū)導(dǎo)游

樹上前綴和+lca。先算出不刪除走完全稱所需要的時(shí)間假設(shè)為asum。如何算，sum[i]代表從根走到i節(jié)點(diǎn)需要花多少時(shí)間，那么從u到v(后文表示為dis(u,v))則需要花sum[u]+sum[v]-sum[lca(u,v)]*2這么多時(shí)間，如果刪去一個(gè)點(diǎn)i后，全程答案為 asum - dis(a[i],a[i+1]) - dis(a[i],a[i-1]) + dis(a[i-1],a[i+1]),刪掉開頭和結(jié)尾特判，入代碼所示。

復(fù)雜度: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所經(jīng)過的邊權(quán)值加1，最后看那一條邊的權(quán)值等于給出的無序?qū)Φ膫€(gè)數(shù)，輸出序號(hào)最大的那條邊即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-446742.html

#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;
}

到了這里，關(guān)于第十四屆藍(lán)橋杯大賽軟件賽省賽 C/C++ 大學(xué) B 組的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！