Codeforces
「CF750E」New Year and Old Subsequence-矩阵+线段树+dp
· ✏️ 1156 words · ☕ 3 mins read

定义一个数字串为“妙”的当且仅当:该串包含某一子序列为 $2017$ ,且不包含子序列 $2016$。

定义一个数字串的“丑值”为:该串至少删去几个字符,可以使得剩余串变“妙”;如果删去任意多个字符,均无法使该串变“妙”,则该串的“丑值”是 $-1$。

给定一个长度为 $n$ 的数字串 $s$ 。有 $q$ 次询问,每次询问用 $(l_i,r_i)$ 表示。对于每次询问,回答子串 $s[l_i…r_i]$ 的“丑值”。


「CF875E」Delivery Club-二分+贪心
· ✏️ 681 words · ☕ 2 mins read

有两个快递员,分别在 $s_1, s_2(0\le s_1,s_2\le 10^9)$ 位置。现在有 $n(1\le n\le 100000)$ 个任务,需要依次完成,每个任务用一个整数 $x_i$ 表示要将货物送到 $x_i$ 位置,让任何一个快递员到 $x_i$ 都可以。

由于快递员之间需要有对讲机联系,请你设计一种方案使得两个快递员之间的最长距离最短。


「CF353E」 Antichain-乱搞
· ✏️ 650 words · ☕ 2 mins read

给定一个长度为 $n$ 的 $01$ 序列,第 $i$ 位是 $0$ 代表 节点 $i$ 到节点 $i \bmod n + 1$ 有一条有向边,第 $i$ 位是 $1$ 代表 节点 $i \bmod n + 1$ 到节点 i 有一条有向边。

我们称一个节点对 $(u,v)$ 是妙的当且仅当不存在 $u$ 到 $v$ 和 $v$ 到 $u$ 的路径任何两者之一。

现在你要从这个图里面挑出一个集合,使得集合中任意两个不同的节点 $u$ 和 $v$ 之间构成的节点对 $(u,v)$ 都是妙的。

请你输出这个集合的大小的最大值。


「CF581F」 Zublicanes and Mumocrates - 树形dp
· ✏️ 581 words · ☕ 2 mins read

一棵树上有 $n$ 个节点,把每个节点染成黑色或白色,要求叶子节点一半是黑色,一半是白色(保证叶子节点的个数是偶数)。

求在满足要求的情况下,最小的两端颜色不同的边的数量。


「CF542D」Superhero's Job - dp + 数论
· ✏️ 625 words · ☕ 2 mins read

我们定义
$$
J(x) = \sum_{d | x} [\gcd(x,\frac{x}{d}) = 1] d
$$

请你求出 $J(x) = A$ 有多少个 $x$ 满足条件。


「CF804D」Expected diameter of a tree-树的直径+乱搞
· ✏️ 1004 words · ☕ 3 mins read

给定一个含有 $n$ 个点, $m$ 条边的森林。有 $q$ 个询问,每次给出两个点 $u_i,v_i$ ,如果 $u_i$ 在联通块 $A$ 内,$v_i$ 在联通块 $B$ 内,我们随机选择两个点 $a \in A,b \in B$ ,我们在 $(a,b)$ 之间连一条边,如果这个连接成后新联通块不构成一个树,输出 $-1$ ,否则输出新联通块树的直径的期望。所有边权均为 $1$ 。


「CF543C」Remembering Strings-状态压缩dp
· ✏️ 652 words · ☕ 2 mins read

给定 $n$ 个长度均为 $m$ 的字符串,再给出一个 $n$ 行 $m$ 列的矩阵 ${a_{nm}}$。
矩阵元素 $a_{ij}$ 代表把第 $i$ 个字符串第 $j$ 个字符改成其它任意字符所需要的代价。

现在要求对于任意一个字符串,总存在某一位置 $j$ 使得该位置上的字符在任意其他字符串该位置的字符不同。

即为对于第 x 个字符串 ,有 $\exists j \in [1,m] , \forall i \in [1,n],s_{xj} \neq s_{ij}$ 。

求把所有字符串修改成满足上述要求的字符串的最小代价是多少?

数据范围: $1 \le n,m \le 20,1\le a_{ij} \le 10^6$ 。


「CF321E」Ciel and Gondolas-wqs二分+决策单调性
· ✏️ 733 words · ☕ 2 mins read

Ciel 狐狸在游乐园里排队等待上摩天轮。现在有 $n$ 个人按编号顺次在队列里,有 $m$ 条船,第 $i$ 条船到时,前 $q_{i}$ 个人可以上船。保证 $\sum q_i = n$。 人总是不愿意和陌生人上同一条船的,当第 $i$ 个人与第 $j$ 个人处于同一条船上时,会产生 $u_{i,j}$ 的沮丧值。请你求出最小的沮丧值和。一条船上的人两两都会产生沮丧值,不会计算这个沮丧值两次。


「CF877F」Ann and Books-莫队
· ✏️ 628 words · ☕ 2 mins read

有 $n$ 本书,第 $i$ 本书中有 $a_i$ 个问题,均属于第 $t_i$ 类问题。

有 $q$ 次询问,每次询问给出一个区间 $[l_i,r_i]$ ,询问有多少个原序列的连续子区间是给出区间的子区间,且该子区间中所有书中问题的和满足第 $1$ 类的问题恰好比第 $2$ 类的问题恰好多 $k$ 个。


「CF476E」Dreamoon and Strings-动态规划
· ✏️ 774 words · ☕ 2 mins read

Dreamoon 有一个字符串 $s$ 和一个模式串 $p$ ,他会先从 $s$ 中删除恰好 $x$ 个字符来产生一个新的字符串 $s'$ 。然后他会计算 $occ(s’,p)$,即从 $s'$ 中能找到的等于 pp 的不相交的子串数量的最大值。他想让 $occ(s’,p)$ 的值尽可能大。

更形式地说,让我们用 $ans(x)$ 表示所有可以从 $s$ 中删去恰好 $x$ 个字符得到的 $s'$ 中 $occ(s’,p)$ 的最大值。Dreamoon 想要知道对于所有的 $x$ $(0 \leq x \leq |s|)$, $ans(x)$ 的值。


「CF232D」Fence-后缀数组+主席树
· ✏️ 973 words · ☕ 2 mins read

给定长度为 $n$ 的整数序列 $h[n]$ ,有 $Q$ 个询问,每次给出 $l_1,r_1$ ,​询问有多少对 $l_2,r_2$ ,满足以下条件:

  1. $r_2 – l_2 = r_1 – l_1$
  2. 区间 $[l_1, r_1]$ 与区间 $[l_2, r_2]$ 没有交集
  3. 对于任意 $i \in [0,r_1 – l_1]$ ,满足 $h[l_1 + i] + h[l_2 + i] = h[l_1] + h[l_2]$

「CF103E」Buying Sets-霍尔定理-网络流-最小权闭合子图
· ✏️ 975 words · ☕ 2 mins read

我们有 $n$ 个集合,第 $i$ 个集合有 $m_i$ 个数($1$ 到 $n$ 中的整数),权值为 $w_i$ 。

现在请你从中选出 $k$ ($k$ 为任意 $0$ 到 $n$ 中的整数)个集合,满足这 $k$ 个集合的并集的大小为 $k$ ,询问这 $k$ 个集合的权值和最小值。

保证从这 $n$ 选出任意 $x$ 个集合,他们的并集大小不小于 $k$ 。


「CF813D」Two Melodies-简单dp
· ✏️ 648 words · ☕ 2 mins read

给定一个长度为 $n$ 的数组,我们要从中找出两个不相交(不含邮相同元素的)的子序列,要求每个子序列的任意两个相邻元素的差的绝对值为 $1$ 或 在模 $7$ 意义下相同。请你求出这两个子序列长度和的最大值。


「CF68D」Half-decay tree-期望瞎搞题
· ✏️ 805 words · ☕ 2 mins read

定义一个完全二叉树树高为根节点到叶子节点经过的边数。

给定一个树高为 $h(1 \le h \le 30)$ 的完全二叉树,其中第 $x$ 个节点的左儿子为第 $2x$ 个节点,右儿子为第 $2x+1$ 个节点。

现在有 $q(1 \le q \le 10^{5})$ 个,分为两种操作:

  1. add v e ( $1 \le v \le 2^{h+1}-1,1 \le e \le 10^4$ )表示给第 $v$ 个节点的权值加 $e$ 。
  2. decay 操作。我们在这个二叉树里面以等概率选择一个叶子节点,将这个叶子节点到根的路径上所有的边都删去。在删除后,树会形成若干个联通块,我们定义某个联通块的的权值为这个联通块内所有节点的权值之和。我们定义删除后的树的权值为形成的所有联通块的权值的最大值。请你求出这个值的期望。每次删除后会恢复所有删除的边。

「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 序列的个数。