AGC060B 题解

发布时间 2023-11-18 18:35:00作者: liangbowen

blog。很强的思维题。


如果能用 \(0\sim 2^T-1\) 表示出来(\(T\le k\))那么显然也可以用 \(0\sim 2^k-1\) 表示出来,转化为求最小的合法填数方案 \(T\)

如图所示,红色是唯一路径,黄粉色处是一个拐角。让在黄粉色拐弯的路径不合法,可以给两者填 \(2^0\)\(2^1\),然后这个值一直往左下延申,把这一整段屏蔽掉。

类似地,每出现一个单独的拐角,\(T\) 就该加一。右上部分的拐弯是同理的,可以不考虑。做完了。

code,时间复杂度 \(O(T(n+m))\)