【11.14】Codeforces 刷题

$\text{DP}$ ：

---

B. Two Strings

题意：

考虑 $s$ 的所有与 $t$ 相同的子序列，询问是否 $s$ 中每一个字母都属于这样的一个子序列中。长度 $n,m\le 2\cdot 10^5$ 。

思路：计算 $s$ 每个字符 $s_i$ ，预处理以该字符为起始 / 结束的最长匹配子序列长度。

AC代码：https://codeforces.com/contest/223/submission/180593963

---

D. Two out of Three

题意：

一队顾客排在一位收银员前面。他采取这样一个策略：每次，假如队伍有至少两人，就会从前面的前三人（如果有）中选取两位一起收银，所花费的时间为这两人单独收银所需时间的最大值。如果只有两人，那么一起收银；如果只有一人，那么单独收银。请问所需的总时间最少是多少？

$1\le n\le 1000,1\le a_i\le 10^6$

题解：CF82D Two out of Three 题解

思路：容易知道，收银 $i$ 次之后，对于前 $2\cdot i+1$ 个人，一定会剩下一个人。我们就以剩下这个人为标准进行集合分类。

定义 $dp(i,j)$ 表示收银 $i$ 次且剩下的这个人编号为 $j$ 的最少时间。转移方程：

设 $x=2\cdot i,y=2\cdot i+1$
$dp(i,j\in [1,2\cdot i-1])=dp(i-1,j)+\max (a_x,a_y)$
d p ( i , x ) = max ⁡ { d p ( i − 1 , j ∈ [ 1 , 2 ⋅ i − 1 ] ) + max ⁡ ( a i , a y ) } dp(i,x)=\max \{dp(i-1,j\in[1,2\cdot i-1])+\max(a_i,a_y) \} dp(i,x)=max{dp(i−1,j∈[1,2⋅i−1])+max(ai​,ay​)}
d p ( i , y ) = max ⁡ { d p ( i − 1 , j ∈ [ 1 , 2 ⋅ i − 1 ] ) + max ⁡ ( a i , a x ) } dp(i,y)=\max \{dp(i-1,j\in[1,2\cdot i-1])+\max(a_i,a_x) \} dp(i,y)=max{dp(i−1,j∈[1,2⋅i−1])+max(ai​,ax​)}

AC代码：https://codeforces.com/contest/82/submission/180949721

---

构造 ${}^{\ast }1700{\sim }^{\ast }2000$ ：

---

D. Walk on Matrix

题意：

有这么一个问题：

有一个 $n\times m$ 的矩阵 $a_{n,m}$，矩阵的每个位置都有一个数，要求寻找一个每次只能向右或向下走的从 $(1,1)$ 至 $(n,m)$ 的路径，最大化路径上的数的按位与之和。

$1\le n,m\le 500$，$0\le a_{i,j}\le 3\times 10^5$。

现在给出解决该问题的一个错误 dp 算法（见题面图片），请构造一组数据，hack 掉这个算法，使得正确答案比错误的输出恰好大 $k$。

$0\le k\le 10^5$。

题解：CF1332D Walk on Matrix 题解

思路：写这一题，需要想出来如何合理构造路径，骗过这个错误的算法。

AC代码：https://codeforces.com/contest/1332/submission/180949691

---

D. Task On The Board

题意：

给定一个字符串s，保证字符串内的字符在"a"到"z"范围内

然后给一定一个整数 m 和一个长度为 m 的序列 b

要求从s中取出 m 个字符构成一个新的字符串a（不可重复取相同位置的字符），任意排列后，是其满足对于每一个 i 都有 a[i] 到 a 中 所有比它大的（即字典序比它大，如 b > a,z > x ）的字符在字符串 a 中的距离之和为 b[i]

要求输出满足条件的字符串 a

思路：主要思路是，从字典序最大的向最小的填，填的位置可以一个一个推出来。

AC代码：https://codeforces.com/contest/1367/submission/180962175

---

E. Maximum Subsequence Value

题意：

给出一个长度为 $n(1\le n\le 500)$ 的数列 $a(1\le a_i\le 10^{18})$，你需要选出一个子序列，使其价值最大，输出最大的价值。

对于一个长度为 $k$ 的子序列，若在这个子序列中有不少于 $\max (1,k-2)$ 个数的二进制位 $i$ 上是 $1$，则其价值增加 $2^i$。

思路：诈骗题。不少于 $\max (1,k-1)$ 在这一进制位上为 $1$ ，意味着最多有两个 $0$ 。我们如果有一个序列，删除一个数，如果这一位上是 $1$ ，那么不影响 $0$ 的个数；如果是 $0$ ，那么更有可能对答案有贡献。因此删数后答案一定不会更劣，枚举 $k=3$ 的序列。

AC代码：https://codeforces.com/contest/1365/submission/181052652

---

B. Orac and Medians

题意：

询问$a_1,a_2,\cdots a_n$能否通过若干次将任意区间全部赋值为其中位数这个操作，来使得整个序列全部变为$k$。（中位数指第$\lfloor \frac{\mid s\mid +1}{2}\rfloor$小的数）
多次询问，每次第一行两个整数，$n$和$k$；第二行$n$个整数，$a_1,a_2,\cdots a_n$。
数据范围:$1\le n\le 10^5,1\le k\le 10^9,1\le a_i\le 10^9$，并保证所有询问中$n$的和不超过$10^5$。

思路：这是一道推理题，需要思考出一些性质，从这些性质解决问题。详见 题解 。

AC代码：https://codeforces.com/contest/1349/submission/180956072