试吃活动（eat）

首先，我们可以先想一想当 $n=2$ 时，若小组内两头奶牛都喜欢同种类型的干草则有解；当 $n=3$时，则当组内有任意两头奶牛喜欢同种类型的干草时有解。

然后很容易即可推出，若奶牛 $i-1$ 和奶牛 $i$ 或奶牛 $i$ 和奶牛 $i-2$ 喜欢同类型的干草，那么奶牛 $i-$ 2 ，奶牛 $i-1$ 和奶牛 $i$ 将可以同时喜欢奶牛 $i$ 所喜欢的干草类型。

而对于任何奶牛数大于 3 的焦点访谈小组，我们一定能从中找到一个有 3 头奶牛的焦点访谈小组。若有干草类型满足上面推导的关系，则这种类型的干草将可以受到所有奶牛的喜爱。

工作任务（work）

题目应该很好理解，从 $1 \leq N, M \leq 200000$ 可以知道要用 $O(n)$ 或者 $O\left(n \log _2 n\right)$ 的算法。 首先我想到的是贪心，每次从两叠书的顶部选用时最少的一本书来读，直到时间用完为止。 但这个贪心是错的，可以被下面的数据 hack。

2 2 4
3 1
2 3

因为优先选用时少的书不一定最优，可能像上面的数据一样，用时多的书下面放了很多用时少的书，而程序不会去取那本用时多的书，所以最后答案不会是最优的。 因为读书只能连续的读，不能跳过一本书直接去读下一本书，设第一叠书读到第 $x$ 本，第二叠书读到第 $y$ 本，所以问题就是满足 $\left(\sum_{i=1}^x a_i\right)+\left(\sum_{i=1}^y b_i\right) \leq k$ 的最大的 $x+y$ ，就是 $a$ 数组的前缀和和 $b$ 数组的前缀和，设 $a$ 数组的前缀和为 $s u m a, b$ 数组的前缀和为 $s u m b$ ，所以问题就变成了求满足 $s u m a_x+s u m b_y \leq k$ 的最大的 $x+y$ ，这个问题可以用双指针解决，代码实现有些细节见代码注释。

学习计划（study）

令 $d_i(x)$ 表示第 $i$ 个植物经过 $t$ 天后的高度，有：

$$d_i(x)=h_i+t \times a_i$$

根据 $t$ 的定义，若用 $p_i$ 表示 FJ 希望长到第 $i$ 高的植物，易得，对于 $1 \leq x \leq n$ ：

$$p_{t_x+1}=x$$

那么，若最少经过 $k$ 天后满足 FJ 的要求，显然有 $d_{p_1}(k)>d_{p_2}(k)>\cdots>d_{p_n}(k)$ ，即：

$$\left\{\begin{array}{l} d_{p_1}(k)>d_{p_2}(k) \\ d_{p_2}(k)>d_{p_3}(k) \\ \cdots \\ d_{p_{n-1}}(k)>d_{p_n}(k) \end{array}\right.$$

分开来说，对于排名相邻的两个植物 $x=p_i$ 和 $y=p_{i+1}$ ，有 $d_x(k)>d_y(k)$ ，即 $h_x+k \times a_x>$ $h_y+k \times a_y$ ，化简得：

$$\left(a_x-a_y\right) k>h_y-h_x$$

分类讨论 $a_x-a_y$ 的正负：

• 当 $a_x-a_y>0$ ，即 $a_x>a_y$ 时，有 $k>\frac{h_y-h_x}{a_x-a_y}$ ；
• 当 $a_x-a_y<0$ ，即 $a_x<a_y$ 时，有 $k<\frac{h_y-h_x}{a_x-a_y}$ ；
• 当 $a_x-a_y=0$ ，即 $a_x=a_y$ 时，有 $0>h_y-h_x$ ，即 $h_x>h_y$ ：
• 若 $h_x>h_y, k \in \mathbb{R}$ ；
• 反之，若 $h_x \leq h_y$ ，无解。

此时我们得到了 $n-1$ 个不等式。其中，有 $l_1$ 个不等式 $k$ 大于某值，$l_2$ 个不等式 $k$ 小于某值，$l_3$ 个结果 $k \in \mathbb{R}$ ，以及 $l_4$ 个无解。

若 $l_4>0$ ，显然无解，输出 -1 。由于 $k \in \mathbb{R}$ ，可以忽略所有 $l_3$ 个结果。接下来考虑剩余的 $l_1$ 个 $k>q 1_i$ 和 $l_2$ 个 $k<q 2_i$ 。那么，根据初中课本中的「同大取大，同小取小」，易得 $k>\max \left(q 1_i\right)$及 $k<\min \left(q 2_i\right)$ 。合并，得：

$$\max \left(q 1_i\right)<k<\min \left(q 2_i\right)$$

• 若 $\max \left(q 1_i\right)<\min \left(q 2_i\right)$ ，且区间 $\left(\max \left(q 1_i\right), \min \left(q 2_i\right)\right)$ 中至少含有 1 个正整数，则 $k=$ $\left\lfloor\max \left(q 1_i\right)\right\rfloor+1$ ；

• 反之，则无解。

  时间复杂度 $O(T \cdot n)$ 。

魔法井字棋（magic）

首先我们发现，可以使用一个 $3^9$ 大小的数字储存下一个井字棋状态。由于 $3^9 \leq 2 * 10^5$ ，所以我们可以考虑 $O\left(3^9 N^2\right)$ 的方法。

考虑进行深度优先搜索。使用 bool hav $[N][N][3 * * 9]$ 记录下这个状态是否出现过（位置和井字棋的状态），防止重复搜索。如果没有被搜索过，首先判断这个位置上要不要填入棋子，需要的话改变状态。然后判断这个状态是否胜利，是的话记录并且退出。最后想四个方向进行搜索即可。

对于可行状态，可以直接转换成 $3 * 3$ 的数组，然后暴力判断。建议先预处理出所有状态的可行性。

邮票收集（stamp）

我们设 $m=26$ ，则若直接暴力枚举，则复杂度为 $\Theta\left(m^k\right)$ ，根本无法接受。 考虑dp。 我们设 $f_{i, j}\left(1 \leq i \leq 26,1 \leq j \leq \min \left(k, \sum_{s=1}^{26} c_s\right)\right)$ 为在前 $i$ 组字母中选出 $j$ 个字母组成字符串的方案数对 998244353 取模的结果，他可以由 $f_{i-1, l}\left(\max \left(0, j-c_i\right) \leq l \leq j\right)$转移而来，但是是如何转移的呢？ 我们的这个长度为 $j$ 的字符串 $s$ 的第 $x$ 位 $(1 \leq x \leq j)$ 可以分配给前 $i-1$ 组字母其中的一组，也可以分配给第 $i$ 组，由于必须分配给前 $i-1$ 组字母 $l$ 位，则分配的方式有 $\binom{j}{l}$种，由于前 $i-1$ 组字母还可以有 $f_{i-1, l}$ 种排列，那么我们就得到了状态转移方程：

$$f_{i, j}=\sum_{l=j-c_i}^j f_{i-1, l} \times\binom{ j}{l}$$

我们可以先预处理 $\binom{i}{j}(0 \leq i \leq k, 0 \leq j \leq i)$ ：

$$\binom{i}{j}=\binom{i-1}{j}+\binom{i-1}{j-1}$$

再进行 dp。 由于 $f_{i, j}$ 只与 $f_{i-1, l}$ 有关，所以我们可以将第一维压掉。 总体复杂度为 $\Theta\left(m k^2\right), m k^2 \leq 2.6 \times 10^7$ ，可以接受。

音符序列（seq）

一道比较简单好想的数据结构。

我们不妨先分析 $T$ 串的性质，由题意得 $T$ 的字母是递增的，那意味着我询问的子串也应该递增的。

但是子串递增并不意味着他是 $T$ 的子串，因为排序后可能会有其他的字母插入进来。举个例子：

$$\begin{aligned} S=\tt{aaaaaabbbbddyyyyzzzffbaaaz}\\ T=\tt{aaaaaaaaabbbbbddffyyyyzzzz} \end{aligned}$$

假设我们现在查询 $\tt{aabbbbddyy}$ 这个子串是否是 $T$ 的一个子串。

我们不难发现将 $S$ 串排序后发生了以下几个事情：

1. $\tt a$ 和 $\tt z$ 被归位了，看上去并不影响我们的查询。
2. $\tt b$ 被塞了一个进去。
3. $\tt f$ 被塞了两个进去，但是我们原本的子串并没有 $\tt f$。

所以经过简单的分析，我们得到如下结论：

1. 在 $S_l+1$ 到 $S_r-1$ 的所有字母中，其在子串中的出现次数应当等于全串的出现次数。
2. 跟 $S_l$ 和 $S_r$ 相同的字母不影响查询。
3. 区间要递增。

看上去“区间递增”是最好做的，不妨想一下如何用数据结构维护。

• 如果 $S_i\geqslant S_{i-1}$，那么我们令 $a_i:=1$，否则 $a_i:=-1$。

那么一个区间 $[l,r]$ 递增的条件可以转化为 $\sum\limits_{l+1}^r a_i=r-l$。开一个线段树维护即可，每次询问都要检查如上条件，修改时考虑新的字符与其前后的关系，要更改两处线段树的值。

“出现次数”这个条件就十分简单了，不难发现值域只有 $26$，可以考虑开 $26$ 个线段树或者树状数组（我知道大家懒得写所以还是写树状数组吧）。每一个树状数组维护一个值，如果串中 $S_i=p$，那么 $tr_{p,i}=1$，累加起来即可得到出现次数。