---

一、选择题（每题 2 分，共 30 分）

1. 线性同余方程组

$$\begin{cases} x \equiv -1 \pmod 7\\ x \equiv 9 \pmod{17} \end{cases}$$

的最小自然数解的个位是（ ）。 {{ select(1) }}

• A. 1
• B. 3
• C. 6
• D. 8

2. 你需要维护一个初始为空的多重集合 S，支持“添加一个数 x”和“询问 x 在 S 中出现的次数”。 下列 STL 容器中，能保证单次操作最坏复杂度为 $O(\log |S|)$ 的前提下，使用最方便的是（ ）。 {{ select(2) }}

• A. set
• B. multiset
• C. priority_queue
• D. map

3. 在 Linux 系统中，返回上一级目录的命令是（ ）。 {{ select(3) }}

• A. back
• B. cd /.
• C. cd
• D. cd ..

4. 一张 100 个结点的简单无向图存在欧拉路径，则图上至多有（ ）条边。 {{ select(4) }}

• A. 4950
• B. 4900
• C. 99
• D. 前三个选项都不对

5. 以下程序片段的输出是（ ）。

bitset<8> a;
a[4] = 1; a.flip(); a.flip(2);
a &= a << 3; cout << a;

{{ select(5) }}

• A. 01001000
• B. 00010010
• C. 00001001
• D. 01001111

6. Alice 给一些长度为 200 的 01 串进行自然溢出哈希。串 $a_0a_1\ldots a_k$ 的哈希值为 $\left(\sum_{i=0}^{k} a_i B^i\right) \bmod 2^{64}$。下列 B 的取值中，最合适的是（ ）。 {{ select(6) }}

• A. 1
• B. 6
• C. 27
• D. $2^{63}+1$

7. 一棵二叉树满足小根堆性质，其中序遍历为 9, 1, 4, 6, 2, 8, 7, 3, 5，则其前序遍历为（ ）。 {{ select(7) }}

• A. 9, 8, 6, 4, 1, 2, 7, 5, 3
• B. 1, 2, 4, 6, 3, 5, 7, 8, 9
• C. 1, 4, 2, 6, 5, 3, 7, 8, 9
• D. 1, 9, 2, 4, 6, 3, 7, 8, 5

8. 在 $n$ 个结点、$m=\Theta(n)$ 的稀疏有向图中用 SPFA 求 1 到各点最短路（无负环）。若用优先队列替换原队列，则（ ）。 {{ select(8) }}

• A. 最坏时间复杂度为 $O(nm)$
• B. 正权图中，时间复杂度为 $O(n\log n)$
• C. 有负边权时，算法可能无法结束
• D. 令 $T(n)$ 为 n 个结点强连通图的最小用时，则 $T(n)=O(n\log n)$

9. 现有一棵 2025 个结点的有根树，根为 1，满足结点 $i(2\le i\le 2025)$ 的父结点为 $\lfloor i/2\rfloor$。 通过更改根结点，可让结点 920 和 457 的最近公共祖先变成（ ）。 {{ select(9) }}

• A. 28
• B. 914
• C. 460
• D. 231

10. 定义递归函数

$$f(x)= \begin{cases} 1,& x\ge 2\\ 0,& 1<x<2\\ f(3x),& x\le 1 \end{cases}$$

若 $x$ 在 $(1/6,\,1/2)$ 间随机均匀选取，则 $f(x)=1$ 的概率是（ ）。 {{ select(10) }}

• A. $1/9$
• B. $1/6$
• C. $1/3$
• D. 前三个选项都不对

11. 8 个小朋友手拉手围成两个圆圈，每圈 4 人，面向圆圈内部。两个圆圈没有顺序，且旋转后重合视为一种。共有（ ）种排法。 {{ select(11) }}

• A. 1260
• B. 2520
• C. 5040
• D. 前三个选项都不对

12. 一程序运行时间 $T(n)$ 满足 $T(1)=O(1)$，$T(n)=T(\lfloor\sqrt n\rfloor)+\log_2 n$。其时间复杂度为（ ）。 {{ select(12) }}

• A. $O(\log n)$
• B. $O(\log n \log\log n)$
• C. $O(\log^2 n)$
• D. $O(\sqrt n)$

13. 为避免快排在“基本有序”时退化，改为“三数取中作为基准”。但仍可能退化为 $O(n^2)$，例如（ ）。 {{ select(13) }}

• A. $2,3,4,\ldots,n,1,n+1,n+2,\ldots,2n$
• B. $1,3,5,\ldots,2n-1,\,2n,\,2n-2,\ldots,6,4,2$
• C. $1,2,\ldots,2n$ 随机打乱
• D. 前三个选项都不对

14. 在 $3^{48}$、$\varphi(119)$、$C_9$ 中，模 97 意义下与 $96!$ 同余的数有（ ）个。（注：$C_8=1430$） {{ select(14) }}

• A. 0
• B. 1
• C. 2
• D. 3

15. NOI 2025 于 7 月 18 日落幕。本次是 NOI 全国赛第三次落地历史文化名城（ ）。 {{ select(15) }}

• A. 临沂
• B. 绍兴
• C. 杭州
• D. 南京

---

二、阅读程序（无特殊说明时判断 1.5 分，选择 3 分，共 40 分）

（1）第 1 题（12 分）

判断题

16. 若将第 21 行改为 cout << (function_2(x, y) & function_2(y, x)) << "\n"; 输出不变。（ ） {{ select(16) }}

• 正确
• 错误

17. 若将第 7 行替换为 return u ^ (1ull << 63) - 1; 后结果不变。（ ） {{ select(17) }}

• 正确
• 错误

18.（2 分）若将第 21 行改为 cout << (function_2(x, y) | function_2(y, x)) << "\n"; 则输出一定大于等于任意一个输入的数。（ ） {{ select(18) }}

• 正确
• 错误

选择题

19. 若将第 4 行替换为 unsigned int x, y;，第 21 行改为 cout << (function_2(x,y)|function_2(y,x)|function_3(x,y)) << "\n"; 且输入 12345678910 10987654321，输出为（ ）。 {{ select(19) }}

• A. 10985409584
• B. 12347923647
• C. 4294967293
• D. 以上结果均可能不正确

20.（4 分）当输入为 68 53 时，将第 21 行替换为（ ）可使输出结果最大。 {{ select(20) }}

• A. cout << (function_2(x,y) | function_3(x,y)) << "\n";
• B. cout << (function_2(y,x) | function_3(x,y)) << "\n";
• C. cout << (function_2(x,y) & function_3(x,y)) << "\n";
• D. cout << (function_2(y,x) & function_3(x,y)) << "\n";

---

（2）第 17 题（14 分）

#include <cstdio>
#include <iostream>
using namespace std;

const int N = 1.01e6;
char s[N];
int n, l[N], r[N];
int f[N][2];

int solve1() {
  int res = 0;
  for (int i = 1, x = 0; i <= n; i++) {
    l[i] = l[i - 1];
    if (s[i] == '0') l[i] += x;
    else ++x, res += l[i - 1] + 1;
  }

  for (int i = n, x = 0; i >= 1; i--) {
    r[i] = r[i + 1];
    if (s[i] == '0') r[i] += x;
    else ++x;
  }

  for (int i = 1; i <= n; i++)
    if (s[i] == '1') res += l[i - 1] * r[i + 1];
  return res;
}

int solve2() {
  for (int i = 1; i <= n; i++) {
    f[i][0] = f[i - 1][0];
    f[i][1] = f[i - 1][1];
    if (s[i] == '0') f[i][0] += f[i - 1][1];
    else f[i][1] += f[i - 1][0] + 1;
  }
  return f[n][1];
}

int main() {
  cin >> n;
  if (n > 50) { printf("0 1\n"); return 0; }
  scanf("%s", s + 1);
  int ans1 = solve1();
  int ans2 = solve2();
  printf("%d %d\n", ans1, ans2);
  return 0;
}

判断题

21. 输入 7 1001101 时，程序输出为 15 15。（ ） {{ select(21) }}

• 正确
• 错误

22. 任意合法输入下，solve1() 的返回值总不超过 solve2() 的返回值。（ ） {{ select(22) }}

• 正确
• 错误

23.（2 分）当 n=10 时存在至少一种输入，使得 solve1() 的返回值不小于 50。（ ） {{ select(23) }}

• 正确
• 错误

选择题

24.（2 分）若程序输出的两个数不同，则 n 的最小值为（ ）。 {{ select(24) }}

• A. 6
• B. 7
• C. 8
• D. 51

25. 当 n=10 时，有（ ）种合法输入使程序输出的两个数字相同。 {{ select(25) }}

• A. 648
• B. 720
• C. 848
• D. 1024

26.（4 分）当程序输出的两个数相差为 128 时，输入可能是（ ）。 {{ select(26) }}

• A. 14 11001011010011
• B. 14 10101000010101
• C. 14 10111000011101
• D. 14 11001100110011

---

（3）第 18 题（14 分）

#include <bits/stdc++.h>
using namespace std;

int n, m, dp[1<<20];
int ty, a[20];
int pc[1<<20];

int main() {
  cin >> n >> m;
  cin >> ty;
  if (ty == 1) {
    for (int i = 0; i < n; i++) a[i] = i;
  } else {
    for (int i = 0; i < n; i++) cin >> a[i];
  }

  dp[0] = 1;

  for (int i = 0; i < (1<<20); i++) {
    for (int t = 0; t < 20; t++) {
      if (i & (1<<t)) ++pc[i];
    }
  }

  for (int i = 0; i < (1<<n); i++) {
    for (int j = i; j; j = (j-1) & i) {
      int x = 0;
      for (int t = 0; t < n; t++) {
        if (j & (1<<t)) x ^= a[t];
      }
      if (pc[x] == m) dp[i] |= dp[i - j];
    }
  }

  if (dp[(1<<n)-1]) printf("Yes\n");
  else printf("No\n");
  return 0;
}

判断题

27. 当输入的 ty=1 时，将第 21 行的 t<20 改为 t<5，输出不变。（ ） {{ select(27) }}

• 正确
• 错误

28. 输入 5 2 1 时，程序输出 Yes。（ ） {{ select(28) }}

• 正确
• 错误

29.（2 分）当 n=16, ty=1 且 0≤m≤4 时，程序总会输出 Yes。（ ） {{ select(29) }}

• 正确
• 错误

选择题

30.（2 分）当前三个数字满足 n=4, m=1, ty=2 时，程序还需输入 4 个数。输入（ ）会使输出为 No。 {{ select(30) }}

• A. 2 4 16 256
• B. 5 6 7 8
• C. 17 21 5 7
• D. 3 7 12 48

31. 下列说法正确的是（ ）。 {{ select(31) }}

• A. n 为偶数、m=1, ty=1 时输出 Yes
• B. n 为奇数、m=1, ty=1 时输出 Yes
• C. n 为偶数、m=0, ty=1 时输出 Yes
• D. n 为奇数、m=0, ty=1 时输出 Yes

32.（4 分）该程序的时间复杂度为（ ）。 {{ select(32) }}

• A. $O(n)$
• B. $O(n \cdot 2^n)$
• C. $O(n \cdot 3^n)$
• D. $O(n \cdot 4^n)$

---

三、完善程序（单选题，每小题 3 分，共 30 分）

3.1 Genshin（15 分）

#include <bits/stdc++.h>
using namespace std;
struct odt_node {
  int l, r;
  mutable char val;
  odt_node(int a=0,int b=0,char c=0):l(a),r(b),val(c){}
  bool operator<(const odt_node& t)const{
    return (/* Blank 1 */);
  }
};
int n, q, pre = 1;
char c1, c2;
struct odt : (/* Blank 2 */) {
  auto split(int p){
    auto it = (/* Blank 3 */)(p);
    if (it != end() && it->l == p) return it;
    auto t = *--it;
    erase(it);
    emplace(t.l, p-1, t.val);
    return emplace(p, t.r, t.val).first;
  }
  auto assign(int l,int r,char k){
    erase(split(l), split(r+1));
    return emplace(l,r,k).first;
  }
  bool query(int l,int r){
    auto ir = split(r+1), il = split(l);
    if (l != 1 && r != n && prev(il)->val == ir->val) return false;
    for (auto it = il; it != ir; ++it)
      if (il->val != it->val)
        return assign(il->l, (/* Blank 4 */), il->val), false;
    return assign(l, r, il->val), true;
  }
} s;

signed main(){
  cin >> n >> c2;
  for (int i=2;i<=n;i++){
    cin >> c1;
    if (c1 != c2) s.emplace(pre, i-1, c2), pre = i;
    c2 = c1;
  }
  (/* Blank 5 */);
  s.emplace(n+1, n+1, 'D');
  cin >> q;
  for (int l, r; q--; ){
    char op, k; cin >> op;
    if (op == 'A') cin >> l >> r >> k, s.assign(l,r,k);
    else cin >> l >> r, cout << (s.query(l,r) ? "Yes\n" : "No\n");
  }
  return 0;
}

33. /* Blank 1 */ 应填（ ）。 {{ select(33) }}

• A. l < t.l
• B. t.l < l
• C. r < t.l
• D. t.r < r

34. /* Blank 2 */ 应填（ ）。 {{ select(34) }}

• A. vector<odt_node>
• B. list<odt_node>
• C. set<odt_node>
• D. map<odt_node>

35. /* Blank 3 */ 应填（ ）。 {{ select(35) }}

• A. lower_bound
• B. upper_bound
• C. find
• D. count

36. /* Blank 4 */ 应填（ ）。 {{ select(36) }}

• A. (--it)->r
• B. (it--)->r
• C. (++it)->r
• D. (it++)->r

37. /* Blank 5 */ 应填（ ）。 {{ select(37) }}

• A. s.emplace(1, n, c1)
• B. s.emplace(1, n, c2)
• C. s.emplace(pre, n, c1)
• D. s.emplace(pre, n, c2)

---

3.2 Impact（15 分）

#include <bits/stdc++.h>
#define siz(x) int((x).size())
using namespace std;

template <typename T1, typename T2>
T1 &cmin(T1 &x, T2 &&y){ if (y < x) x = y; return x; }
template <typename T1, typename T2>
T1 &cmax(T1 &x, T2 &&y){ if (x < y) x = y; return x; }

int n, ans, B;
string s;

void solve(const string &a, const string &b){
  int f[siz(a)+1][siz(b)+1]; memset(f,0,sizeof f);
  for (int i=1;i<=siz(a);i++)
    for (int j=1;j<=siz(b);j++){
      f[i][j] = max(f[i-1][j], f[i][j-1]);
      if (a[i-1] == b[j-1]) cmax(f[i][j], f[i-1][j-1]+1);
    }
  cmax(ans, 2 * f[siz(a)][siz(b)]);
}

void solve(const string &a, const string &b, const string &c){
  int f[siz(a)+1][siz(b)+1][siz(c)+1]; memset(f,0,sizeof f);
  for (int i=1;i<=siz(a);i++)
    for (int j=1;j<=siz(b);j++)
      for (int k=1;k<=siz(c);k++){
        f[i][j][k] = max({f[i-1][j][k], f[i][j-1][k], f[i][j][k-1]});
        if (/* Blank 1 */) cmax(f[i][j][k], f[i-1][j-1][k-1]+1);
      }
  cmax(ans, 3 * f[siz(a)][siz(b)][siz(c)]);
}

signed main(){
  cin >> s; n = siz(s);
  B = (/* Blank 2 */);

  for (int i=1;i<n;i++) solve({&s[0], &s[i]}, {&s[i], &s[n]});
  for (int i=1;i<n;i++)
    for (int j=i+1;j<n;j++)
      solve({&s[0], &s[i]}, {&s[i], &s[j]}, {&s[j], &s[n]});

  for (int l=0;l<n;l+=B){
    int r = min(n-1, l+B-1), m = r-l+1;
    for (int k=1;k<(/* Blank 3 */);k++){
      string t; int L = n, R = 0, res = 1;
      for (int i=0;i<m;i++)
        if (k>>i & 1) t += (/* Blank 4 */), cmin(L, l+i), cmax(R, l+i);
      int p = 0;
      for (int i=0;i<L;i++)
        if (t[p] == s[i]) res += (/* Blank 5 */);
      p = 0;
      for (int i=R+1;i<n;i++)
        if (t[p] == s[i]) res += (/* Blank 5 */);
      if (res > 1) cmax(ans, res * siz(t));
    }
  }
  cout << ans;
  return 0;
}

38. /* Blank 1 */ 应填（ ）。 {{ select(38) }}

• A. a[i-1]==b[j-1]
• B. a[i-1]!=b[j-1]
• C. a[i-1]==b[j-1] && b[j-1]==c[k-1]
• D. a[i-1]==b[j-1] || b[j-1]==c[k-1]

39. /* Blank 2 */ 应填（ ）。 {{ select(39) }}

• A. 4
• B. 8
• C. 16
• D. 32

40. /* Blank 3 */ 应填（ ）。 {{ select(40) }}

• A. (1<<(m-1)) - 1
• B. (1<<(m-1))
• C. (1<<m) - 1
• D. (1<<m)

41. /* Blank 4 */ 应填（ ）。 {{ select(41) }}

• A. s[l-i]
• B. s[l+i]
• C. s[r-i]
• D. s[r+i]

42. /* Blank 5 */ 应填（ ）。 {{ select(42) }}

• A. !((++p)%=siz(t))
• B. !((p++)%=siz(t))
• C. !!((++p)%=siz(t))
• D. !!((p++)%=siz(t))