首页 > 极客资料 博客日记

CCF CSP-S 2024 提高组初赛解析

2024-09-26 10:30:03极客资料围观19

这篇文章介绍了CCF CSP-S 2024 提高组初赛解析,分享给大家做个参考,收藏极客之家收获更多编程知识

Certified Software Professional - Senior 非专业级软件能力认证测试

本解析不提供阅读程序与完善程序题目的代码,如有需要请通过 luogu.com.cn 相关链接 下载

如有谬误烦请指正

答案

AACBB
BDABD
ACBCD
✓××BC
✓✓✓BCC
✓×✓CAC
AAAAA
AABAA

单项选择

1

在 Linux 系统中,如果你想显示当前工作目录的路径,应该使用哪个命令?

A pwd
B cd
C ls
D echo

pwd : print working directory
cd : 跳转到指定目录
ls : 列出当前目录的所有子文件和子文件夹
echo : 输出指定内容

2

假设一个长度为n的整数数组中每个元索值互不相同,且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少?

A \(O(n)\)
B \(O(logn)\)
C \(O(nlogn)\)
D \(O(1)\)

无序的数组只能通过两两比较来查找,需要比较 \(n-1\) 次(第一次不需要比较),因此为 \(O(n)\)

3

在 C++中,以下哪个函数调用会造成溢出?

A int foo(){ return 0;}
B int bar(){int x=1;return x; }
C void baz(){ int a[1000];baz();)
D void qux(){ return; }

函数栈溢出一般有两种:函数内变量开的太大,或者函数递归深度太深

这里 baz() 函数重复调用自身,无终止条件,因此会溢出

4

在一场比赛中,有 \(10\) 名选手参加,前三名将获得金、银、牌。若不允许并列,且每名选手只能获得一枚奖牌,则不同的颁奖方式有多少种?

A 120
B 720
C 504
D 1000

不妨选出一个长度为 \(3\) 的序列,依次获得金,银,铜牌,则方案有 \(A^{3}_{10}=10\times 9\times 8=720\)

5

下面哪个数据结构最适合实现先进先出(FIFO)的功能?

A 栈
B 队列
C 线性表
D 二叉搜索树

栈是先进后出

后面两种数据结构不具备存放与弹出基本数据的功能

线性表在功能上类似数组

6

已知 \(f(1)=1\),且对于 \(n\ge2\)\(f(n)=f(n-1)+f(⌊n/2⌋)\) ,则 \(f(4)\) 的值为:

A \(4\)
B \(5\)
C \(6\)
D \(7\)

\(f(2)=f(1)+f(1)=2\)

\(f(3)=f(2)+f(1)=3\)

\(f(4)=f(3)+f(2)=5\)

7

假设有一个包含 \(n\) 个顶点的无向图,且该图是欧拉图。以下关于该图的描述中哪一项不一定正确?

A 所有顶点的度数均为偶数
B 该图连通
C 该图存在一个欧拉回路
D 该图的边数是奇数

欧拉图定义:仅由欧拉回路构成的图

欧拉回路:即一笔能画完的图。形式化地说,欧拉回路是从任意一个点出发,不重复经过任何一条边,也不遗漏任何一条边,最终仍能回到该节点的路径

根据定义,D 是错误的,反例为一个正方形

8

对数组进行二分查找的过程中,以下哪个条件必须满足?

A 数组必须是有序的
B 数组必须是无序的
C 数组长度必须是 \(2\) 的幂
D 数组中的元素必须为整数

二分查找本质上也是一种二分答案,需要保证答案具有单调性

9

考虑一个自然数 \(n\) 以及一个数 \(m\),你需要计算 \(n\) 的逆元(即 \(n\)\(m\) 意义下的乘法逆元),下列哪种算法最为适合?

A 使用暴力法依次尝试
B 使用扩展欧几里得算法
C 使用快速幂法
D 使用线性筛法

逆元的定义是这样的:

定义 \(a\) 在模 \(p\) 意义下的逆元 \(b\) 满足 \((\frac{c}{a})\mod p=(c\times b)\mod p\)

\(p\) 为质数的时候,才能使用快速幂(+费马小定理)来求逆元,而扩展欧几里得算法为更加通用的求逆元方法,只需要满足两个数互质

更详细的求逆元方法可以通过 这篇文章 的 5.3.1 章了解

10

在设计一个哈希表时,为了减少冲突,需要使用适当的哈希函效和冲突解决策略。已知某哈希表中有 \(n\) 个键值对,表的装载因子为 \(a(0<a\le 1)\) 。在使用开放地址法解决冲突的过程中,最坏情况下查找一个元素的时间复杂度为

A \(O(1)\)
B \(O(logn)\)
C \(O(1/(1-a))\)
D \(O(n)\)

开放地址法解决冲突:假设当前元素 \(x\) 需要放入地址 \(p\) 中,但现在 \(p\) 位置已经有了元素,直接放置就会导致冲突,因此考虑向后依次找,找到第一个没有放置元素的位置放置,这样可以防止冲突(遍历到最后再从头开始)

因此最坏情况下需要把整个表遍历一遍,复杂度为 \(O(n)\)

科普装载因子的定义:装载因子定义了一个阈值,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行扩容、rehash操作(即重建内部数据结构),扩容后的哈希表将具有两倍的原容量。

11

假设有一棵 \(h\) 层的完全二叉树,该树最多包含多少个结点?

A \(2^h-1\)
B \(2^{h+1}-1\)
C \(2^h\)
D \(2^{h+1}\)

因为每个节点都有两个儿子,因此每一层的节点个数都是上一层的两倍

总结点数为 \(1+2^{1}+2^{2}+\cdots+2^{h-1}=2^{h}-1\)

12

设有一个 \(10\) 个顶点的完全图,每两个顶点之间都有一条边。有多少个长度为 \(4\) 的环?

A \(120\)
B \(210\)
C \(630\)
D \(5040\)

因为图完全联通,任取四个点一定能保证它们构成一个环

因为环上的点是无序的,因此很多人会考虑计算 \(C^{4}_{10}=\frac{10\times 9\times 8\times 7}{4\times 3\times 2\times 1}=210\),然而这样是错误的

考虑是什么地方出了问题

刚才我们说,任取四个点一定能保证它们构成一个环

但是环 1 2 3 4 和环 2 1 3 4 并不是同一个环,前者有 1->2->3 的连边,后者有 2->1->3 的连边,显然不是同一个环

正确的做法是考虑重复的环:

注意到 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 是重复的,以此类推,每一种可能的组合都有四种可能的起始节点,因此会重复计算 \(4\)

另外,注意到 1 2 3 4 4 3 2 1 是重复的,同样,上面的每一种反过来和原来都是一样的,因此答案为 \(\frac{A^{4}_{10}}{2\times 4}=630\)

13

对于一个整数 \(n\)。定义 \(f(n)\)\(n\) 的各位数字之和。问使 \(f(f(x))=10\) 的最小自然数 \(x\) 是多少?

A \(29\)
B \(199\)
C \(299\)
D \(399\)

代选项即可

\(f(29)=11,f(f(29))=2\)

\(f(199)=19,f(f(199))=10\)

\(f(299)=20,f(f(299))=2\)

\(f(399)=21,f(f(399))=3\)

14

设有一个长度为 \(n\) 的 01 字符串,其中有 \(k\)\(1\) ,每次操作可以交换相邻两个字符。在最坏情况下将这 \(k\)\(1\) 移到字符串最右边所要的交换次数是多少?

A \(k\)
B \(\frac{k\times (k-1)}{2}\)
C \((n-k)\times k\)
D \(\frac{(2n-k-1)\times k}{2}\)

D 这个数的来源:令全部数字都排在最左边,然后从右到左一个一个挪,然后认为答案是 \((n-1)+(n-2)+(n-3)\cdots+(n-k)\)

实际上,在排后面的数字时,由于右边已经有排好的数字,不需要将新来的数字与排好的数字进行比较与交换了,所以每个数字的交换次数只有 \((n-k)\) 次,一共 \(k(n-k)\)

15

如图是一张包含 \(7\) 个顶点的有向图,如果要除其中一些边,使得从节点 \(1\) 到节点 \(7\) 没有可行路径,且删除的边数最少,请问总共有多少种可行的删除边的集合?

A \(1\)
B \(2\)
C \(3\)
D \(4\)

一个可能更丑的图

上来先注意到 \(\{8,9\}\) 是合法的,并且不存在只删一个边的解法,因此最优解为 \(2\)

可行的边的集合

\(\{8,9\}\)
\(\{5,6\}\)
\(\{6,8\}\)
\(\{1,6\}\)

阅读程序

1

分析

logic() 函数内的位运算,采用枚举法来判断

  1. \(x=0,y=0\) 时,(0 & 0) ^ ((0 ^ 0) | (~0 & 0))=0 ^ (0 | 0)=0
  2. \(x=0,y=1\) 时,(0 & 1) ^ ((0 ^ 1) | (~0 & 1))=0 ^ (1 | 1)=1
  3. \(x=1,y=0\) 时,(1 & 0) ^ ((1 ^ 0) | (~1 & 0))=0 ^ (1 | 0)=1
  4. \(x=1,y=1\) 时,(1 & 1) ^ ((1 ^ 1) | (~1 & 1))=1 ^ (0 | 0)=1

因此为逻辑或运算

观察到 recursion() 函数非常像快速排序算法,但是有最大递归深度限制,最多只会进行 depth 层递归,因此 这个排序算法的结果不一定有序

因为快速排序最多只会进行 \(\log n\) 层,因此当 \(d\ge \log b\) 时,输出的序列是有序的

题目

  • \(1000\ge d\ge b\) 时,输出的序列是有序的

\(d\ge b\ge \log b\),正确

  • 当输入 5 5 1 时,输出为 1 1 5 5 5

通过暴力模拟可以发现,初始数组为 5 5 1 1 5,排序函数只进行了一层,排序不完全,输出值为 5 1 1 5 5

  • 假设数组 c 长度无限制,该程序所实现的算法的时间复杂度是 \(O(b)\)

该排序算法在每一层都花费 \(O(b)\) 遍历了一遍数组,然而该算法共有 \(d\) 层,因此复杂度为 \(O(bd)\)

  • 函数 int logic(int x,int y) 的功能是

按位或,详见上方解析

  • 当输入为 10 100 100 时,输出的第 \(100\) 个数为

\(d\ge \log b\),可知输出数组是有序的,也即让我们求一个最大的数

尝试代选项,判断哪个数可以通过 \(0\)\(99\) 内的数 \(i\) 通过 (a|i)%(b+1) 得到,可以发现 \(98\) 不合法(不存在 \(a\) 中为 \(1\) 的二进制位),而 \(95\) 合法,因此为 \(95\)

详细地说,二进制意义下 a=1010,而 98=1100010,显然,如果一个数为 a|i 的形式,那么第四位一定是 \(1\),类似地,98+101=11000111 同样不合法(需要考虑这个是因为 (98+101)%101=98),因此 \(98\) 不合法

2

分析

观察 solve() 函数的 dp 部分

发现 int k = (j<<1)|(s[i]-'0') 这一句,其实就相当于是在 \(j\) 的后面再拼一个数字,然后用拼接前的数字去更新拼接后的数字,因为拼接上的数字都是 s[i] 中的内容,i 为正序遍历,初态为 \(0\),那么我们发现,该 dp 数组一直在尝试将 s 中新的字符拼接到已有的字符后面,并且这样的拼接是有序的,只能将后面的字符拼接到前面的字符后面,综合这三个条件我们可以总结出:这个 dp 数组是在统计 s 的子序列方案数

但是这个方案数是有限制的,下面我们对这些限制来进行一些描述

  1. 注意到只有在 \([0,2^{m-1}-1]\) 内的数字才能用于对答案进行更新,对应到二进制就是所有不大于 \(m\) 位的二进制数,因此,s 中大于 \(m\) 位的子序列是不会被统计到的
  2. 此外的一个限制条件是 if(j !=0 || s[i]=='1'),这是这个函数区别于 solve2() 的最大不同点,这意味着当一个子序列开头是 \(0\) 的时候,由于 j=0,k=0,因此无法进行更新,也就是说 这个函数要求子序列的开头必须是 \(1\)

随后函数统计了所有 i*dp[i] 的值,值*方案数=总和

根据以上条件,我们可以总结出该函数的功能:找出 s 全部以 \(1\) 开头的,不超过 \(m\) 位的子序列的十进制值总和

下面来看 solve2(),它则枚举了全部 \([0,2^{n}-1]\) 的全部情况,转为二进制即为全部不超过 \(n\) 位的二进制数,随后,如果二进制位为 \(1\),就把该位上的 s 拼接到已有的字符后面(num = num * 2 + (s[j]-'0') 一句),可以发现 solve2() 同样是在找子序列的值,那么我们来说一下 solve2() 的限制

  1. 注意到,虽然我们枚举了所有可能的情况,但只有 cnt<=m 的数才能对答案进行更新,也就是说最终子序列中最多只能拼接 \(m\) 个数

也就是说这个函数的功能为:找出 s 全部不超过 \(m\) 位的子序列的十进制值总和

可以发现,两者的差距就在是否以 \(1\) 开头

题目

  • 假设数组 dp 长度无限制,函数 solve() 所实现的算法的时间复杂度是 \(O(n2^{m})\)

solve() 函数的核心算法与复杂度瓶颈为两层 for 循环,根据 solve() 函数的 for 循环边界,可以得出其复杂度为 \(T(n2^{m-1})\),即 \(O(n2^{m})\)(相当于乘以一个常数 \(2\)

  • 输入 11 2 10000000001 时,程序输出两个数 3223

对于 solve2()

\(m=1\) 时:11 个数,贡献为 \(2\times 1+9\times 0=2\)

\(m=2\) 时:10\(9\) 种,01\(9\) 种,11\(1\) 种,贡献为 \(2\times 9+1\times 9+3=30\)

总贡献 \(2+30=32\)

对于 solve()

\(m=1\) 时:11 个数,贡献为 \(2\times 1+9\times 0=2\)

\(m=2\) 时:10\(9\) 种,01\(0\) 种(不合法),11\(1\) 种,贡献为 \(2\times 9+1\times 0+3=21\)

总贡献 \(2+21=23\)

故正确,这道题最大的坑点就是实际输出的时候 solve2() 在前

  • \(n\le 10\) 时,solve() 的返回值始终小于 \(4^{10}\)

可以发现其子序列贡献最多为 \(\sum^{10}_{i=1}C^{i}_{10}\times (2^{i}-1)\) 个(这里的做法不是本题所需要的,如果你想知道为什么是这个式子,可以去下面 "当 \(n\le 6\) 时,solve() 的最大可能返回值为" 那道题去找)

但是考场上显然我们不好算这么大的数,因为我们找出的所有子序列都小于 \(1111111111\),而我们一共有 \(2^{10}\) 个数,而每个数都不会超过 \(2^{10}\),因此一定小于 \(2^{10}\times 2^{10}=2^{20}=4^{10}\),因此正确,这也是出题人把这个数设成 \(4^{10}\) 的意图

  • \(n=10\)\(m=10\) 时,有多少种输入使得两行的结果完全一致

根据刚才的分析,不能存在任何以 \(0\) 开头,且有值的子序列,也就是说,只要序列中出现了 \(0\),必须保证后面的数都没有值,即都是 \(0\)

不难发现 00000000001000000000110000000011100000001111000000111110000011111100001111111000111111110011111111101111111111 都符合要求,共 \(11\)

  • \(n\le 6\) 时,solve() 的最大可能返回值为

考虑极限情况,即 \(111111\),且 \(m\ge n\),此时每一位对答案都会有最大贡献,即答案也最大,那么,位数为 \(1\) 的子序列共有 \(C^{1}_{6}\) 个,而因为每一位都为 \(1\),因此每一个的值都为 \(1\),同理,位数为 \(2\) 的子序列共有 \(C^{2}_{6}\) 个,每一个的值都为 \(3\),以此类推,可以发现其子序列贡献最多为 \(\sum^{6}_{i=1}C^{i}_{6}\times (2^{i}-1)=665\)

  • \(n=8,m=8\),solve 和 solve2 的返回值最大可能的差值为

和上面那个结果完全一致的题正好反过来了,这道题里我们需要一个以 \(0\) 开头的子序列值最大的序列,那么容易想到的是这个序列开头一定是 \(0\),为了使后面的值最大,我们构造出 01111111 这样的序列作为答案

题目让我们计算的差值,实际上也就是以 \(0\) 开头的子序列权值和,去掉开头的 \(0\),也就相当于求 \(n=7,m=7\)1111111 的子序列权值和,又回到刚才那个问题,答案为 \(\sum^{7}_{i=1}C^{i}_{7}\times (2^{i}-1)=2059\)

3

分析

首先来看 \(p\) 数组,可以发现其用于埃氏筛(init() 函数内局部代码),最后筛出来,\(p_{i}=1\) 则表示 \(i\) 为素数

然后观察变量 const P1,P2,B1,B2,K1,K2

其中 P1,P2 用于取模,而后面这两组变量,一组用于给 H 赋初值,另一组用来生成 p1,p2 数组(在主函数中),发现其格式类似 线性同余,判断作用为生成随机数,也就是说,p1,p2,H 三种变量的起始值均是随机的,推测是哈希算法

对于这个哈希结构体 H,我们可以观察出如下这几点:

  • H 定义的加法不满足交换律
  • H 中有两个哈希参数 h1,h2,另外一个参数 l 记录合并的次数,同时也参与运算

下方的选择题问我们,H 的合并方式看起来像什么,后面列出的选项全都是树上操作,据此推测该算法是树哈希,一个节点的初值由该节点编号是否为质数来决定,一个节点最终的哈希值由其初值,左子树值,右子树值共同决定,当两个节点对应的子树(这里指子树结构和子树上节点的 p 数组状态)完全相同时,这两个节点的哈希值就相等

随后程序进行了排序与去重,这并不在树哈希的算法范围内,用处在下方题目中会有体现

题目

  • 假设程序运行前能自动将 maxn 改为 n+1,所实现的算法的时间复杂度是 \(O(n\log n)\)

总复杂度为筛法+排序+去重= \(T(n\log\log n+n\log n+n)=O(n\log n)\)

  • 时间复杂度的瓶颈在 init()

init(): \(T(n+n\log\log n)\)

solve(): \(T(2n+n\log n)\)

显然 solve() 更大

  • 若修改常数 B1K1 的值,该程序可能会输出不同的结果

程序第一行输出的是哈希值,尽管修改哈希内部的参数并不影响哈希判等(不考虑哈希冲突),但仍然会导致哈希值改变,因此正确

  • 在 solve() 函数中,h[] 的合并顺序可以看做是

\(2i\) 是左子树,\(i\) 是当前,\(2i+1\) 是右子树,则 h[i]=h[2*i]+h[i]+h[2*i+1] 表示 左-中-右,即中序遍历

  • 输入 \(10\),输出的第一行是

暴力模拟哈希值即可通过本题

但是显然有更好的解法,考虑到这个哈希值在扩展的时候,每次都是乘 \(2^{l}\),再加上一个新的哈希值,这是一个非常好的性质,假如我们把某一位的哈希值看做一个 \(m\) 位的二进制数,这样的合并方式就会告诉我们,这个二进制数对应的 \(l\) 一定等于 \(m\),因为初态时,对于 \(l=1\) 的节点,值恰好就是 \(1\),因此每次合并的时候,都会正好将左右两边的 \(h1\) 值拼接起来,形成一个新的二进制数

因此我们可以直接利用这个性质,对 \(n=10\) 的完全二叉树的中序遍历 8 4 9 2 10 5 1 6 3 7 转成二进制数(该位编号是质数就为 \(1\),否则为 \(0\),详见 H 的构造函数),即 \(0001010011_{d}=83\)

  • 输入 16,输出的第二行是

即问:\(n=16\) 时,子树哈希值不同的节点共有几个(哈希值不同在上方已有定义,即子树结构或者子树上节点的 p 数组状态存在不同)

可以发现 9 10 12 14 15 16 是相同的,11 13 是相同的,其余都是不同的

因此为 \(16-(6-1)-(2-1)=10\)

完善程序

1

分析

upper_bound() 函数是有其固定作用的,含义为 “查找有序序列中第一个大于给定元素的值的下标”,根据下面调用 upper_bound(b,b+n,...) 也可以发现,这里的区间是左闭右开的

get_rank() 函数相当于二分答案里的 check() 函数,这里的作用是检查当前和在所有 sum 里的排名。这里使用了一种写法为 upper_bound(b,b+n,sum-a[i])-b,假设我们固定 \(a_{i}\),那么在 \(b\) 数组里,比 \(sum-a_{i}\) 小的元素值,与 \(a_{i}\) 的和也一定比 \(sum\) 小,因此我们就将它加到当前 \(sum\) 的排名前,这是这段函数的含义

solve() 即为二分答案函数,二分可能的 \(sum\) 值,找出排名恰好为 \(k\) 的那个

程序相对比较简单,主要的难点可能在二分的格式上,如果你平常用的二分不是 l=mid+1,r=mid 格式,那么可能就容易选错

题目

  • 选二分区间右端点,二分范围是给定数组,不少人会错选 an-a-1,然而因为是左闭右开的,因此应该选 an-a

  • 现在我们要找的是第一个大于 \(a_{i}\) 的数字,注意到 r=mid 应该说明两点,首先说明当前点是合法的(否则应该直接调到 \(mid-1\)),其次说明当前值大了,合法说明严格大于查找值,因此选 a[mid] > ai

  • 返回查找元素的地址,这里查到了第 \(l\) 个元素,因为地址从 \(a+0\) 开始,因此返回 \(a+l\)

  • 仍然选二分区间右端点,由于二分的是 \(sum\) 的值,最大值应该是两边最大的元素相加,由于两边元素都单调不减,所以选最后两个即可,注意最后的元素是 \([n-1]\) 不是 \([n]\)

  • 同第二问,我们来分析,首先当前答案是不合法的,其次当前答案的排名应该较小,因此需要将 \(sum\) 的值变大,不合法说明不能取等,因此选 get_rank(mid) < k

2

分析

严格次短路算法,即找出严格大于最短路的第二短路,首先来分析次短路算法的逻辑:

  • 跑最短路,分别记录当前最短路与次短路
  • 如果当前没有任何路径,那么新找到的路径成为最短路
  • 如果新找到的路径比当前最短路短,那么新找到的成为最短路,之前的最短路成为次短路
  • 如果新找到的路径小于最短路但大于次短路,那么新找到的路径成为次短路

这样,我们就能够找到最短路和次短路

题目中要求输出路径,因此推测 pre 数组是记录路径的数组,dis 数组按照一般最短路算法,记录的是节点到起点的最短路,这里比较奇怪的是两个指针 pre2dis2,它们是属于次短路的数组,你可以理解成它们也是独立的数组,只不过用的是 predis 的空间

也就是说,dis[a]=(dis+n)[a-n]=dis2[a-n]dis2[a]=(dis+n)[a]=dis[a+n]

然后来看加边,用的是链式前向星,加边函数是 add

下面分析这个 upd 函数

写过 dij 算法的应该能看出来,这是一个松弛操作,因为其中有对 dis 的比较,赋值和优先队列的 push(),并且能看出来,松弛成功之后函数会返回 true,否则为 false,函数的参数中,a 是节点的前驱编号,b 是节点编号,d 是更新的距离,p 是一个优先队列

在 solve() 函数里跑的就是一个比较正常的 dij

题目

  • 这里的目的是用当前最短路的 dis 去更新次短路的 dis,因为这两个 dis 分在两个不同的数组里,所以可能会不相同,但只有两个数组相同才能进行松弛操作,所以需要统一一下,那么这里的前驱显然是 pre[b],节点编号应该是 n+b,因为我们要更新的是 dis2[b],因为 dis2=dis+n,所以这里应该为 n+b,距离是最短路距离 dis[b]
  • 考的是 pair<> 的关键字问题,pair<> 在排序的时候会优先以第一关键字排序,相同时以第二关键字排序,那么这里我们显然应该优先排节点 dis 而不是节点编号,所以应该是 d 在前,然后应该是 dis 小的在前,因为优先队列把大的放在前面,所以为了实现小的在前面,我们应该插入一个负的,取出来的时候再把它变成正的就行了
  • 不少人直接会无脑选 0x3f,因为这个数好记,不会炸 int,并且够大,但是这个题已经为我们定义了最大值 const int inf,所以我们直接照着 inf 值选 0x1f
  • 这个地方是已经松弛过最短路了,并且失败了,现在要来尝试松弛次短路,和上面第二题一样,次短路编号为 n+b,因为我们还没更新 dis2,所以这里不能用 dis2[a]+c,只能用 dis[a]+c
  • 上面的判断语句告诉我们现在 an 大(并且一定比 2n 小),所以我们直接调 dis2[a] 会越界(但是在这里调用 dis[a] 就是可以的),为了不让其越界,我们应该调用 dis2[a-n],即 dis2[a%n]

版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!

标签:

相关文章

本站推荐

标签云