Asusetic
0%

2021.09.24模拟赛

发表于 分类于 Valine：
本文字数： 669 阅读时长 ≈ 1 分钟

苟利国家生死以，岂因祸福避趋之

2021.09.24模拟赛

A. maze

maze

考虑到竖边代价变大最短路必然不降，所以具有单调性，二分即可

code

B. 论逼格

论逼格

显然有长度为 2i−12i-1 的回文串有 9×10i9\times10^i 个

要求的就是

9∑i=1n2(2i−1)×10i=18∑i=1n2i10i−∑i=1n210i9\sum\limits_{i=1}^{\frac{n}{2}}(2i-1)\times10^i = 18\sum\limits_{i=1}^{\frac{n}{2}}i10^i-\sum\limits_{i=1}^{\frac{n}{2}}10^i

有 ∑i=1niqi=q+qn+1(n(q−1)−1)(q−1)2\sum\limits_{i=1}^{n}iq^i=\dfrac{q+q^{n+1}(n(q-1)-1)}{(q-1)^2}

证明方法很多，建议直接对等比数列求和的式子求导乘x

大力化简完就是 19(11+(18n−11)10n)\dfrac{1}{9}(11+(18n-11)10^{n})

C. 数独

数独

大力爆搜

D. 迷宫

迷宫

只有两行的是经典题高速公路

考虑拓展下就是设 Mi,jM_{i,j} 表示左端点第 ii 个到右端点第 jj 个的最短距离

合并枚举中间点 Floyd 然后拿线段树维护下即可

code