登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›2025牛客寒假算法基础集训营2 题解

2025牛客寒假算法基础集训营2 题解

觞刈 2025-6-9 18:24:04
Preface

作为一名半退役选手，个人感觉本场难度不是太大，感觉和去年比难度貌似是下降了。在打的时候实在是由于乱七八糟的原因（包括不限于眼瞎，眼瞎，还有眼瞎），打得一般般。
感觉本场模拟题偏多，实在是吃屎。
我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.
以下是代码火车头：
  1. #include <iostream>
  2. #include
  3. #include <cstring>
  4. #include <cmath>
  5. #include <vector>
  6. #include <set>
  7. #include <queue>
  8. #include <map>
  9. #include <unordered_map>
  10. #include <iomanip>
  11. #define endl '\n'
  12. #define int long long
  13. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  14. #define rep2(i,a,b) for(int i=(a);i>=(b);i--)
  15. using namespace std;
  17. template<typename T>
  18. void cc(const vector<T> &tem) {
  19.     for (const auto &x: tem) cout << x << ' ';
  20.     cout << endl;
  21. }
  23. template<typename T>
  24. void cc(const T &a) { cout << a << endl; }
  26. template<typename T1, typename T2>
  27. void cc(const T1 &a, const T2 &b) { cout << a << ' ' << b << endl; }
  29. template<typename T1, typename T2, typename T3>
  30. void cc(const T1 &a, const T2 &b, const T3 &c) { cout << a << ' ' << b << ' ' << c << endl; }
  32. void cc(const string &s) { cout << s << endl; }
  34. void fileRead() {
  35. #ifdef LOCALL
  36.     freopen("D:\\AADVISE\\Clioncode\\untitled2\\in.txt", "r", stdin);
  37.     freopen("D:\\AADVISE\\Clioncode\\untitled2\\out.txt", "w", stdout);
  38. #endif
  39. }
  41. void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
  43. inline int max(int a, int b) {
  44.     if (a < b) return b;
  45.     return a;
  46. }
  48. inline double max(double a, double b) {
  49.     if (a < b) return b;
  50.     return a;
  51. }
  53. inline int min(int a, int b) {
  54.     if (a < b) return a;
  55.     return b;
  56. }
  58. inline double min(double a, double b) {
  59.     if (a < b) return a;
  60.     return b;
  61. }
  63. void cmax(int &a, const int &b) { if (b > a) a = b; }
  64. void cmin(int &a, const int &b) { if (b < a) a = b; }
  65. void cmin(double &a, const double &b) { if (b < a) a = b; }
  66. void cmax(double &a, const double &b) { if (b > a) a = b; }
  67. using PII = pair<int, int>;
  68. using i128 = __int128;
  69. using vec_int = std::vector<int>;
  70. using vec_char = std::vector<char>;
  71. using vec_double = std::vector<double>;
  72. using vec_int2 = std::vector<std::vector<int> >;
  73. using que_int = std::queue<int>;
复制代码
Problem E. 一起走很长的路！

一个很典典的题，简简单单推式子就好了，比\(C\)题简单不少。

设前缀和\(pre_i=a_1+a_2+...+a_i\)，那么需要满足条件：\(pre_i-pre_{l-1}>=a_{i+1}\)，\(l r1) return;        if (l1  1;        if (r1  r1) return info();        if (l1  1;        if (r1 > T;    while (T--) {        cin >> n;        int q;        cin >> q;        rep(i, 1, n) {            cin >> A;            pre += A;            pre += pre[i - 1];        }        seg.clear(1, n - 1);         rep(i, 1, n-1) {            dis = pre - A[i + 1];            seg.add(i, i, dis);        }         rep(i, 1, q) {            int l, r;            cin >> l >> r;            int tem = seg.qry(l, r - 1).mmin;            int ans = 0;            if (tem < pre[l - 1]) {                ans = pre[l - 1] - tem;            }            cc(ans);        }     }    return 0;}[/code]Problem F. 一起找神秘的数！

稍微画一画就能发现，满足条件需要\(x=y\)。
具体推的话，可以用韦恩图画一下就好了，记住，‘或’是求并集，异或是去重，and 是求交集。
  1. //--------------------------------------------------------------------------------
  2. const int N = 1e5 + 10;
  3. const int M = 1e6 + 10;
  4. const int mod = 1e9 + 7;
  5. const int INF = 1e16;
  6. int n, m, T;
  8. //--------------------------------------------------------------------------------
  9. //struct or namespace:
  11. //--------------------------------------------------------------------------------
  13. signed main() {
  14.         fileRead();
  15.         kuaidu();
  16.         T = 1;
  17.         //cin >> T;
  18.         while (T--) {
  19.                 bool fl = 0;
  20.                 rep(i, 1, 7) {
  21.                         int a;
  22.                         cin >> a;
  23.                         if (a == 4 or a == 7) fl = 1;
  25.                 }
  26.                 if (!fl) cc("YES");
  27.                 else cc("NO");
  29.         }
  30.         return 0;
  31. }
复制代码
Problem G. 一起铸最好的剑！

直接模拟就好了，不要直接用\(pow\)函数就好。
  1. //--------------------------------------------------------------------------------
  2. const int N = 5e5 + 10;
  3. const int M = 1e6 + 10;
  4. const int mod = 1e9 + 7;
  5. const int INF = 1e16;
  6. int n, m, T;
  7. int A[N];
  8. //--------------------------------------------------------------------------------
  9. //struct or namespace:
  11. //--------------------------------------------------------------------------------
  13. signed main() {
  14.         fileRead();
  15.         kuaidu();
  16.         T = 1;
  17.         //cin >> T;
  18.         while (T--) {
  19.                 cin >> n;
  20.                 rep(i, 1, n) cin >> A[i];
  21.                 sort(A + 1, A + n + 1);
  22.                 // rep(i, 1, n) cc(A[i]);
  24.                 int val = A[(n + 1 + 1) / 2] - 1;
  25.                 cc(val);
  26.         }
  27.         return 0;
  28. }
复制代码
Problem H. 一起画很大的圆！

最吃屎的时候，交了\(12\)发才过，还是最后蒙过去的。
首先先读题，边界！一开始读题读成了内部也可以，然后就先固定了两个点在斜线，然后找了最接近斜线的横坐标的每一个点去判断，时间复杂度按理来说是横坐标或者纵坐标的差值，\(1\)秒应该是能勉强跑过才对的，但是\(wa\)了，要不就是\(t\)了。
然后发现是在边界上...，但是依旧不会，脑子已经秀逗了。
最后暴力枚举了角落边界和中间边界的位置，然后跑过的。（其实也是有直觉是感觉两个点在角落，一个点在另一个同侧的角落，但是不确定）
  1. //--------------------------------------------------------------------------------
  2. const int N = 2e5 + 10;
  3. const int M = 1e6 + 10;
  4. const int mod = 1e9 + 7;
  5. const int INF = 1e16;
  6. int n, m, T;
  7. char s[N];
  8. //--------------------------------------------------------------------------------
  9. //struct or namespace:
  11. //--------------------------------------------------------------------------------
  13. signed main() {
  14.         fileRead();
  15.         kuaidu();
  16.         T = 1;
  17.         cin >> T;
  18.         while (T--) {
  19.                 cin >> n >> m;
  21.                 if (n == m) {
  22.                         cc("NO");
  23.                         continue;
  24.                 }
  27.                 if (m >= n - m + 1) {
  28.                         if (n - m - 1 <= 25 and n >= 4 and m >= 3) {
  29.                                 cc("YES");
  30.                                 s[1] = 'a';
  31.                                 s[n] = 'a';
  32.                                 rep(i, n-m+1, m) s[i] = 'a';
  33.                                 rep(i, 2, n-m+1-1) {
  34.                                         s[i] = 'a' + i - 1;
  35.                                         s[n - i + 1] = s[i];
  36.                                 }
  38.                                 rep(i, 1, n) { cout << s[i]; }
  40.                                 cout << endl;
  41.                         }
  42.                         else {
  43.                                 cc("NO");
  44.                         }
  45.                 }
  46.                 else {
  47.                         if (m - 1 + (n - m - m) <= 25) {
  49.                                 cc("YES");
  51.                                 int k = m - 1 + (n - m - m);
  52.                                 int x = n - k - 2, y = k - x;
  53.                                 rep(i, 1, x) { cout << char('a' + i); }
  54.                                 cout << 'a';
  55.                                 rep(i, x+1, x+y) { cout << char('a' + i); }
  56.                                 cout << 'a';
  57.                                 rep(i, 1, x) { cout << char('a' + i); }
  59.                                 cout << endl;
  61.                         }
  62.                         else {
  63.                                 cc("NO");
  64.                         }
  65.                 }
  66.         }
  67.         return 0;
  68. }
复制代码
Problem I. 一起看很美的日落！

一个典典的树形dp，但是赛时没有时间做了，应该是有铜+的难度的。
首先我们对于每一位可以独立看待，于是每个点的权值变成了0或者1，然后经典树形dp。
设\(dp_x\)是包含了\(x\)的联通块的\(ans\)，\(f_{x,0}\)是联通块里0的个数，\(f_{x,1}\)同理，\(g_x\)是联通块大小。
然后考虑如何合并两个联通块：
  1. //--------------------------------------------------------------------------------
  2. const int N = 2e5 + 10;
  3. const int M = 1e6 + 10;
  4. const int mod = 1e9 + 7;
  5. const int INF = 1e16;
  6. int n, m, T;
  7. int pre[N][31];
  8. int suf[N][31];
  9. string s;
  11. //--------------------------------------------------------------------------------
  12. //struct or namespace:
  14. //--------------------------------------------------------------------------------
  15. bool check(int len) {
  16.         rep(i, 1, n) {
  17.                 int l = i, r = i + len - 1;
  18.                 if (l < 1 or r > n) break;
  19.                 if (pre[l - 1][s[l] - 'a'] or suf[r + 1][s[r] - 'a']) {
  20.                         return 1;
  21.                 }
  22.         }
  23.         return 0;
  24. }
  26. signed main() {
  27.         fileRead();
  28.         kuaidu();
  29.         T = 1;
  30.         //cin >> T;
  31.         while (T--) {
  32.                 cin >> n;
  33.                 cin >> s;
  34.                 s = ' ' + s;
  36.                 rep(i, 1, n) {
  37.                         rep(j, 0, 25) pre[i][j] = pre[i - 1][j];
  38.                         pre[i][s[i] - 'a'] = 1;
  39.                 }
  40.                 rep2(i, n, 1) {
  41.                         rep(j, 0, 25) suf[i][j] = suf[i + 1][j];
  42.                         suf[i][s[i] - 'a'] = 1;
  43.                 }
  45.                 int ans = 0;
  47.                 int l = 0, r = n;
  48.                 while (l + 1 != r) {
  49.                         int mid = l + r >> 1;
  50.                         if (check(mid)) l = mid;
  51.                         else r = mid;
  52.                 }
  53.                 cc(l);
  55.         }
  56.         return 0;
  57. }
复制代码
我觉得式子很显然，大家看了就晓得了。代码很简洁，顺手抄了个题解的取模类。
  1. //--------------------------------------------------------------------------------
  2. const int N = 2e5 + 10;
  3. const int M = 1e6 + 10;
  4. const int mod = 1e9 + 7;
  5. const int INF = 1e16;
  6. int n, m, T;
  8. //--------------------------------------------------------------------------------
  9. //struct or namespace:
  10. class SEG {
  11. #define xl x+x
  12. #define xr x+x+1
  14.     //TODO 节点维护信息、apply函数、up函数
  15.     struct info {
  16.         int mmin = INF;
  18.         void apply(int k) {
  19.             mmin = k;
  20.         }
  22.         friend info operator+(const info &q1, const info &q2) {
  23.             info q;
  24.             q.mmin = min(q1.mmin, q2.mmin);
  25.             return q;
  26.         }
  27.     };
  29.     int L, R;
  30.     info F[unsigned(N * 2.7)];
  32.     void init(int x, int l, int r) {
  33.         if (l == r) {
  34.             F[x] = info();
  35.             return;
  36.         }
  37.         int mid = l + r >> 1;
  38.         init(xl, l, mid), init(xr, mid + 1, r);
  39.         F[x] = F[xl] + F[xr];
  40.     }
  42.     void add(int x, int l, int r, int l1, int r1, int k) {
  43.         if (l1 > r1) return;
  44.         if (l1 <= l and r <= r1) {
  45.             F[x].apply(k);
  46.             return;
  47.         }
  48.         int mid = l + r >> 1;
  49.         if (r1 <= mid) add(xl, l, mid, l1, r1, k);
  50.         else if (mid < l1) add(xr, mid + 1, r, l1, r1, k);
  51.         else add(xl, l, mid, l1, mid, k), add(xr, mid + 1, r, mid + 1, r1, k);
  52.         F[x] = F[xl] + F[xr];
  53.     }
  55.     info qry(int x, int l, int r, int l1, int r1) {
  56.         if (l1 > r1) return info();
  57.         if (l1 <= l and r <= r1) return F[x];
  58.         int mid = l + r >> 1;
  59.         if (r1 <= mid) return qry(xl, l, mid, l1, r1);
  60.         else if (mid < l1) return qry(xr, mid + 1, r, l1, r1);
  61.         else { return qry(xl, l, mid, l1, mid) + qry(xr, mid + 1, r, mid + 1, r1); }
  62.     }
  63. #undef xl
  64. #undef xr
  66. public:
  67.     void clear(int l, int r) {
  68.         L = l, R = r;
  69.         init(1, l, r);
  70.     }
  72.     void add(int l, int r, int k) { add(1, L, R, l, r, k); }
  73.     info qry(int l, int r) { return qry(1, L, R, l, r); }
  74. };
  76. SEG seg;
  77. int A[N], pre[N], dis[N];
  78. //--------------------------------------------------------------------------------
  80. signed main() {
  81.     fileRead();
  82.     kuaidu();
  83.     T = 1;
  84.     //cin >> T;
  85.     while (T--) {
  86.         cin >> n;
  87.         int q;
  88.         cin >> q;
  89.         rep(i, 1, n) {
  90.             cin >> A[i];
  91.             pre[i] += A[i];
  92.             pre[i] += pre[i - 1];
  93.         }
  94.         seg.clear(1, n - 1);
  96.         rep(i, 1, n-1) {
  97.             dis[i] = pre[i] - A[i + 1];
  98.             seg.add(i, i, dis[i]);
  99.         }
  101.         rep(i, 1, q) {
  102.             int l, r;
  103.             cin >> l >> r;
  104.             int tem = seg.qry(l, r - 1).mmin;
  105.             int ans = 0;
  106.             if (tem < pre[l - 1]) {
  107.                 ans = pre[l - 1] - tem;
  108.             }
  109.             cc(ans);
  110.         }
  112.     }
  113.     return 0;
  114. }
复制代码
Problem L. 还会再见吗？

看了题解，虚树。
于是直接再见。
学虚树不如继续搞开发。
Problem M. 那是我们的影子

赛时没有做出来，赛后看题解发现不算太难。
但是个人感觉难度应该和\(I\)差不多才对。只能说这种题自己总会写的复杂，感慨大佬写的代码很简洁。
感觉官方题解写的很好很清楚，建议去看（不是自己懒了
借鉴了\(Heltion\)的代码：
  1. //--------------------------------------------------------------------------------
  2. const int N = 5e5 + 10;
  3. const int M = 1e6 + 10;
  4. const int mod = 1e9 + 7;
  5. const int INF = 1e16;
  6. int n, m, T;
  7. int A[N];
  8. //--------------------------------------------------------------------------------
  9. //struct or namespace:
  11. //--------------------------------------------------------------------------------
  13. signed main() {
  14.         fileRead();
  15.         kuaidu();
  16.         T = 1;
  17.         //cin >> T;
  18.         while (T--) {
  19.                 cin >> n;
  20.                 rep(i, 1, n) {
  21.                         int a, b;
  22.                         cin >> a >> b;
  23.                         cc(b - a + 1);
  24.                 }
  25.         }
  26.         return 0;
  27. }
复制代码
PostScript

只能说自己吃屎吃得太多，有些题自己写的太烂，点名批评\(h\)题。
感觉难度比去年真的少了很多，不知道是不是错觉。
题解如果有误希望可以指出来。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
觞刈
2025-6-9 18:24:04

0

粉丝关注

10

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫