题解 P5657 【格雷码】
HoshinoTented
2019-11-16 16:55:26
这道题其实很简单（应该是入门吧），可以先打出暴力：
```haskell
forceGrayCode :: Word64 -> [String]
forceGrayCode 1 = ["0", "1"]
forceGrayCode n = map ('0':) last ++ map ('1':) (reverse last)
where
last = forceGrayCode (n - 1)
main :: IO ()
main = do
[n, c] <- map read . words <$> getLine
putStrLn $ forceGrayCode n !! fromIntegral c
```
但是一旦测试会发现最大的数据 `64 18446744073709551615` 会 TLE。
这个时候思考一下，事实上拿到的格雷码只可能存在于左边（`map ('0':) last`）或者右边（`map ('1':) (reverse last)`），所以我们可以写出这样的代码：
```haskell
grayCode :: Word64 -> Word64 -> String
grayCode 1 0 = "0"
grayCode 1 1 = "1"
grayCode n c = if c < mid
then '0' : grayCode (n - 1) c -- 如果需要的格雷码在左边，就去左半边找
else '1' : grayCode (n - 1) (mid - 1 - (c - mid)) -- 如果需要的格雷码在右边，就去右半边找
where
mid = 2 ^ (n - 1) -- 当前格雷码长度的一半
main :: IO ()
main = do
[n, c] <- map read . words <$> getLine
putStrLn $ grayCode n c
```