某島

… : "…アッカリ~ン . .. . " .. .
April 10, 2020

Andrew Stankevich Contest 14

https://codeforces.com/gym/100217

Problem A. Finite Automata

一個鋪瓷磚的機器人希望可用用 1×2 的瓷磚鋪滿 \(m\times n \) 的矩形。
機器人的指令序列由 HVS 三種字元組成,分別表示平鋪,縱鋪,和跳過。
機器人初始在左上角,它會像老式打字機那樣,每執行完一個指令就往下移動一格,一列處理完之後就跳到下一列的開頭。
一個指令序列是 m-合法的,如果它對於某個 n 在執行完指令序列後,能夠不重疊的鋪滿 mxn 的區域,並且處在右下角。
現在要求你構造一個自動機,能夠識別所有 m-合法的指令序列。。

構造方案很多,腦補一下,這個自動機,可以模擬狀態壓縮 DP 的過程,開 \(m\times(2^m-1)+1 \) 個狀態即可。

Problem B. Bacteria

有兩種菌落種群生活在面積為 1×1 的單位培養皿內,每個種群在每個微元的密度分布,符合以下關係:
The small dx × dy part of the plate with coordinates (x, y) contains a number of first
culture bacteria proportional to (αx + β) dx dy, and a number of second culture bacteria proportional to (γy + δ) dx dy.
求一條直線,使得可以將培養皿分成兩部分,並且兩邊的種群密度相等。

???只考慮一個我都不會。。Orz。。

Problem C. Express Trains

利用 dag 的性質進行 dp。

Problem D. Merge Sort

對一個 1 到 n 的排列進行歸併排序,問:
1. 最多需要進行幾次比較操作。
2. 構造一組這樣的排列。
3. 滿足做多比較次數的排列方案數。
DP。需要高精度。

Problem E. Guarding the Place of the Murder

Vijos 1007. 繞釘子的長繩子
不過每個釘子的半徑不一樣… 需要手動算一算那些弧長。。
hmmm, 也可以.. 直接.. 貼.. HDU 4667 的代碼。。。把三角形的部分去掉就好了。。
(交上去居然 WA 了。。看來還是 Stankevich 的數據比較強啊)

https://user.qzone.qq.com/251815992/blog/1376703043

看起來是精度爆了。

Problem F. Wall Painting

簡單幾何。

Problem G. Palindromes

本質不同的迴文子串計數。
呃,隨著科技的進步,這個題變成迴文樹模板題了。

Problem H. Prime Sum

把 n 拆成若干素數的和,問有多少種方案。
搜索剪枝。

Problem I. Sharing the Sweets

簡單拆分數,需要高精度。

Problem J. Tree Analysis

子樹同構,樹 hash。