devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组_试题来源:第十四届蓝桥杯大赛软件赛决赛 cb-5

作者：笔触狂放9 | 2024-04-17 07:13:39

赞

踩

试题来源:第十四届蓝桥杯大赛软件赛决赛 cb-5

目录

试题 A: 日期统计 .本题总分：5 分

试题 B: 01 串的熵.本题总分：5 分

试题 C: 冶炼金属.本题总分：10 分

试题 D: 飞机降落.本题总分：10 分

试题 E: 接龙数列 .本题总分：15 分

试题 F: 岛屿个数 .本题总分：15 分

试题 G: 子串简写 .本题总分：20 分

试题 H: 整数删除.本题总分：20 分

试题 I: 景区导游 .本题总分：25 分

试题 J: 砍树 .本题总分：25 分

试题 A: 日期统计 .本题总分：5 分

 相同的日期你只需要统计一次即可，直接dfs剪枝跑就可以了 我的答案235

试题 B: 01 串的熵.本题总分：5 分

二分，l=1,r=23333333>>1 ,我的答案11027421

试题 C: 冶炼金属.本题总分：10 分

对于最大值，可以根据整除分块定理2知道是a/b,然后取个min就是最大值，对于最小值，二分求，复杂度O（nlogn） 

然后其实知道r=a/b,那么也不难推出l是前一个块的r+1，也就是l=a/(b+1)+1 复杂度O(N)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define x first
  6. #define y second
  7. #define pd push_back
  8. const int maxn=1e4+10;
  9.  
  10.  
  11. int n;
  12. ll a[maxn],b[maxn];
  13.  
  14. void solve()
  15. {
  16.     cin>>n;
  17.     ll ma=-1,mi=-1;
  18.     for(int i=1;i<=n;i++)
  19.     {
  20.         cin>>a[i]>>b[i];
  21.         ll now=a[i]/b[i];
  22.         if(ma==-1||ma>now)
  23.         {
  24.             ma=now;
  25.         }
  26.         mi=max(mi,(a[i]/(b[i]+1))+1);
  27.     }
  28.     cout<<mi<<" "<<ma;
  29. }
  30. int main()
  31. {
  32.     ios::sync_with_stdio(0);
  33.     cin.tie(0);
  34.     cout.tie(0);
  35.     int tn=1;
  36.     //cin>>tn;
  37.     while(tn--)
  38.     {
  39.         solve();
  40.     }
  41.     return 0;
  42. }

试题 D: 飞机降落.本题总分：10 分

贪心寄了，还是全排列暴力~~~~~

还是dfs剪枝暴力吧，t<=10,n<=10

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define x first
  6. #define y second
  7. #define pd push_back
  8. const int maxn=1e2+10;
  9.  
  10. struct node
  11. {
  12.     int t,d,l;
  13. } ;
  14. int n;
  15. node a[maxn];
  16. int f[maxn];
  17. int flag;
  18. void dfs(int len,int last)
  19. {
  20.     if(len==n)
  21.     {
  22.         flag=1;
  23.         return;
  24.     }
  25.     for(int i=1;i<=n&&!flag;i++)
  26.     {
  27.         if(f[i])continue;
  28.         auto [t,d,l]=a[i];
  29.         if(last<=t+d)
  30.         {
  31.             f[i]=1;
  32.             dfs(len+1,max(last+l,t+l));
  33.             f[i]=0;
  34.         }
  35.     }
  36. }
  37. void solve()
  38. {
  39.     cin>>n;
  40.     flag=0;
  41.     for(int i=1;i<=n;i++)
  42.     {
  43.         cin>>a[i].t>>a[i].d>>a[i].l;
  44.         f[i]=0;
  45.     }
  46.     dfs(0,-1);
  47.     if(flag)cout<<"YES"<<endl;
  48.     else cout<<"NO"<<endl;
  49. }
  50. int main()
  51. {
  52.     ios::sync_with_stdio(0);
  53.     cin.tie(0);
  54.     cout.tie(0);
  55.     int tn=1;
  56.     cin>>tn;
  57.     while(tn--)
  58.     {
  59.         solve();
  60.     }
  61.     return 0;
  62. }

试题 E: 接龙数列 .本题总分：15 分

考虑dp, dp[i],表示以i结尾的子序列最大长度，当前数字开头为j结尾为i，那么dp[i]=max(dp[i],dp[j]+1);,最后n-最长子序列就可以了，复杂度O(N)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define x first
  6. #define y second
  7. #define pd push_back
  8. const int maxn=1e5+10;
  9.  
  10.  
  11. int n;
  12. int dp[10];
  13. /*
  14. 5
  15. 11 121 22 12 2023
  16. 1
  17. */
  18. void solve()
  19. {
  20.     cin>>n;
  21.     for(int i=1,j;i<=n;i++)
  22.     {
  23.         cin>>j;
  24.         int f=j,d=j%10;
  25.         while(f>=10)f/=10;
  26.         dp[d]=max(dp[d],dp[f]+1);
  27.     }
  28.     int ma=1;
  29.     for(int i=0;i<10;i++)
  30.     {
  31.         ma=max(ma,dp[i]);
  32.         //cout<<dp[i]<<endl;
  33.     }
  34.     cout<<n-ma<<endl;
  35. }
  36. int main()
  37. {
  38.     ios::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cout.tie(0);
  41.     int tn=1;
  42.     //cin>>tn;
  43.     while(tn--)
  44.     {
  45.         solve();
  46.     }
  47.     return 0;
  48. }

试题 F: 岛屿个数 .本题总分：15 分

 先从最外海水跑图，记录外部海水数量，岛的4周海水得有1个方向等于外部海水.否则就是环岛的子岛屿；

跑海水从8个方向染色；

然后跑周围是外部海水的岛屿，四个方向染++cnt，最后输出cnt就是答案

0(N*N)

  1. #include <bits/stdc++.h>
  2. #define int int64_t
  3. #define endl '\n'
  4. using namespace std;
  5. const int MAX = 55;
  6. const int INF = 0x3f3f3f3f3f3f3f3fll;
  7. const int MOD = 1e9 + 7;
  8.  
  9. char map_[MAX][MAX];              // 地图
  10. bool track[MAX][MAX] = {false};   // 访问标记
  11. bool outsea[MAX][MAX] = {false};  // 外海标记
  12. struct XY {
  13.     int x, y;
  14. } nxt[] = {
  15.     {1, 0},
  16.     {-1, 0},
  17.     {0, 1},
  18.     {0, -1},
  19.     {1, 1},
  20.     {-1, 1},
  21.     {1, -1},
  22.     {-1, -1},
  23. };
  24.  
  25. void solve() {
  26.     int n, m;
  27.     cin >> n >> m;
  28.     for (int i = 0; i < n; i++) {
  29.         cin >> map_[i];
  30.     }
  31.     for (int i = 0; i < n; i++) {
  32.         for (int j = 0; j < m; j++) {
  33.             track[i][j] = false;
  34.             outsea[i][j] = false;
  35.         }
  36.     }
  37.     // 预处理外海
  38.     for (int i = 0; i < n; i++) {
  39.         for (int j = 0; j < m; j++) {
  40.             if (map_[i][j] == '1' or track[i][j]) continue;
  41.             bool yep = false;
  42.             queue<XY> que, arr;
  43.             track[i][j] = true;
  44.             que.push({i, j});
  45.             arr.push({i, j});  // 记录搜索到的所有海域
  46.             while (not que.empty()) {
  47.                 XY pos = que.front();
  48.                 que.pop();
  49.                 // 注意：海域搜索可以往八个方向走，陆地搜索只能朝四个方向
  50.                 for (int i = 0; i < 8; i++) {
  51.                     XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};
  52.                     if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {
  53.                         if (map_[nw.x][nw.y] == '0' and track[nw.x][nw.y] == false) {
  54.                             track[nw.x][nw.y] = true;
  55.                             que.push(nw);
  56.                             arr.push(nw);
  57.                         }
  58.                     } else {
  59.                         yep = true;  // 如果有一次搜索到地图外，标记此次搜索的所有区域为外海
  60.                     }
  61.                 }
  62.             }
  63.             if (yep) {
  64.                 while (not arr.empty()) {
  65.                     XY pos = arr.front();
  66.                     arr.pop();
  67.                     outsea[pos.x][pos.y] = true;  // 标记搜索到的海域为外海
  68.                 }
  69.             }
  70.         }
  71.     }
  72.  
  73.     // 别忘了清空访问标记
  74.     for (int i = 0; i < n; i++) {
  75.         for (int j = 0; j < m; j++) {
  76.             track[i][j] = false;
  77.         }
  78.     }
  79.     // 处理岛屿
  80.     int cnt = 0;
  81.     for (int i = 0; i < n; i++) {
  82.         for (int j = 0; j < m; j++) {
  83.             if (map_[i][j] == '0' or track[i][j]) continue;
  84.             bool yep = false;
  85.             queue<XY> que;
  86.             track[i][j] = true;
  87.             que.push({i, j});
  88.             while (not que.empty()) {
  89.                 XY pos = que.front();
  90.                 que.pop();
  91.                 for (int i = 0; i < 4; i++) {
  92.                     XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};
  93.                     if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {
  94.                         if (map_[nw.x][nw.y] == '1') {
  95.                             if (track[nw.x][nw.y] == false) {
  96.                                 track[nw.x][nw.y] = true;
  97.                                 que.push(nw);
  98.                             }
  99.                         } else {
  100.                             if (outsea[nw.x][nw.y]) {
  101.                                 yep = true;  // 搜索到外海为外岛
  102.                             }
  103.                         }
  104.                     } else {
  105.                         yep = true;  // 搜索到边界外为外岛
  106.                     }
  107.                 }
  108.             }
  109.             if (yep) {
  110.                 cnt++;  // 外岛计数
  111.             }
  112.         }
  113.     }
  114.     cout << cnt << endl;
  115. }
  116.  
  117. int32_t main() {
  118.     cin.tie(0);
  119.     cout.tie(0);
  120.     ios::sync_with_stdio(0);
  121.  
  122.     int t;
  123.     cin >> t;
  124.     while (t--)
  125.         solve();
  126.  
  127.     return 0;
  128. }

试题 G: 子串简写 .本题总分：20 分

把c1的位置存起来，对于每个c2位置二分找最小符合的位置，ans加上这个位置下标就可以了

也可以双指针暴力

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define x first
  6. #define y second
  7. #define pd push_back
  8. #define pii pair<int,int>
  9. const int maxn=5e5+10;
  10. int n,k;
  11. char s[maxn],a,b;
  12. /*
  13. 4
  14. abababdb a b
  15. 4
  16. ba a b
  17. */
  18. void solve()
  19. {
  20.     cin>>k;
  21.     cin>>s+1;
  22.     cin>>a>>b;
  23.     n=strlen(s+1);
  24.     vector<int>va,vb;
  25.     for(int i=1;i<=n;i++)
  26.     {
  27.         if(s[i]==a)
  28.         {
  29.             va.pd(i);
  30.         }
  31.         if(s[i]==b)
  32.         {
  33.             vb.pd(i);
  34.         }
  35.     }
  36.     va.pd(n+1);
  37.     vb.pd(n+1);
  38.     ll ans=0;
  39.     for(int i=0;i<vb.size()-1;i++)
  40.     {
  41.         int r=lower_bound(va.begin(),va.end(),vb[i]-k+1)-va.begin();
  42.         if(va[r]>vb[i]-k+1)
  43.         {
  44.             r--;
  45.         }
  46.         ans+=r+1;
  47.         //cout<<r+1<<" "<<va[r]<<" "<<vb[i]<<" "<<ans<<endl;
  48.     }
  49.     cout<<ans<<endl;
  50.  
  51. }
  52.  
  53. int main()
  54. {
  55.     ios::sync_with_stdio(0);
  56.     cin.tie(0);
  57.     cout.tie(0);
  58.     int tn=1;
  59.     //cin>>tn;
  60.     while(tn--)
  61.     {
  62.         solve();
  63.     }
  64.     return 0;
  65. }

试题 H: 整数删除.本题总分：20 分

 线段树+并查集

对于每个点并查集维护左父亲和右父亲。对于每次操作线段树找到最左侧最小下标，然后返回，

这个点的左父亲等于这个点左边的点的左父亲，右同理，然后线段树修改值即可

复杂度 O(KlogN)

可以也采用set存点值和下标，然后+并查集

复杂度也是O(KlogN)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define x first
  6. #define y second
  7. #define pd push_back
  8. #define pii pair<int,ll>
  9. const int maxn=5e5+10;
  10.  
  11.  
  12.  
  13. int n,k;
  14. ll a[maxn];
  15. int l[maxn],r[maxn],f[maxn];
  16. int findl(int x)
  17. {
  18.     return x==l[x]?x:l[x]=findl(l[x]);
  19. }
  20. int findr(int x)
  21. {
  22.     return x==r[x]?x:r[x]=findr(r[x]);
  23. }
  24.  
  25. ll tr[maxn<<4];
  26. void up(int rt)
  27. {
  28.     tr[rt]=min(tr[rt<<1],tr[rt<<1|1]);
  29. }
  30. void build(int rt,int l,int r)
  31. {
  32.     tr[rt]=a[l];
  33.     if(l==r)return;
  34.     int mid=l+r>>1;
  35.     build(rt<<1,l,mid);
  36.     build(rt<<1|1,mid+1,r);
  37.     up(rt);
  38. }
  39. pii cha(int rt,int l,int r)
  40. {
  41.     if(l==r)
  42.     {
  43.         return {l,tr[rt]};
  44.     }
  45.     int mid=l+r>>1;
  46.     pii ans;
  47.     if(tr[rt<<1]<=tr[rt<<1|1])
  48.     {
  49.         ans=cha(rt<<1,l,mid);
  50.     }else
  51.     {
  52.         ans=cha(rt<<1|1,mid+1,r);
  53.     }
  54.     return ans;
  55. }
  56. void add(int rt,int l,int r,int id,ll val)
  57. {
  58.     if(id==l&&id==r)
  59.     {
  60.         tr[rt]+=val;
  61.         a[l]=tr[rt];
  62.         return;
  63.     }
  64.     int mid=l+r>>1;
  65.     if(l<=id&&id<=mid)add(rt<<1,l,mid,id,val);
  66.     else if(id>mid&&id<=r)add(rt<<1|1,mid+1,r,id,val);
  67.     up(rt);
  68. }
  69. /*
  70. 5 3
  71. 1 4 2 8 7
  72. 5 4
  73. 1 4 2 8 7
  74. 5 5
  75. 1 4 2 8 7
  76. */
  77. void solve()
  78. {
  79.     cin>>n>>k;
  80.     l[0]=0;l[n+1]=0;
  81.     r[0]=0;r[n+1]=0;
  82.     for(int i=1;i<=n;i++)
  83.     {
  84.         cin>>a[i];
  85.         l[i]=i;r[i]=i;
  86.         f[i]=1;
  87.     }
  88.     build(1,1,n);
  89.     while(k--)
  90.     {
  91.         ll mi=1e18,id=-1;
  92. //        for(int i=1;i<=n;i++)//可用线段树优化
  93. //        {
  94. //            if(mi>a[i])
  95. //            {
  96. //                mi=a[i];
  97. //                id=i;
  98. //            }
  99. //        }
  100.         pii i=cha(1,1,n);
  101.         id=i.x;mi=i.y;
  102.         f[id]=0;
  103.         l[id]=findl(l[id-1]);
  104.         r[id]=findr(r[id+1]);
  105.         if(l[id]>=1)add(1,1,n,l[id],mi);
  106.         if(r[id]<=n)add(1,1,n,r[id],mi);
  107.         add(1,1,n,id,1e17);
  108. //        a[l[id]]+=a[id];
  109. //        a[r[id]]+=a[id];
  110. //        a[id]=1e18;
  111. //        for(int i = 1; i <= n; i++)
  112. //        {
  113. //            if(f[i])
  114. //            {
  115. //                cout << a[i] << " ";
  116. //            }
  117. //        }
  118. //        cout<<endl;
  119.     }
  120.     int ff=1;
  121.      for(int i = 1; i <= n; i++)
  122.         {
  123.             if(f[i])
  124.             {
  125.                 if(ff)ff=0;
  126.                 else cout<<" ";
  127.                 cout << a[i] ;
  128.             }
  129.         }
  130. }
  131.  
  132. int main()
  133. {
  134.     ios::sync_with_stdio(0);
  135.     cin.tie(0);
  136.     cout.tie(0);
  137.     int tn=1;
  138.     //cin>>tn;
  139.     while(tn--)
  140.     {
  141.         solve();
  142.     }
  143.     return 0;
  144. }

试题 I: 景区导游 .本题总分：25 分

倍增，由于要按顺序去游览点，考虑起点那么只有A1,A2，对于2-k的点都是以A1为起点，那么其实路都差不多，假设在这之中p点不去，减去p-1到p的路径值减去p到p+1的路径值，加上p-1到p+1的路径值即可

复杂度O(NlogN+KlogN)

对于加减路径值也可以用树链剖分或lct 复杂度O(NlogN+KlogN)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int N = 2e5 + 10;
  5. int h[N], e[N], w[N], ne[N], idx = 0;
  6. int lg[N], p[N][20], deep[N], a[N];
  7. ll dis[N], n, k, sum = 0;
  8. void dfs(int lst, int now) {
  9.     deep[now] = deep[lst] + 1;
  10.     p[now][0] = lst;
  11.     for (int i = 1; (1 << i) <= deep[now]; i++)
  12.         p[now][i] = p[p[now][i - 1]][i - 1];
  13.  
  14.     for (int i = h[now]; i; i = ne[i]) {
  15.         int to = e[i], cost = w[i];
  16.         if (to != lst) {
  17.             dis[to] = dis[now] + cost;
  18.             dfs(now, to);
  19.         }
  20.     }
  21. }
  22. int lca(int u, int v) {
  23.     if (deep[u] < deep[v]) swap(u, v);
  24.     while (deep[u] > deep[v])
  25.         u = p[u][lg[deep[u] - deep[v]]];
  26.  
  27.     if (u == v) return u;
  28.     else {
  29.         for (int i = lg[deep[u]]; i >= 0; i--) {
  30.             if (p[u][i] != p[v][i])
  31.                 u = p[u][i], v = p[v][i];
  32.         }
  33.     }
  34.     return p[u][0];
  35. }
  36. inline void add(int u, int v, int t) {
  37.     e[++idx] = v, w[idx] = t, ne[idx] = h[u], h[u] = idx;
  38. }
  39. inline ll ask(int u, int v) {
  40.     if (u == 0 || v == 0) return 0;
  41.     else return dis[u] + dis[v] - 2 * dis[lca(u, v)];
  42. }
  43. inline ll query(int i) {
  44.     return ask(a[i - 1], a[i + 1]) - ask(a[i - 1], a[i]) - ask(a[i], a[i + 1]);
  45. }
  46. int main() {
  47.     cin >> n >> k;
  48.     for (int i = 1; i < n; i++) {
  49.         int u, v, t;
  50.         cin >> u >> v >> t;
  51.         add(u, v, t);
  52.         add(v, u, t);
  53.     }
  54.     for (int i = 2; i <= n; i++)lg[i] = lg[i >> 1] + 1;
  55.     dfs(0, 1);
  56.     for (int i = 1; i <= k; i++)cin >> a[i];
  57.     for (int i = 2; i <= k; i++)sum += ask(a[i - 1], a[i]);
  58.     for (int i = 1; i <= k; i++)cout << sum + query(i) << ' ';
  59. }

试题 J: 砍树 .本题总分：25 分

倍增+树上差分，对于一个数对，我们对数对路径上的值＋1，最后看是否有一条边的左右点的点值相等

复杂度O(NlogN+N)

其实要对于数对路径值+1，也可以使用树链剖分来写，这样复杂度也是O(NlogN)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define x first
  6. #define y second
  7. #define pd push_back
  8. #define pii pair<int,ll>
  9. const int maxn=1e5+10;
  10.  
  11.  
  12. struct beizeng
  13. {
  14.     int dp[22][maxn],deep[maxn];
  15.     int val[maxn];
  16.     vector<int>v[maxn];
  17.     void add(int a,int b)
  18.     {
  19.         v[a].pd(b);
  20.         v[b].pd(a);
  21.     }
  22.     void dfs(int x,int fa)
  23.     {
  24.         //dft[op]=x;
  25.         //df[x]=op++;
  26.         deep[x]=deep[fa]+1;
  27.         dp[0][x]=fa;
  28.         for(int i=1;(1<<i)<=deep[x];i++)
  29.         {
  30.             dp[i][x]=dp[i-1][dp[i-1][x]];
  31.         }
  32.         for(int y:v[x])
  33.         {
  34.             if(y==fa)continue;
  35.             dfs(y,x);
  36.         }
  37.     }
  38.     void dfs2(int x,int fa)
  39.     {
  40.         for(int y:v[x])
  41.         {
  42.             if(y==fa)continue;
  43.             dfs2(y,x);
  44.             val[x]+=val[y];
  45.         }
  46.     }
  47.     int lca(int a,int b)
  48.     {
  49.         if(deep[a]>deep[b])swap(a,b);
  50.         for(int i=20;i>=0;i--)
  51.         {
  52.             if(deep[a]<=deep[b]-(1<<i))
  53.                 b=dp[i][b];
  54.         }
  55.         if(a==b)
  56.             return a;
  57.         for(int i=20;i>=0;i--)
  58.         {
  59.             if(dp[i][a]!=dp[i][b])
  60.             {
  61.                 a=dp[i][a];
  62.                 b=dp[i][b];
  63.             }
  64.         }
  65.         return dp[0][a];
  66.     }
  67. }tree;
  68. int n,m;
  69. int a[maxn],b[maxn];
  70. void solve()
  71. {
  72.     cin>>n>>m;
  73.     for(int i=1;i<n;i++)
  74.     {
  75.         cin>>a[i]>>b[i];
  76.         tree.add(a[i],b[i]);
  77.     }
  78.     tree.dfs(1,0);
  79.     for(int i=1;i<=m;i++)
  80.     {
  81.         int x,y;
  82.         cin>>x>>y;
  83.         int c=tree.lca(x,y);
  84.         tree.val[x]++;tree.val[y]++;
  85.         tree.val[c]--;tree.val[tree.dp[0][c]]--;
  86.     }
  87.     tree.dfs2(1,0);
  88.     int ans=-1;
  89.     for(int i=n-1;i>=1;i--)
  90.     {
  91.        if(tree.val[a[i]]==m&&tree.val[b[i]]==m)
  92.        {
  93.            ans=i;
  94.            break;
  95.        }
  96.     }
  97.     cout<<ans<<endl;
  98. }
  99.  
  100. int main()
  101. {
  102.     ios::sync_with_stdio(0);
  103.     cin.tie(0);
  104.     cout.tie(0);
  105.     int tn=1;
  106.     //cin>>tn;
  107.     while(tn--)
  108.     {
  109.         solve();
  110.     }
  111.     return 0;
  112. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/438867
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号