SRM 555

Brief description:

…1000:
。给定一个图灵机。。问按照指定的操作序列(长度 m)有多少种初始状态可以到达给定的目标状态。
。。(不论它的初始位置。。。

Live:

255 […预处理生成长度 50 以内的 5^k 模式串。 暴力匹配点位置 DP ] .。。555 [.. 枚举行使用的行数 i,计算出为了得到 s 需要使用的列数 j,累计 pow() * pow() * C() * C() 。。。]。。。1055 [….] 。

Analysis:

555
。。 555 最后一步的公式推的不对。。(两处 pow() 应该换成可重组合。。
… 另外如果要使用 O(n) 算法的话,对 i=n/2 (也就是列不产生贡献的情况,要特判。。。
(现场生的话直接用 O(n2) 就不会有事了。。。Mark。。。

1000
。。首先确认使用容斥原理。但是复杂度大概会过高。。之后注意到有一个不自然的条件:
“It is not allowed for the head to leave the tape (i.e., move left from the leftmost cell or right from the rightmost one). Should that happen, the player loses — even if the goal has been reached before the head left the tape.”
。。。猜测使用这个条件进行剪枝。。那么步骤是。

首先扫描一遍操作序列得出求出最大的相对位移。。记做 nn。(后面要用这个量剪枝。。
。。以及合法初始位置的范围 l, r。( n 记做 r – l。。。

考察具体的一个位置 x 。。由于之前已经判断了越界的情况,所以现在只要在中间任意一个过程合法就要纳入统计。。
考察操作对每个位置的影响,有三种情况。。未产生过影响。。修改了这个位置且合法。。修改了这个位置但是不合法。。。
最后者只要出现一个则跳过。。继续进行后续的扫描。。前者初始位置的状态是固定的。。不谈。。中间这种会产生一个2倍的因子。。。。。

。。。直接应用容斥定理 O(2^n*n)。。。之后注意到相隔太远的状态之间不可能产生交集的可以跳过。。(。注意跳过的部分仍然可能有平凡解。!。。(初始状态等于目标状态。。

255.。。(字符串,DP。
。。555.。(组合。。
1055.。(容斥原理 + 剪枝。。

External link: