P8704 [蓝桥杯 2020 省 A1] 填空问题 题解

SAMSHAWCRAFT · 2024-03-24 23:06:34 · 题解

我 XCPC 的队友要打蓝桥杯，他做到这个题的 E 的时候和我说他怎么也做不出来这个题。我后来一看标答数据和里面的 E 题答案是 1499441040，感慨蓝桥杯题目数据谬误如此之大竟没有一人怀疑，反而人云亦云重复错误答案，遂作此题解。此题解代码均用 Haskell 语言书写，以推广函数式编程之应用。

A 题

我们可以写一个函数模拟这个过程。定义 tick 是跑步-休息或休息-跑步转换的时刻对应的分钟数，当 tick 是偶数时，当前是全过程开始（对应 tick 是 0 的情况）或休息-跑步转换的时刻（对应 tick 是其它偶数的情况），分类讨论，如果当前体力值 stamina 大于 600 就给体力值减去 600 进入下一分钟，否则递归结束，返回当前的体力值除以跑步时每分钟消耗的体力值 600；当 tick 是奇数时，直接给体力值 stamina 加上 300 即可。

注意到本题题面中写到了：为了使答案为整数，以秒为单位输出答案。所以这里使用了 round 对答案取整，答案为 3880。

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE Strict, MultiParamTypeClasses, FlexibleInstances #-}
import Control.Monad
import System.IO

exercise :: Double
exercise = exerciseWith 10000 600 300 0 
  where
    exerciseWith :: Double -> Double -> Double -> Integer -> Double 
    exerciseWith stamina decRate incRate tick 
     | even tick = 
      if stamina >= decRate 
        then exerciseWith (stamina - decRate) decRate incRate (tick + 1) 
        else fromIntegral tick * 60 + stamina * 60 / decRate
     | otherwise = exerciseWith (stamina + incRate) decRate incRate (tick + 1) 

main :: IO()
main = do
  (print . round) exercise

B 题

混检一共可以分成两步，第一步是检测 k 个人的混合样本，混合样本结果为阴性则这 k 个人检测结果均为阴性，此时每人等价于被检测了 \frac 1 k 次；若第一步检测出阳性，则为每一个人进行一次检测，此时每人等价于被检测了 \frac 1 k + 1 次。所以每个人的样品被检测次数要么为 \frac 1 k，要么为 \frac 1 k +1。

考察这两种取值的概率，设单人检测的结果为阳性的概率（意即题目中的感染率）为 p，则第一步 k 个人混检结果为阴性的概率为 (1-p)^k，需要进入第二步的概率为 1-(1-p)^k，所以每个人被检测的次数期望值是

化简得 E(X)=1-(1-p)^k+\frac 1 k，得到 k 人混检将为每人平均节省

个试剂盒，代入 p=\frac 1 {100} 容易知道 1-E(X) 关于 k 的函数 S(k) 在 k\in(0,k_0) 是凹函数（图像上凸），其中 k_0 是一个在实际情况中相当大的数字，至少在 k=1000 时 \frac {\mathrm d^2 S} {\mathrm d k^2} 仍为正，大于这个 k_0 的部分在实际情况中已经不需要考虑。求导并应用零点存在定理得知该函数极大值点满足 k\in(10,11)，分别计算两点处的函数值得到

因此本人认为答案应该为 11。

我注意到其它题解另有计算出 10 的情况，这里不再重复，本人姑且保留我的个人意见。

C 题

我们可以使用搜索的方法完成这个问题，对于每一批口罩，都有两种分配方法，使用递归函数枚举所有分配方法（共 2^{15} 种），取最小值即可，答案为 2400。

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE Strict, MultiParamTypeClasses, FlexibleInstances #-}
import Control.Monad
import System.IO

masks :: [Integer]
masks = [9090400,8499400,5926800,8547000,4958200,4422600,5751200,4175600,6309600,5865200,6604400,4635000,10663400,8087200,4554000]

distribute :: Integer
distribute = distributeWith masks 0 0 
  where
    distributeWith :: [Integer] -> Integer -> Integer -> Integer
    distributeWith masks alphaMasks betaMasks
     | null masks = abs (alphaMasks - betaMasks)
     | otherwise = min (distributeWith (tail masks) (alphaMasks + head masks) betaMasks) (distributeWith (tail masks) alphaMasks (betaMasks + head masks))

main :: IO()
main = do
  print distribute

D 题

本题等价于问 2\times n 的矩阵的标准杨氏矩阵的数量，利用勾长公式或者应用规约的方法可以直接规约到求第 n 项 Catalan 数的问题上，因此本题不用动态规划，直接写数列递推即可，答案为 1340。

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE Strict, MultiParamTypeClasses, FlexibleInstances #-}
import Control.Monad
import System.IO

arrange :: Integer
arrange = mod (arrangeWith 1010) 2020 
  where
    arrangeWith :: Integer -> Integer 
    arrangeWith 0 = 1
    arrangeWith x = div ((4 * x - 2) * arrangeWith (x - 1)) (x + 1)

main :: IO()
main = do
  print arrange

E 题

我们面对这种有关于数字当中每一位的性质的题其实没有太多的解决办法，数论上并没有什么捷径可以直接求出第 k 个『每一位都是完全平方数的完全平方数』（这样的数组成的数列叫做 Smarandache 平方数位数列，英文名 Smarandache square-digital sequence）。

所以说这种问题目前来说只能是搜索解决，我这里提供一个逐步优化的思路。首先我们写一个最幼稚的搜索代码，直接枚举每一个数字，然后判断它的每一位是不是完全平方数：

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE Strict, MultiParamTypeClasses, FlexibleInstances #-}
import Control.Monad
import System.IO

square :: Integer -> Integer
square x = x * x

checkDigit :: Integer -> Bool
checkDigit x
 | x >= 10 = checkDigit (div x 10) && checkSingleDigit (mod x 10)
 | otherwise = checkSingleDigit x
 where
  checkSingleDigit :: Integer -> Bool
  checkSingleDigit x
   | x == 0 || x == 1 || x == 4 || x == 9 = True
   | otherwise = False

replicateTransitionM :: Monad m => Int -> a -> (a -> Bool) -> (a -> m a) -> m a
replicateTransitionM 0 x _ _ = return x
replicateTransitionM n x g f
 | g x = f x >>= \y -> replicateTransitionM (n - 1) y g f
 | otherwise = f x >>= \y -> replicateTransitionM n y g f

main :: IO ()
main = do
  replicateTransitionM 2020 0 (checkDigit . square) $ \x -> do
    when ((checkDigit . square) x) ((print . square) x) >> return (x + 1)
  >> return ()

我们思考这样一个问题，题目要求的数字是不是有什么特殊性质？最容易想到的是个位数字只能是 0,1,4,9 之中的一个，那么谁的平方的个位数是 0,1,4,9 之一呢？只能是以 0,1,2,3,7,8,9 之一为个位数的数字。这是因为一个数的平方的最后一位只由它自身的最后一位决定。所以我们可以提前去掉不符合这些条件的数字，减少 30% 的搜索量：

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE Strict, MultiParamTypeClasses, FlexibleInstances #-}
import Control.Monad
import System.IO

square :: Integer -> Integer
square x = x * x

-- 0 ^ 2 = 0, 1 ^ 2 = 1, 2 ^ 2 = 4, 3 ^ 2 = 9, 4 ^ 2 = 6 
-- 5 ^ 2 = 5, 6 ^ 2 = 6, 7 ^ 2 = 9, 8 ^ 2 = 4, 9 ^ 2 = 1
-- if x mod 10 = 3 then the next candidate is some y mod 10 = 7
succRCandidate :: Integer -> Integer
succRCandidate x 
 | mod x 10 == 3 = x + 4
 | otherwise = x + 1

checkDigit :: Integer -> Bool
checkDigit x
 | x >= 10 = checkDigit (div x 10) && checkSingleDigit (mod x 10)
 | otherwise = checkSingleDigit x
 where
  checkSingleDigit :: Integer -> Bool
  checkSingleDigit x
   | x == 0 || x == 1 || x == 4 || x == 9 = True
   | otherwise = False

replicateTransitionM :: Monad m => Int -> a -> (a -> Bool) -> (a -> m a) -> m a
replicateTransitionM 0 x _ _ = return x
replicateTransitionM n x g f
 | g x = f x >>= \y -> replicateTransitionM (n - 1) y g f
 | otherwise = f x >>= \y -> replicateTransitionM n y g f

main :: IO ()
main = do
  replicateTransitionM 2020 0 (checkDigit . square) $ \x -> do
    when ((checkDigit . square) x) ((print . square) x) >> return (succRCandidate x)
  >> return ()

我们接着还可以优化，注意到一个完全平方数后两位只可能是某 22 个数字（包括但不限于 00,01,04,09,16,21,24 等），去除掉我们不需要的数字（如 16,21,24 等），然后再分析剩下这些两位数的结尾是哪些两位数平方的最后两位（如 09 结尾的完全平方数能由 03 结尾的 3,103,203,\cdots 和 53 结尾的 53,153,253,\cdots 等生成），由此接着优化 succRCandidate 函数，从而减少搜索范围。

这 22 个数字仍然可以通过编程求得，只需要枚举所有两位数，计算它们的平方，然后留下符合条件的即可。用这种方法，我们也可以继续推广到一个完全平方数的后 k 位只可能是某 F_0(k) 个数字，去掉这 F_0(k) 个数字中数位含非 0,1,4,9 的数，然后反推这些剩余的 F(k) 个数字可能由谁生成，逐步减少搜索范围。注意到 k 存在一个阈值，当你选取了大于这个阈值的 k，你处理出 F(k) 个候选数字结尾所花的时间会大于直接搜索的所花的时间，不过这个阈值并不算好分析。 最终我选取了 k=4 跑出这个答案，但是由于代码过于难看（主要是 succRCandidate 的部分），就不放了。

本题答案为 491499994440019919104，我之前也算错了一回（算成了第 2022 项），如果使用 C++ 等编程语言请务必使用 __int128 或者高精度等防止溢出的方法。