Codeforces Round 604 (Div. 2)

作者: ffacs 分类: Codeforces 发布时间: 2019-12-31 03:42

A

给你长度为1e5的字符串,只包含'a','b','c','?'。让你把问号填上abc,问能否使字符串中没有两个相邻字符相同

解法

因为给了三种字符,所以我们只要判断一下前面和后面就一定可以保证填了的部分相邻不同,再判断一下已经填好的地方是否有相邻相同即可

B

\(1..n \le 1e5\)的排列,对于i从1到n回答是否存在\(l\)使得原排列中存在长度为\(i\)的子区间是\(1..i\)的排列

解法

首先,原排列是\(1..n\)的一个排列,所以如果存在,那么一定是连续的。那么对于一个任意的i,我们只需要知道\(1...i\)中的元素,分布在原排列里最小的序号以及最大的序号。如果这个长度是\(i\)那么就有,不然就没有。从\(i\)\(i+1\)的转移是\(O(1)\)的,所以我们只要维护一下左右端点即可。

C

解法

贪心,金牌只给解题数最多的队伍,银牌只要保证比金牌多就不发,剩下全给铜牌。如果满足规则就输出,不然就无解

D

有0,1,2,3四个数字分别\(a,b,c,d\)个。要求输出序列使得相邻两个数字之差的绝对值是1的一种构造方案。如果不存在输出-1

解法

首先,0边上只能是1,3边上只能是2。所以如果0太多或者3太多就不可能构成了。0最多只能比1多一个,这个情况下2和3都要为0,否则就不可能。2和3同理。那么我们就先把0和3用完,我们就构成了很多很多0101和2323,然后把它们连在一起就0101..012323..23。接下来只剩下1和2了。之前的串在中间都不可能再塞进去1或者2了。只可能在两头加。所以对剩下的1和2又有要求。然后再分析一下就做出来了

E

概率DP,先学习一会儿再回来补题

有点学会了,回来补

有n个点,每个点有\(p_i\)的几率通过进入下一个点,不通过就回到第一个点。问期望多少天通过全部的点

解法

\(E_i\)表示走到第\(i\)个点的期望,\(E_1\)=0。那么\(E_i=1/p_i*(p_i+(1-p_i)*E_{i-1})+E_{i-1}\),要走到第\(i\)个点,他肯定要先走到\(i-1\),然后开始尝试,尝试的期望次数是\(1/p_i\)次。每次的代价是成功:\(p_i*1\),失败:\((1-p_i)*(E_{i-1}+1)\)

发表评论

电子邮件地址不会被公开。 必填项已用*标注