某島

… : "…アッカリ~ン . .. . " .. .
September 15, 2012

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: