做题记录2019.4

结束啦结束啦~~~~

CF1149-B

题意:给你一个长度为$n \leq 1e6$的只包含小写字母的模式串,有 3 个初始长度为 0 的串,有$q \leq 1000$次操作,每次操作可以选择一个串在其尾部增加一个字母或去掉一个字母,回答是否这三个串同时满足是模式串的不重合子序列。每个串的长度不超过 250.

解:一开始光想着贪心选择最靠后的满足条件的字母。但是发现有点问题,只能 dp 了。 dp[i][j][k] 表示第一个串的前 i 个和第二个串的前 j 个和第三个串的前 k 个满足条件的最小模式串长度。由于每次只在最后添加或删除字母,因此只要更新剩下的两维即可,复杂度是 250*250 的。(还是太年轻

同济校赛

H-菜哭武的 01 串

题意:给你一个长度为$n \leq 1e6$的 01 串,问这个串所有子序列可以表示的最大的连续正整数。

解:序列自动机上 bfs 第一个不能表示的正整数,然后减一。需要记忆化,为什么能够记忆化呢?假设当前点 i 是从之前很多状态转移过来的,因为每次转移都是贪心走字典序最小的,所以只要记录第一次访问 i 的状态即可。

到现在已经用序列自动机解决了两种题目了

  • 判断一个串是否是另一个串的子序列
  • 判断一个串中所有子序列可以表示的最大连续正整数
  • 本质不同子序列个数(感觉 dp 一下当前结点出去的子序列个数,然后求个和

Comet OJ - Contest #2

比赛网址

B

解:一个小技巧记录一下,就是在精度要求不高的时候比如 1e-4 这种,可以将数据乘 1e4 之后枚举计算,最后结果再除回去就可以。

D

题意:记$dist(i,j)$为树上 i 到 j 路径上的边数,设$f(S)=max{dist(x,y) | x,y \in S, x \neq y}$,$S$为点集。对每个 i 求满足$f(S) = i$的点集个数。 $n \leq 2000$

解:首先我们注意到$f(S)$实际上是点集的直径。对于一个点集,其中所有的直径的中点是一样的(有可能是边,有可能是点)。那么我们可以通过枚举中点(边)和半径来做。由于边不好枚举,因此我们将一条边的中点拿出来,即(u->v)拆成(u->m->v)。这样只要枚举点即可。因为枚举的是半径,那么要求有至少有两个子树中的点被选到。

E

题意:有 n 个人在睡觉,第 i 个人有$p_i$的概率自己醒来。第 i 个人向第$to_i$个人中出卖了自己的自由,也就是说当第 i 个人没有睡着时,他会有$s_i$的概率去把第$to_i$个人叫醒。求最终每个人醒来的概率。$2 \leq n \leq 10^5$

解:不难发现这是一个基环森林。如果不考虑环的存在,那么每个人醒来的概率简单 dp 即可算出。对于有环的情况,我们先用前面的 dp 把当前的基环树缩成一个环。即环上的每个点醒来的概率都是 dp[i]。那么环上的概率怎么算呢?$ans[i] = dp[i] + (1 - dp[i])(dp[i-1]s[i-1]) + (1-dp[i])(1-dp[i-1])(dp[i-2]s[i-2]s[i-1])…$ 意思是:i 点本身醒着的概率+i 点没醒,i-1 点醒了且叫醒了 i 点的概率 + i 和 i-1 点都没醒,i-2 醒了且叫醒了 i-1,i-1 又叫醒了 i 的概率 + …

需要注意的是:为什么不能用$ans[i-1]$去更新$ans[i]$呢?因为$ans[i-1]$表示 i-1 点最终醒来的概率,它是考虑了$i$的影响的。而计算$i$最终醒来的概率是不能考虑$i$对其它人的影响的。

南昌网络赛

比赛网址

B

题意:

给定$n$个食物,每个食物有个能量$a[i]$。每次查询一个区间$[l,r]$,表示从第$l$个食物开始顺序吃到第$r$个食物得到的能量。
要求:

  • 要吃就全部吃完
  • 当前吃的食物的能量只能比上一次吃的食物的能量低
  • 当前食物能吃就吃,不能吃就跳过(原题意中没有这句话,但是没有这句话会理解错题意,导致这题的难度会上升)

一共有$q$个查询,每次给定$l,r,p,c$,分别表示查询吃$[l,r]$区间能获得的能量,吃完之后修改第$p$个食物的值为$c$。

解:

$f[rt]$表示线段树中当前结点代表的区间的答案,那么它的转移有两种:

  • 如果$rt$结点的最小值在左子树$lson$中取得,那么$f[rt] = f[lson]$
  • 不然的话$f[rt] = f[lson] + x$,$x$表示在右子树$rson$中能够获得的能量

接下来考虑如何计算$x$

设$dfs(x,u)$表示初始值小于$x$,在$u$结点所代表的区间内可获得的能量。

那么上面第二个转移中的转移可以写为$f[rt] = f[lson] + dfs(lson_min, rson)$

接下来考虑$dfs(x,u)$的状态转移。设$lu$为$u$的左子树,$ru$为$u$的右子树。

  • 如果$x \leq lu_min$,那么$dfs(x,u) = dfs(x, ru)$
  • 不然$dfs(x,u) = dfs(x,lu) + f[u] - f[lu]$

这样我更新一个结点的复杂度是$O(\log n)$

接下来是查询:

首先把要查询区间所包含的所有结点找到,按左端点排序,顺序调用上面的$dfs$加一加就可以了。

更新的话就正常线段树单点更新。

D

题意:

给一个长度为$n(\leq 100)$的表达式,只包含数字和加减运算符。每个数字和运算符都是由若干个火柴拼接而成。问在不改变原始表达式的结构(数字的个数,运算符的个数和每个数字的位数)的条件下,通过移动火柴使得新的表达式的值最大。

解:

$dp[i][tot][0/1]$表示到第$i$个位置,还剩下$tot$个火柴,上一个运算符是加或减,所能得到的最大值。转移的状态只有十种,注意一下前导零。

I

题意:

设一个区间的$val$为这个区间的和乘以这个区间的最小值。给定一个 n 个整数的数组,求它所有子区间中最大的$val$。(有负数)

解:

单调栈搞一下每个数最为最小值的范围,然后线段树维护一下前缀和的最值和后缀和的最值。

M

题意:

给一个字符串$S(\leq 100000)$,再给 $n(\leq 100000)$ 个字符串$t_i(\leq 1000)$,判断每个$t_i$是不是$S$的子序列。

解:

卡的有 1 丶丶紧,必须要纯正的$O(nt)$的做法,维护一下$next[i][ch]$从$i$位开始,字符$ch$的下一个出现位置,搞一搞。

原来这就是序列自动机啊(cslnb

2050 大厦 hdu6496

题意:

在二维平面上匡一个矩形,给定若干条斜率为 pi/4 和 3pi/4 的直线,问这些直线组成的矩形有多少个在大矩形框内。

解:

将直线分为两个集合$S_1,S_2$,对$S_1$中的每条直线暴力出与$S_2$中每条直线的交点(在大矩形框内。

从$S_1$中任选两条直线,它们合法交点的交集就是这两条直线对答案的贡献

http://acm.hdu.edu.cn/showproblem.php?pid=6496


codeforce 1155 D

题意:

给一个数组,求其最大的连续子序列和

解:

dp[i][0/1/2]分别表示到第 i 个,还没选/正在选/选完了的状态。
http://codeforces.com/contest/1155/problem/D


gcj qualification D 交互

题意:有 1024 台机器,其中有 15 台坏了,要你猜五次,把这些坏的机器猜出来。每一次猜,可以输入一个只有 0 和 1 的字符串,第 i 位表示发送给第 i 台机器的数字。若机器没坏则它会把原始数据返回给你。

解:如果可以猜十次,那么我可以把[0,1023]遍历一遍。缺少的数字就是坏掉的机器。猜五次的话就要利用只有 15 台坏掉的条件,我们按 16 台一组进行分组,这样不会有一组同时被吞掉。组内枚举[0,15]即可。


夺宝奇兵 秦皇岛 Day1

题意:有 n 个人,m 个宝贝,每个宝贝有个价值 w[i],这 m 个宝贝都在这 n 个人手里。如果想获得某个宝贝,必须从这个人手里花费 w[i]买过来。现在你手上没有宝贝,问至少需要多少钱才可是使得你成为拥有宝物最多(严格大于所有人)的人。

解:

两种策略:

  • 去买那些价值小的宝物
  • 从拥有宝物多的人那里买

显然只考虑一种是不够的,那我们需要同时兼顾这两种策略。

枚举当前人民最多拥有的宝物数,对于那些拥有宝物多的人,要优先购买他们手中价格低的宝物。如果最后拥有的宝物数没有满足条件,则再从所有未购买的宝物中购买价值最低的那些宝物。

用权值线段树去维护宝物的价值。最后均摊复杂度$O(n\log n)$。

树上博弈

题意:在基环树上有若干终点,A 先手,A B 轮流移动,A 不能移动到 B 经过过的点上,当 A 到达若干个终点之一时即可获胜。

解:首先如果存在某个终点到 A 的距离比 B 近,那么 A 一定可以赢。不然 A 只能借助环来赢。那么 A 什么情况会赢呢?首先应该是 B 先到环,然后 B 会懵逼,不知道往哪里走,他会随机挑一个方向走。这时候 A 到环上,只要选择另一条路走,这时候 B 再回头可能就晚了,于是 A 就可以赢了。


ccpc final:Balance of the Force 二分+优先队列 贪心

题意:有 n 个人,每个人可以选择属性值加$l_i$或者$d_i$,有 k 个限制,每个限制是两个人不能选择一样的(比如都选$l_i$)。现在想要所有人中属性值最大的和最小的的差值尽可能小,求出这个差值。

解:每个限制抽象成一条无向边,那么原图就会形成若干个连通分量。对于一个连通分量他会有两种值,因为一个联通分量里,一个人确定,那么整个联通分量的最大和最小值就确定了。现在我们把每个联通分量的两种取值情况都拿出来$(l_1,r_1)和(l_2,r_2)$。然后我们二分答案,答案确定后,我们将所有的 pair 按最大值($r$)排序,知道最大值后减去答案就是最小值。用个优先队列,队列中按最小值($l$)排序。当队列中 pair 的数量大于一半的时候说明当前答案是可以满足的。


2050 热身

赶火车 期望的递归定义

题意:一共有 n+m 条路,n 条路正确,走正确的路则 a[i]分钟后会到达终点。走错误的路会浪费 b[i]分钟。走过的路可能会重复走。问期望走到终点的时间?

解: 用递归的定义写出期望的表达式,然后就可以解出期望。$EX = \frac{\sum a[i]}{n + m} + \frac{\sum b[i] + mEX}{n+m} $


定理证明 递归解题

题意: 有 n 个定理,现在要顺序写出一些推理关系,使得最终这个 n 个定理相互可达。怎么写可以写出最多的推理关系?比如 3 个定理:可以写成 4 条(1->2,2->3,3->2,2->1),也可以写成 5 条(1->3,2->3,1->2,2->1,3->2)

解:1 先向 3 到 n 连边,然后 2 向 3 到 n 连边,再将 1 和 2 相连,这样 1 和 2 就可以缩成一个点。这样规模就变成了 n-1.


kickstar2019 round B

b

题意:有 n 个能量棒,每个能量棒有 s,e,l 三个属性。s 表示吃掉这根能量棒所需要的时间,e 表示吃掉这个能量棒能获得的能量,l 表示每秒钟能量棒的能力会衰减的值。现在要使得所获得的能量最多,问最多是多少? n 为 100

解:对于能量棒 i 和 j,如果不存在能量棒衰减为 0 的情况,那么如果$s_i \times l_j < s_j \times l_i$ 那么就应该先吃 j 再吃 i。按这个顺序排序之后,贪心选就可以了。

但是如果某个能量棒会衰减为 0,那么就不能这么贪心。但这些会衰减为 0 的能量棒并不影响选择的顺序。因此可以 01 背包做一下。

简单证明一下:假设按照排序结果先吃 i 再吃 j 或者只吃 j 不吃 i 。我们需要证明的是先吃 j 再吃 i 不会更优。

  • 第一种情况是 i 和 j 都不会衰减到 0。这时候一定是先吃 i 再吃 j;
  • 第二种情况是 i 会衰减到 0,j 不会。这时候吃完 j,i 已经衰减到 0 了,我们绝对不会再去选择 i
  • 第三种情况是 j 会衰减到 0,i 不会。$e_i - l_i \times t \geq e_j - l_j \times t + e_i - l_i \times(t + s_j)$ 又因为$e_j - l_j(t + s_i) \leq 0$ 并且$s_i \times l_j > s_j \times l_i$。所以先吃 i 的的收益更大。
  • 第四种情况是 i 和 j 都会衰减到 0。这种情况要么吃 i 要么吃 j,不会出现先吃 j 又把 i 吃了的情况。

c

题意:给一个有 n 数字的数组 a[]和一个 s。 定义$(l,r)$表示区间[l,r]内,所有合法元素的数量。合法的定义为该种类的数字重复出现的次数小于等于 s。若出现次数大于 s,那么该元素就不算了。比如 s=2,那么对于 a=[1,1,1],那么$(1,2) = 2, (1,3) = 0$。

解:我们将数组内的元素用 [+1, +1, -2]这种形式来表示,那么对于一个固定的左端点,只要求一个前缀和最大值即可。那么移动左端点的话,只需要更改几个点。所以我们就可以用线段树来维护一个前缀和最大值。