Atcoder Regular Contest 065(E没做)

C 白昼夢 / Daydream

题解:
贪心 从后向前比较方便 每次看最后3位 四个串的最后3位都不同 所以可以直接确定应该是那个串
时间复杂度: O(n)

D 連結 / Connectivity

题解:
就是给定两个图, 点集相同, 边集不相同, 问对于每一个点, 有多少个点在两个图中同时与它属于一个连通块
对于每一个图, 我们可以通过dfs或者并查集处理出来每个点属于哪一个连通块
这时候我们把两个合起来, 用hash或者map记录下来每一种情况(指的是类似于一个pair的状态)对应着有多少个点 就得到了答案
时间复杂度: O(n)

F シャッフル / Shuffling

题解:
关键在于题目中的一个性质 l_i \leq l_i+1
这有什么用处呢 其实即使输入不限制这个条件也是一样的 大不了读入之后排序就好了
那么这个条件的作用在于 当前做到第i个命令的时候, l_i-1之前的都已经确定, 所以我们可以dp
令dp[L][R][num]表示当前做到左端点为L,右端点为R的区间, L到R中间的1的个数为num的方案数
但是我们必须保证 r_i+1之后的元素确定 不然的话num这一维状态不好变化
然后发现 事实上 l_i,r_i都是单调递增的
因为对于当前的l, 我们可以找到以他为左端点的所有区间中r最大的那一个, 其他的区间对结果没有影响, 反正都是将这一段大区间里面的元素shuffle一下
所以对于每一个l,只有最大的r是有用的 我们把这个r处理出来, 记作a_l
记录ok_l表示所有区间中出现的所有的左端点坐标l是否出现
记录sum_l表示从L对应的R到下一个L对应的R之间(左开有闭)中1的数量
然后把dp状态中第二维去掉
下面我们就可以进行转移:
dp[L][num]=\left\{\begin{array}{cc} 1 & L=n\\ dp[L+1][num-1] & ok_L=0 \& S_i=1\\ dp[L+1][num] & ok_L=0 \& S_i=0\\ dp[L+1][num+sum_L] & ok_L=1 \& num=0\\ dp[L+1][num+sum_L]+dp[L+1][num+sum_L-1] & ok_L=1 \& num>0 \end{array}\right.
用记忆化搜索去做
时间复杂度:O(n)