08-03 21:01 幼儿园中班 C++ 发布于福建

关注

牛客周赛103文字版题解

写在前面

a.今天2025年8月3日，恰逢 qcjj & zngg 结婚，在此送上诚挚的新婚祝福。祝他们新婚快乐，百年好合，早生贵子~

b.如有不理解的地方可以私信出题人，会尽快回复的。

c.赛前换了比赛题目名字，与视频讲解中略有出入。

A.清楚（好数）

预估难度：100

按照题意，判断给定的数字 $n$ 是否存在尾 0 即可，即判断 $n$ 是否是 10 的倍数。

时间复杂度 $\mathcal{O(1)}$ 。

参考代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(int task) {
  int n;
  cin >> n;
  if (n % 10 == 0)
    cout << "NO";
  else
    cout << "YES";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

B.姐姐（好数组）

预估难度：600

若要满足断开的数组单调，由于断开的是一个位置，所以最多存在一个位置存在 $a_i>a_{(i+1)\mod{n}}$ 。循环判断次数即可。

时间复杂度 $\mathcal{O(n)}$ 。

参考代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(int task) {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    cnt += (a[i] > a[(i + 1) % n]);
  }
  cout << (cnt <= 1 ? "YES" : "NO") << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

C.智乃（好排列）

预估难度：1000

由于一个长度为 $k$ 的排列必须包含 $1\sim k$ 的所有元素，所以题意可以转化成对于序列 1,2,3, $\cdots$ ,n 的任意前缀都需要连续放置。

初始序列只有 1 这个元素，对于 $i\in[2,n]$ ，我们可以考虑放在序列的首部或者尾部，有 2 种选择，根据乘法原理，答案便是 $2^{n-1}$ 种， $n\leqq 10^9$ ，则采用快速幂解决。

时间复杂度 $\mathcal{O(log(n))}$ 。

参考代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int mod = 1e9 + 7;
i64 qmi(i64 a, i64 b) {
  i64 ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
void solve(int task) {
  int n;
  cin >> n;
  cout << qmi(2, n - 1) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

D.哥哥（好串）

预估难度：1200

分类讨论或者 dp 做法均可。

做法一：dp 做法可参考周赛 102 的 D 题，此题是出题人读错的产物。

做法二：

当序列中存在大于等于 $3$ 个好串，答案为 0。当序列中存在 2 个好串：即序列被分成了3个部分 xxxxxyyyyyyxxxx 此形式，所以只需要改变唯一一个非连接点的位置即可达到三个，而对于长度小于等于 4 的两种不满足，所以特判。若序列为 1001 和 0110 答案为 2，否则为 1.

当序列中存在 1 个好串：即序列被分成了2个部分 xxxxxyyyyy 此形式，所以只需要改变唯一一个非连接点的位置即可达到三个，而对于长度小于等于 4 的两种不满足，所以特判。若序列为 1100 和 0011 答案为 2，否则为 1. 当序列存在 0 个好串：即序列只存在一个部分 xxxxxxx 的形式，此时序列答案为 2。

时间复杂度 $\mathcal{O(n)}$ 。

参考代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(int task) {
  int n, cnt = 0;
  string s;
  cin >> n;
  cin >> s;
  for (int i = 0; i + 1 < n; i++) {
    cnt += (s[i] != s[i + 1]);
  }
  if (cnt >= 3) {
    cout << "0\n";
  } else if (cnt == 2) {
    if (s == "1001" || s == "0110")
      cout << 2 << "\n";
    else
      cout << 1 << "\n";
  } else if (cnt == 1) {
    if (s == "1100" || s == "0011")
      cout << 2 << "\n";
    else
      cout << "1\n";
  } else if (cnt == 0) {
    cout << 2 << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

E.新婚（好路径）

预估难度：1600

做法一：对于每个点 $u$ ，可以考虑用 pair<int,int> $f_{u,i}$ 来维护从 $u$ 出发向上走 $i$ 个点（包含 $u$ ）的值和当前存在多少个前导 0（用于维护一个点向下走的情况）。对于一个点若是 1，则 $f_{u,i}=\{f_{father,i-1}.first\times (2^{i-1}),0\}$ 。对于一个点若是 0，则 $f_{u,i}=\{f_{father,i-1}.first,f_{father,i-1}.second+1\}$ 。对于每个位置的翻转可以采用位运算如下方法：

unsigned int rev(unsigned int x) {
    x=((x&0x55555555u)<<1)|((x>>1)&0x55555555u);
    x=((x&0x33333333u)<<2)|((x>>2)&0x33333333u);
    x=((x&0x0F0F0F0Fu)<<4)|((x>>4)&0x0F0F0F0Fu);
    x=((x&0x00FF00FFu)<<8)|((x>>8)&0x00FF00FFu);
    x=(x<<16)|(x>>16);
    return x;
}
unsigned int ff(unsigned int x) {
    int L=32-__builtin_clz(x);
    unsigned int ans=rev(x);
    return ans>>(32-L);
}

这样时间复杂度可以做到 $\mathcal{O(21\times n)}$ ，空间复杂度 $\mathcal{O(21\times n+2^{20})}$ ，当然先可以先存下询问的数字用 map 记录，空间复杂度可以约为 $\mathcal{O(21\times n)}$ ，根据 E 题难度就没有再进一步扩大数据范围。

做法二： 当然也可以采用每个点暴力操作 $21(1<<20)$ 个位置的做法，此处不再展开。

参考代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 22;
pair<int, int> f[100001][N];
unsigned int rev(unsigned int x) {
  x = ((x & 0x55555555u) << 1) | ((x >> 1) & 0x55555555u);
  x = ((x & 0x33333333u) << 2) | ((x >> 2) & 0x33333333u);
  x = ((x & 0x0F0F0F0Fu) << 4) | ((x >> 4) & 0x0F0F0F0Fu);
  x = ((x & 0x00FF00FFu) << 8) | ((x >> 8) & 0x00FF00FFu);
  x = (x << 16) | (x >> 16);
  return x;
}
unsigned int ff(unsigned int x) {
  int L = 32 - __builtin_clz(x);
  unsigned int ans = rev(x);
  return ans >> (32 - L);
}
bool cnt[1 << 22];
void solve(int task) {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  s = " " + s;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < N; j++) {
      f[i][j] = {-1, 0};
    }
  }
  vector<vector<int>> e(n + 1);
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  vector<int> val;
  auto dfs = [&](auto &&self, int u, int fa) -> void {
    int num = (s[u] == '1' ? 1 : 0);
    f[u][1] = {num, 0};
    cnt[f[u][1].first] = 1;
    if (num & 1) {
      for (int i = 2; i < N; i++) {
        if (f[fa][i - 1].first == -1) break;
        f[u][i] = {f[u][1].first * (1 << (i - 1)) + f[fa][i - 1].first, 0};
        cnt[f[u][i].first] = 1;
      }
    } else {
      for (int i = 2; i < N; i++) {
        f[u][i] = {f[fa][i - 1].first, f[fa][i - 1].second + 1};
      }
    }
    for (auto v : e[u]) {
      if (v == fa) continue;
      self(self, v, u);
    }
  };
  dfs(dfs, 1, 0);
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j < N; j++) {
      if (f[i][j].first == -1) break;
      cnt[(ff(f[i][j].first) * (1 << f[i][j].second))] = 1;
    }
  }
  while (q--) {
    int x;
    cin >> x;
    if (cnt[x]) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

F.快乐（最长公共前缀长度之和）

预估难度：1900

做法一:

对于字符串集合 $t$ ，首先建立一棵 $\text{trie}$ 维护字符串集合，并且标记每个点出现的次数（此处是每个点，并非 $t_i$ 的最后一个位置，因为要维护 $\text{LCP}$ 的长度），然后用哈希维护 $\text{trie}$ 上的每个前缀的贡献总和，便可以得到一个字符串的贡献次数总数。

最后扫描字符串 $s$ 的所有后缀 $l=i,r=n$ 。若对于 $s[l:mid]$ 出现过，则 $[l:less_{mid}]$ 也必然出现过，所以此处长度的贡献具有单调性。找到最右边的位置的哈希在 $\text{trie}$ 对应的贡献，最后取较大值即可。

对于 $\text{trie}$ 建立部分的时间复杂度为 $\mathcal{O(\sum |t|)}$ 。

对于枚举字符串 $s$ 的部分，都是既要二分后缀，又要查找哈希值是否存在，所以需要 $\mathcal{O(\sum |t|+n\times \text{logn} \times \text{logn})}$ 。

前缀和做法：当然如果你不会 $\text{trie}$ 也无妨，也可以直接采用前缀和的方法先记录哈希值为 $x$ 的贡献，然后再用前缀和累计一下其所有前缀的贡献也可以。

对于存哈希的方法可以以任何方式的形式存，经过测试，使用 map , unordered_map ,容器等的办法大约 400ms $\sim$ 1500 ms ，都可以在 2 s 的时间内通过。

参考代码 trie：：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 1;
int tree[N * 5][26];
int cnt[N * 5 * 26];
i64 PP[N];
int g = 0;
void ins(string s) {
  int idx = 0;
  for (auto c : s) {
    int k = c - 'a';
    if (tree[idx][k] == 0) tree[idx][k] = ++g;
    idx = tree[idx][k];
    cnt[idx]++;
  }
}
const int P = 13331;
const i64 mod = 4611686018427387847;
vector<pair<i64, int>> h1;
void gg(int he, i64 nowhash, int sumtr) {
  for (int i = 0; i <= 25; i++) {
    if (tree[he][i] != 0) {
      i64 nexthash = ((__int128_t)nowhash * P % mod + (i + 97)) % mod;
      sumtr += cnt[tree[he][i]];
      h1.push_back({nexthash, sumtr});
      gg(tree[he][i], nexthash, sumtr);
      sumtr -= cnt[tree[he][i]];
    }
  }
}
void init() {
  h1.clear();
  for (int i = 0; i <= g; i++) cnt[i] = 0;
  for (int i = 0; i <= g; i++) {
    for (int j = 0; j <= 25; j++) tree[i][j] = 0;
  }
  g = 0;
}
void solve(int task) {
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  for (int i = 1; i <= m; i++) {
    string t;
    cin >> t;
    ins(t);
  }
  gg(0, 0, 0);
  s = " " + s;
  vector<i64> p(n + 1);
  for (int i = 1; i <= n; i++) {
    p[i] = ((__int128_t)p[i - 1] * P % mod + (int)(s[i] - 0)) % mod;
  }
  int ans = 0;
  sort(h1.begin(), h1.end(), [&](auto a, auto b) { return a.first < b.first; });
  for (int i = 1; i <= n; i++) {
    int l = i, r = n;
    while (l <= r) {
      int mid = (l + r) >> 1;
      i64 now = ((__int128_t)p[mid] -
                 (__int128_t)p[i - 1] * PP[mid - i + 1] % mod + mod) %
                mod;
      auto f = [&](i64 x) {
        int ll = 0, rr = h1.size() - 1;
        while (ll <= rr) {
          int mid = (ll + rr) >> 1;
          if (h1[mid].first > x) {
            rr = mid - 1;
          } else if (h1[mid].first < x) {
            ll = mid + 1;
          } else {
            return mid;
          }
        }
        return -1;
      };
      int t = f(now);
      if (t != -1) {
        ans = max(ans, h1[t].second);
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
  }
  cout << ans << "\n";
  init();
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  PP[0] = 1;
  for (int i = 1; i < N; i++) PP[i] = (__int128_t)PP[i - 1] * P % mod;
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

参考代码前缀和：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int P = 13331;
const i64 mod = 4611686018427387847;
const int N = 1e5 + 1;
i64 PP[N];
void solve(int task) {
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  map<i64, int> h1;
  map<i64, int> cnt;
  vector<string> t(m + 1);
  for (int i = 1; i <= m; i++) {
    cin >> t[i];
    i64 backh = 0;
    for (int j = 0; j < t[i].size(); j++) {
      i64 nowh = ((__int128_t)backh * P % mod + (t[i][j] - 0)) % mod;
      cnt[nowh]++;
      backh = nowh;
    }
  }
  for (int i = 1; i <= m; i++) {
    i64 backh = 0;
    for (int j = 0; j < t[i].size(); j++) {
      i64 nowh = ((__int128_t)backh * P % mod + (t[i][j] - 0)) % mod;
      h1[nowh] = h1[backh] + cnt[nowh];
      backh = nowh;
    }
  }
  s = " " + s;
  vector<i64> p(n + 1);
  for (int i = 1; i <= n; i++) {
    p[i] = ((__int128_t)p[i - 1] * P % mod + (int)(s[i] - 0)) % mod;
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int l = i, r = n;
    while (l <= r) {
      int mid = (l + r) >> 1;
      i64 now = ((__int128_t)p[mid] -
                 (__int128_t)p[i - 1] * PP[mid - i + 1] % mod + mod) %
                mod;
      if (h1.count(now)) {
        ans = max(ans, h1[now]);
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
  }
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  PP[0] = 1;
  for (int i = 1; i < N; i++) PP[i] = (__int128_t)PP[i - 1] * P % mod;
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

做法二：

验题人 thisislike_fan 也写了O(n) 的做法，还有一些正式赛中各种不同的做法，此处给出一种

出题人没想到，于是寄出了 AI：首先将主串 $s$ 、分隔符以及所有模式串拼接成一个大字符串 $S$ ，并用 $flag$ 数组标记模式串的起始位置，以便后续区分模式串对应的后缀。然后利用 $\text{SA-IS}$ 算法构建 $S$ 的后缀数组，得到所有后缀的字典序排序结果，再通过 $\text{Kasai}$ 算法计算最长公共前缀数组，记录排序后相邻后缀的公共前缀长度。之后通过两次单调栈遍历（左到右和右到左）来统计主串中每个位置的贡献：左到右遍历时，用栈维护 $\text{LCP}$ 值和对应的模式串后缀计数，累加主串位置与左侧模式串后缀的 $\text{LCP}$ 总和；右到左遍历时类似处理右侧的贡献，两次遍历的结果之和存入 $ans$ 数组。最后， $ans$ 数组的最大值即为所求，也就是主串中与所有模式串的公共前缀长度之和最大的数值。

还有各种姿势的不同代码可自行在前排查看。

全部评论

推荐最新楼层

可爱抱抱呀😥

北京邮电大学 Java

调了半天不知道哪里的问题： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78645294

点赞回复分享

发布于 08-04 23:29 河北

convie

南昌航空大学前端工程师

为什么你的题解要放在讨论区呀

点赞回复分享

发布于 08-04 11:53 江西

08-01 16:08

门头沟学院运营

回家吧孩子现在周末也能上班了

真的很糟糕：哇偶，核动力驴吗

点赞评论收藏

08-04 16:48

西安邮电大学产品经理

网易互娱你收了我呗

收到笔试参加了，感觉不是很难，让我进吧听我一句劝，收我让你知道什么叫便宜没好货（开玩笑） 嘿呀

真的很糟糕：很强了

投递网易游戏等公司7个岗位

点赞评论收藏

07-15 18:31

已编辑

广东科贸职业学院嵌入式硬件工程师

求内推

求捞： 求职岗位：能学习到东西就行（可接受出差）期望薪资：到手4-5k专业：嵌入式技术应用学历：专科期望工作地：广州

点赞评论收藏

07-22 09:09

河南科技学院 Java

26双非秋招实习

各位大佬们，帮我提提建议吧，投了几百份简历拿不到面试，是简历问题还是什么问题呀！想迎接秋招

程序员牛肉：1.大头肯定是院校问题，这个没啥说的。 2.虽然有实习，但是实习的内容太水了，在公司待了七个月的时间，看起来就只做了jwt和接入redis。爬取新闻，数据导入。这几个需求值得你做七个月吗？这不就是三四个月的工作量吗？我要是面试官的话真心会认为你能力不太行。所以既然有实习了，一定要好好写，像是Swagger这种东西是真没必要写上去，就拉一个包的事情。 3.我个人觉得话，在校生不要把自己当社招看，除非你的项目是特别牛逼，特别有名的含金量，否则不要写这种密密麻麻的一串子工作职责。你的项目只有一个作用，就是供面试官从中来抽取八股对你进行拷打。但是你现在这个看不来什么技术点，可以改一下，详细表述一下你用什么技术实现了什么功能，在实现这个功能的过程中，你解决了什么难题。

点赞评论收藏