某岛

… : "…アッカリ~ン . .. . " .. .
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。