2026中大综评机试简记

andychen_2012 · 2026-07-17 18:27:14 · 学习·文化课

string:

给一个长为 n 的仅由小写字符构成的字符串 s，它由以下操作得来：

• 一开始有一个字符串数组，如 \set{abb,bc,ab}
• 将这个字符串数组按以下方法排序后拼接：
  • 稳定排序：按照每个字符串的第一个字符严格单调递增排序，如果两个字符串的第一个字符相同，那么它们在数组中的先后顺序保持不变；如上面的数组变为 \set{abb,ab,bc}
  • 拼接：将排序后的字符串按顺序首尾相接；如上面的数组得到 abbabbc

求有多少个起始字符串数组经过操作后得到 s

number:

给定 n,m 和大小为 n 的正整数集合 U=\set{a_1,a_2,...,a_n}，保证集合元素互不相同。

求有理数 t 的最小值，使得 U 中所有大小为 m 的子集 S 中都存在两个数 x,y \in S,x \neq y 使得 \frac{1}{t} \le \frac{x}{y} \le t

形式化即为：\forall S \subseteq U,|S|=m,\exists x,y \in S,x \neq y,\frac{1}{t} \le \frac{x}{y} \le t

注意精度问题

gcd:

给定非负整数 x,y

定义 f(n)=n+x+\gcd(n,y)

给定长度为 m 的序列 a_1,a_2,...a_m

对于其每个前缀 a_1,a_2,...,a_i，你可以对里面任意多个数进行任意多次 f 操作，求操作完后，a_1,a_2,...,a_i 中有几个不同的数字。

多组数据，\sum m \le 10^5,0 \le x \le 10^9,1 \le y \le 10^6,1 \le a_i \le 10^{18}

fish:

共有 n-1 次随机决斗，每次决斗从当前存活的鱼中随机选取2个，记它们的重量分别为 a,b：

胜者的重量变为 a+b，败者死亡。

对于每个标号 i=1,2,...,n，求最后活着的鱼标号为 i 的概率

复合树 tree:

定义复合树如下：

有两棵树 T_1,T_2，记 |T_1|=n,|T_2|=m

这样构造出来的 T_3 满足 |T_3|=n \times m

定义一棵树 T 对应的函数 f(T) 为 T 的最大独立集点数

以下为正式题面：

有 n 棵树，第 i 棵树记为 T_i，|T_i|=i，构造如下：

给定 p_1,p_2,...,p_m，且 p_i \in [1,n]

定义 w(l,r) 如下：设 S_l=T_{p_l}，\forall l+1 \le i \le r,S_i=S_{i-1} \oplus T_{p_i}，w(l,r)=f(S_r)

多组数据，\sum n \le 5 \times 10^5,\sum m,\sum q \le 10^5

My solution:

string:

考虑将最后得到的串分为一些段，显然这些段的首字母必须要是单调不降的。

设 f_{r,k,c} 为以位置 r 结尾，分割了 k 段，最后一段的首字母为 c 的方案数，则有转移方程

对最后一维做一个前缀和优化，转移就变为

时间复杂度为 O(n^4)，不过实际上跑得挺快，因为 [s_{l+1}=c] 的条件可以剪掉很多复杂度

（现在才发现考场的时候脑子不太好，如果直接枚举 r,l,k 的话，还可以再压缩一下时间）

number:

考虑二分答案

有两种方案存储：long double，分数结构体

最后交的是第二种

具体的check(x)函数是说，对于每个 i 二分找到第一个使得 a[r] > a[i] \times x 的位置 r，然后 len[i]=len[r]+1，如果存在一个 len_i >= m，那就说明这个 x 不可行，否则 x 可行

最后将二分出来较小的那个值 l 带进去，就可以得到一些恰好大小为 m 的集合，对每个集合内部求相邻两数之比（大比小）的最小值，然后取这些最小值的最大值，即为答案。

时间复杂度 O(n \log^2 n)

后面三个题不太会，全暴力和部分分

gcd和fish看上去有原题的感觉，gcd有atcoder的风格，fish就是ICPC/CCPC的感觉

tree很显然是出题人发疯了