题解
「CF86C」Genetic engineering-AC自动机+dp
· ✏️ 727 words · ☕ 2 mins read

我们定义一个 DNA 序列为仅有 ATCG 四个字母的字符串。

给出 $m(1 \le m \le 10)$ 个 DNA 序列模式串 $s_i$,每个长度均不超过 $10$ ,我们定义一个 DNA 序列 $w$ 是好的,当且仅当对于 $w$ 的每一个位置 $i$ ,都存在至少一个模式串 $s_j$ , 使得 $w[l…r] = s_j$( $w[l…r]$ 表示一个原字符串的一个子串) , 其中 $1 \le l \le i \le r \le |w|$( $|w|$ 为 DNA序列 $w$ 的长度) 。

请你计算出所有长度为 $n(1 \le n \le 1000)$ 的好的 DNA 序列的个数。


「CF83D」Numbers-容斥原理
· ✏️ 791 words · ☕ 2 mins read

给出三个整数 $l,r,k (1 \le l \leq r \le 2\cdot10^9, 2 \le k \le 2 \cdot 10^9)$ 。

求在区间 $[l,r]$ 内满足 $k \mid i$ , 且对于任意 $j \in [2,k-1]$ 都不满足 $k \mid i$ 的数 $i$ 的个数。


「CF540E」Infinite Inversions-动态开点线段树
· ✏️ 886 words · ☕ 2 mins read

现在有一个由所有正整数组成的无限递增序列: $p = {1,2,3,…}$ 。

对这个序列执行 $n$ 次交换操作。每次一个操作,给出两个整数 $a,b$,交换位置 $a$ 和 $b$ 处的元素。

你的任务是在所有操作结束后,输出最终序列的逆序对个数,即满足 $i < j$ 且 $p_i > p_j$ 的有序数对 $(i,j)$ 的数量。


「CF486E」LIS of Sequence-简单数据结构
· ✏️ 1047 words · ☕ 3 mins read

给你一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ ,你需要把这 $n$ 个元素分成三类:$1,2,3$,每类的条件如下:

  1. 所有的最长上升子序列都不包含这个元素

  2. 有但非所有的最长上升子序列包含这个元素

  3. 所有的最长上升子序列都包含这个元素


「CF452E」Three strings-后缀数组
· ✏️ 719 words · ☕ 2 mins read

给出三个仅由小写字母构成的串 $A, B, C$ ,对于每个 $L \in [1, \min(len_A,len_B,len_C)]$ ,求满足$A[a,a+L-1] = B[b,b+L-1] = C[c,c+L-1]$ 的三元组 $(a,b,c)$ 的数量。

答案对 $1000000007 (10 ^ 9 + 7)$ 取模,字符总数小于 $3 \times 10^5$。


「CF400E」Inna and Binary Logic-简单数据结构
· ✏️ 651 words · ☕ 2 mins read

Inna 有一个一个长度为 $n$ 的数列 $a_1 [1],a_1 [2],\dots,a_1 [n]$。

她会进行如下操作,分为 $n$ 个阶段:
在第一阶段,Inna 从数组 $a_1$中写出所有数字,在第 $i$ 个 $(i \ge 2)$ 阶段 Inna 会写出数组的所有元素 $a_i$ ,由 $n - i + 1$ 个整数组成; 数组 $a_i$ 的第 $k$ 个数定义如下:$a _ {i} [k] = a _ {i-1} [k]\ \mathrm{AND}\ a _ {i-1} [k + 1]$ 。 这里 $\mathrm{AND}$ 是二进制的逐位与运算。

Dima 决定检验 Inna 的技能。 他要求 Inna 改变阵列,进行练习并说出她在当前练习中写出的所有元素的总和,即:

$$
\sum _ {i=1}^n \sum _ {j=1}^{n-i+1} a_i[j]
$$

请帮助 Inna 回答问题!


「CF379F」New Year Tree-树的直径-倍增
· ✏️ 938 words · ☕ 2 mins read

你是一个程序猿,现在有一棵新年树(并不是传统的带着叶子的树)——它有四个节点: $1$ ,$2$ ,$3$ ,$4$ . 其中$2$ ,$3$ ,$4$ 的父亲都是 $1$ .

新年里,程序猿们往往会做一些有趣的事情。你则选择以往这棵树上加节点来取乐。 一个添加节点的操作是这样的:

  1. 找到树上的一个叶子结点 $v$ .
  2. 设现在树上有 $n$ 个节点,那么你现在会加入两个节点$n+1$ 和 $n+2$ ,它们都会成为 $v$ 的儿子.

你的任务是在做 $q$ 次这样的操作,并在每做完一次后计算一次树的直径。来吧,我们一起来解决这道新年问题吧!


「CF369E」Valera and Queries-线段树
· ✏️ 675 words · ☕ 2 mins read

有 $n$ 条线段,分别为 $[l_i,r_i]$ 。

有 $m$ 个询问,分别为 $cnt_i,p_1,p_2,…,p _ {cnt_i}$ 。

对于每个询问,输出有多少线段至少覆盖这 $cnt_i$ ​个点中的一个。($\sum cnt_i \le 3 \cdot 10^5$)


「CF311B」Cats Transport-斜率优化dp
· ✏️ 832 words · ☕ 2 mins read

Zxr960115 是一个大农场主。他养了 $m$ 只可爱的猫子,雇佣了 $p$ 个铲屎官。这里有一条又直又长的道路穿过了农场,有 $n$ 个山丘坐落在道路周围,编号自左往右从1到n。山丘 $i$ 与山丘 $i-1$ 的距离是 $d_i$ 米。铲屎官们住在 $1$ 号山丘。

一天,猫子们外出玩耍。猫子 $i$ 去山丘 $h_i$ 游玩,在 $t_i$ 时间结束他的游玩,然后在山丘 $h_i$ 傻等铲屎官。铲屎官们必须把所有的猫子带上。每个铲屎官都会从 $1$ 走到 $n$ 号山丘,可以不花费时间的把所有路途上游玩结束的猫子带上。每个铲屎官的速度为一米每单位时间,并且足够强壮来带上任意数量的猫子。

你的任务是安排每个铲屎官出发的时间,最小化猫子们等待的时间之和。


「CF256E」Lucky Arrays-简单线段树
· ✏️ 770 words · ☕ 2 mins read

给定一个长度为 $n(1 \le n \le 77777)$ 的数列 $a$ ,初始的时候全为 0。

给出一个 $3 \times 3$ 的矩阵 $w _ {i,j}$ ,$w _ {i,j} = 1$ 时代表 $(i,j)$ 这个有序数对为和谐的数对,否则 $(i,j)$ 不为一个和谐数对。

一个数列 $a$ 是和谐的当且仅当对于所有的 $1\le i \le n-1$ , $(a_i,a _ {i+1})$ 均为和谐数对。

有 $m(1\le m \le 77777)$ 次修改和询问,每次给出两个整数 $v_i,t_i$,将 $a _ {v_i} (1 \le v_i \le n)$ 修改为 $t_i(0\le t_i \le 3)$。

每次修改后都询问,如果将数列里所有的 $0$ 都替换为任意 $1$ 到 $3$ 之间的整数(不同位置的 $0$ 可以替换为不同的数),那么最后产生的和谐的数列有多少种。每次修改后的查询并不会使数列发生任何改变。

答案对 $777777777$ 取模。


「CF212D」Cutting a Fence-简单数据结构
· ✏️ 784 words · ☕ 2 mins read

给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$,定义 $f(x,k) = \min _ {i=0}^{k-1} (a _ {x+i})$ ,请对于每一个 $k = 1$ 到 $n$ ,求出 $\sum _ {i=1}^{n-k+1} f(i,k)$ 的值。


「CF160E」Buses and People-线段树
· ✏️ 1043 words · ☕ 3 mins read

Bertown 大街可以抽象为一条数轴。在数轴上有 $10^9$ 个巴士站。站点按照它们在数轴上的顺序从 $1$ 到 $10^9$ 的整数编号。这个城市有 $n$ 辆公共汽车。每天第 $i$ 个公共汽车从 $s_i$ 位置出发,到 $f_i$ 位置停止( $s_i < f_i$ ),它在所有位于 $s_i$ 与 $f_i$ 的中间站点停靠并且仅在晚上返回。公共汽车在时间 $t_i$ 开始行驶,并且它也在时间 $t_i$ 完成行驶(行驶、停靠都是瞬间的)。所有公共汽车的开始时间 $t_i$ 都不同。公交车有无限的容量。

Bertown 有很多居民。今天第 $i$ 个人要从 $l_i$ 位置出发到 $r_i$ 位置结束( $l_i < r_i$ );第 $i$ 个人在时间 $b_i$ 进入他的出发位置( $l_i$ )。一方面,每个人都希望尽快到达目的地,另一方面,他不想换乘公交车。

也就是:为第 $i$ 个人挑选的公交汽车 $j$ ,满足 $s_j \leq l_i$, $r_i \leq f_j$ 和 $b_i \leq t_j$ 的条件下,$t_j$ 最小。

你的任务是确定每个人今天是否可以到达目的地,如果可以,找到每个人将乘坐的公交车的号码,不可以则输出 $-1$ 。


「CF115E」Linear Kingdom Races-dp+线段树优化
· ✏️ 882 words · ☕ 2 mins read

你是一个赛车比赛的组织者,想在线性王国中安排一些比赛。

线性王国有 $n$ 条连续的从左到右的道路。道路从左到右依次编号为从 $1$ 到 $n$ ,因此道路按照升序排列。在这些道路上可能会有几场比赛,每一场比赛都将使用这些道路的某个连续的子序列。而且,如果某场比赛举行了,你将获得一定数额的金钱。没有比赛在时间上重叠,所以每一段道路可以在多个比赛中使用。

不幸的是,所有道路的状况都不佳,需要修理。每条路都有与之相关的维修费用,你需要支付这笔费用来修理道路。只有在某场比赛中需要使用的所有道路都进行了修复,才能进行比赛。你的任务是修复道路并使你的利润最大化。你的利润被定义为你从比赛中获得的总金额减去你花在修理道路上的钱。请注意,您可以决定不修任何道路,并获得利润 $0$ 。

输出你能获得的最大利润。


「CF91E」Igloo Skyscraper-分块
· ✏️ 1032 words · ☕ 3 mins read

有 $n$ 个海象(编号为 $1$ 到 $n$ )参加比赛建造自己的摩天大楼 。在 $t=0$ 时,第 $i$ 个海象的摩天大楼的高度为 $a_i$ 。每一时刻,编号为 $i$ 的海象会完成 $b_i$ 层楼的建造。

在奥运会现场报道的记者向活动组织者提出了 $q$ 次询问。每次询问给出三个数字 $l_i$ ,$r_i$ ,$t_i$。活动组织者用数字 $x$ 回答每个查询,$x$ 满足:

  1. 数字 $x$ 位于从 $l_i$ 到 $r_i$ 的区间,即 $l_i \leq x \leq r_i$ 。

  2. 编号为 $x$ 的海象的摩天大楼在 $t_i$ 时刻拥有编号在 $[l_i,r_i]$ 中所有海象的摩天大楼中的最大高度。

对于每位记者的查询,输出符合上述标准的海象的编号 $x$ 。如果有多个可能的答案,请输出其中任何一个。