主播想要练习一下，故花了两个小时模拟了一下23级的C7赛

特意买了个学校机房同款包浆古董慢回弹键盘

A 选择题

第1题

KMP算法的提出者是哪几位___。

• A. D.E.Knuth
• B. J.H.Morris
• C. V.R.Pratt
• D. htunK.E.D
• E. sirroM.H.J
• F. ttarP.R.V

阅读全文

发现发题解能加平时分，之前都没有交过，最后一次赶紧水两道题，防止我的期末挂挂~

C 前缀数组

题目

题目描述

在植物理想国中有很多种类的仙人掌（Cactus），例如「可爱仙人掌」（Cutetus），「拐弯抹角仙人掌」（Pointless Cactus）。

下面将给出 $n$ （$1 \le n \le 1000$）个名字（一个名字由若干个单词组成，单词是指由空格分割的字符串），Yuki 想知道其中哪些名字是仙人掌的名字。

由于 Yuki 对仙人掌并不熟悉，所以只能认为名字中有至少一个单词满足以下至少一个条件的，都是仙人掌：

1. 单词以 cac 开头（不区分大小写）
2. 单词以 tus 结尾（不区分大小写）
3. 单词含有 cactus 作为子串（不区分大小写）

例如，Cattus 是「仙喵掌」，当然是仙人掌，但 Tree Tree 是「好多树」，不是仙人掌。

输入描述

输入包含不定的若干行（不超过 $1000$ 行），每一行一个字符串（仅包含大写字母，小写字母，空格或连字符）表示一个植物的名字。

形式化的来说，大写字母是指 ASCII 码在 $[65, 90]$ 之间的字符（A-Z）；小写字母是指 ASCII 码在 $[97, 122]$ 之间的字符（a-z）；空格是 ASCII 码为 $32$ 的字符（ ）；连字符是 ASCII 码为 $45$ 的字符（-）；单词是指由空格分割的字符串。

输出描述

输出一个正整数，表示有多少个植物是仙人掌。

阅读全文

A Yuki 的连通块

题目描述

Yuki 有一个无向图，这个无向图有 $n$ 个点和 $m$ 条边，Yuki 希望知道这个无向图有多少个不同的连通块？

两个连通块不同，当且仅当两连通块的点集不同。

输入

第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 10^6$），分别表示无向图的点数和边数。
接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示编号为 $u$ 和 $v$ 的点之间有一条无向边。

输出

输出一行，表示该无向图的连通块数量。

输入样例

6 3
1 2
2 3
4 5

输出样例

3

阅读全文

做的跟shit一样，被虐爆了

F wiki数星星

题目背景

wiki正在一条直线上数星星，她想知道，哪里是离星星最近的地方呢？

题目描述

有一个函数 $ f(x) $，初始为常数函数 $ f(x) = 0 $。

接下来 $ Q $ 次操作：

• 更新 1 a b：给定整数 $ a, b $，令 $ g(x) = f(x) + |x - a| + b $，然后把 $ f(x) $ 替换为 $ g(x) $。

  例如：若当前 $ f(x) = 0 $，执行操作更新操作 1 2 1（即 $ a=2, b=1 $），则新的函数为 $ f(x) = |x-2| + 1 $；接着再执行操作 1 3 2（即 $ a=3, b=2 $），新的函数为
  $ f(x) = |x-2| + 1 + |x-3| + 2 $。

• 查询 2：输出使 $ f(x) $ 最小的整数 $ x $ 以及最小值 $ f(x) $。如果有多个使得最小的 $ x $，选择最小的那个整数。

例如：当 $ f(x) = |x - 2| + 1 $ 时，$ x = 2 $ 使得 $ f(x) $ 最小为 1。

已知询问时输出的值总是整数，请以整数格式输出。

阅读全文

A

题目描述

AndroidNeko 听说在计算复杂度的重要性刻进主题，想希望你以样写写一个程序来计算满足特定形式递归式的算法复杂度。

具体来说，给定正整数 $a, b, k$，所求递归式为：

$$ T(n) = aT\left(\frac{n}{b}\right) + O\left(n^k\right) $$

根据主定理，有：

$$ T(n) = \begin{cases} O\left(n^{\log_b a}\right), & \log_b a > k \\ O\left(n^k \log n\right), & \log_b a = k \\ O\left(n^k\right), & \log_b a < k \\ \end{cases} $$

输入格式

第一行一个正整数 $t$ $(1 \leq t \leq 2 \times 10^5)$，表示数据组数。

对于每组数据，一行三个正整数 $a, b, k$ $(1 \leq a, k \leq 10^9,\, 2 \leq b \leq 10^9)$，含义同题目描述。

输出格式

对于每组数据，输出一行：

• 若 $T(n)=O(n^{\log_b a})$，输出 n^{\log_ba}
• 若 $T(n)=O(n^k \log n)$，输出 n^klog n

• 若 $T(n)=O(n^k)$，输出 n^k

阅读全文