Educational Codeforces Round 118 MEX Sequences 题解 (Java/C++)

题解

首先我们考虑有那些选择方式可以满足条件。

显然[0, 1, 2, 3, 4, 5]是符合条件的,因为对于任意的i,x[i]-MEX(x[1],..., x[i])=-1。
同理,[0, 1, 2, 3, 4, 5, 5, ... ,5]也是满足条件的。
这种构造的总可能数其实是比较明确的:我们用dp[x]表示从0开始以x结尾的子序列的可能数。
于是显然对于每一个i,dp[x[i]]+=dp[x[i]]+dp[x[i]-1]。也就是说,对于当前的x[i],要么其前一位也等于x[i],要么前一位等于x[i]-1。

同时我们注意到另外一种构造,形如:[0, 1, 2, 3, 5]。此时x[i]-MEX(x[1],..., x[i])=5-4=1(当i=5时)。
而这一种构造的一个特殊之处在于,这种构造的进一步扩展有一定的限制。
首先[0, 1, 2, 3, 5, 4]是不符合条件的,因为i=6时,x[i]-MEX(x[1],..., x[i])=4-6=-2。
因此不难发现,其实只有两种扩展方式:1. [0, 1, 2, 3, 5, 3, 5, 3, ...]; 2. [0, 1, 2, 3, 5, 5, 5,...]。
于是对于这种构造,我们用end[x]表示,从0开始以x结尾(不包括x+2)的可能数。
于是对于每一个i,end[x[i]-2]+=end[x[i]-2]+dp[x[i]-2]。也就是说,以x[i]=5为例,要么是在[0,1,2,3,5,3,...]后面添加一个新的5(end[x[i]-2],因为前面的所有情况都可以延续一个5),要么是[0,1,2,3]后面第一次添加5(dp[x[i]-2],因为是第一次,0-3是连续的)。
同时end[x[i]]+=end[x[i]]。也就是说,依然以5为例,如果之前是[0,1,2,3,4,5,7,5,7,...],我们再添加一个5。

最后结果等于所有end[i]和dp[i]的和。

代码

Java

Submission #138464791 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #138464958 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论