2^20时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述我似乎曾记忆化搜寻过这个地方……长途是A C M ACMACM大陆一只快乐的小男孩。今天他在c f cfcf战场上历练遭遇了T TT波丧尸长途快被丧尸咬死啦幸好他手中的两把武器都还有20 20 20 20 20^{{20}^{{20}^{20}}}20202020枚子弹一枚子弹可以击中一个丧尸武器1——【AC】每次射击可以发射一枚子弹武器2——【AK-47】每次射击可以同时朝当前每个丧尸均发射一枚子弹然而丧尸有种特殊的能力每次击中并不会死掉反而会立刻复制出一个新的丧尸长途有点绝望。幸好他发现当前这波的所有丧尸都处在一个特殊的圆盘上这个圆盘被称为圆神当丧尸的数量是2 20 2^{20}220的倍数时可以选择启动这个装置消灭当前这波的全部丧尸值得注意的是一共有T TT大波丧尸只有当一波的丧尸被全部消灭后下一波的丧尸才会出现并且手中武器的子弹数也会恢复情况很紧急长途请你帮帮他。对于每一波丧尸最少需要射击多少次才能消灭这一波的所有丧尸。若消耗完所有的子弹都无法消灭这一波的所有丧尸请输出− 1 −1−1输入描述第一行包含一个整数T TT表示长途遭遇了T ( 1 ≤ T ≤ 10 5 ) T (1≤T≤10^5)T(1≤T≤105)波丧尸对于每波丧尸仅输入一行包含一个正整数n ( 1 ≤ n ≤ 10 9 ) n (1≤n≤10^9)n(1≤n≤109)表示当前这波的丧尸数输出描述对于每波丧尸仅输出一行若消耗完所有的子弹都无法消灭这一波的所有丧尸输出− 1 −1−1否则输出消灭当前这波的所有丧尸所需要的最少射击次数示例1输入3 1048575 1048576 1输出1 0 20解题思路本题本质是模意义下的最少操作次数问题。每次操作可以令当前丧尸数n nn加1 11武器1或乘2 22武器2求使n nn变为2 20 2^{20}220倍数所需的最少操作次数。1. 问题等价转化目标条件n ≡ 0 ( m o d 2 20 ) n \equiv 0 \pmod{2^{20}}n≡0(mod220)。操作操作1ACn → n 1 n \to n1n→n1消耗一次射击。操作2AK-47n → 2 n n \to 2nn→2n消耗一次射击。子弹限制两把武器的子弹数均为天文数字20 20 20 20 20^{20^{20^{20}}}20202020远大于任何可行操作所需因此本题中子弹不会耗尽始终有解。最优化目标求从初始n nn到达目标的最少操作次数。由于目标只依赖n m o d 2 20 n \bmod 2^{20}nmod220可先将n nn对M 2 20 M 2^{20}M220取模。若余数为0 00则无需操作。否则问题变为在模M MM意义下从x n m o d M x n \bmod MxnmodM出发每次可 1 11或× 2 \times 2×2求变为0 00的最小步数。2. 算法实现枚举加法次数观察操作性质× 2 \times 2×2会放大之前所有 1 11的贡献因此最优操作序列一定将所有 1 11放在所有× 2 \times 2×2之前若某次 1 11在× 2 \times 2×2之后将其移至× 2 \times 2×2之前等价于加了0.5 0.50.5不可能更优。设我们做了i ii次 1 11得到x n i x n ixni。此后再做k kk次× 2 \times 2×2最终值为x ⋅ 2 k x \cdot 2^kx⋅2k。要使该值成为2 20 2^{20}220的倍数只需x ⋅ 2 k x \cdot 2^kx⋅2k包含至少20 2020个因子2 22。设x xx中因子2 22的个数为c cc即x xx能被2 c 2^c2c整除但不能被2 c 1 2^{c1}2c1整除则需c k ≥ 20 c k \ge 20ck≥20最小k 20 − c k 20 - ck20−c。总操作次数为i ( 20 − c ) i (20 - c)i(20−c)。由于直接做20 2020次× 2 \times 2×2i 0 , c i0, ci0,c为n nn的因子2 22个数k 20 − c k20-ck20−c总步数≤ 20 \le 20≤20。因此最优解的操作次数不可能超过20 2020枚举i ii从0 00到20 2020即可覆盖所有可能的最优解。初始r e s 20 res 20res20。遍历i ∈ [ 0 , 20 ] i \in [0, 20]i∈[0,20]计算x ( n m o d M ) i x (n \bmod M) ix(nmodM)i。计算c cc反复除以2 22直到奇数统计除的次数。更新r e s min ( r e s , i 20 − c ) res \min(res, i 20 - c)resmin(res,i20−c)。输出r e s resres。3. 复杂度分析时间复杂度对每组数据枚举O ( L ) O(L)O(L)次L 20 L20L20总数据量T ≤ 10 5 T \le 10^5T≤105总操作量约2 × 10 6 2 \times 10^62×106非常快。空间复杂度O ( 1 ) O(1)O(1)。总结将问题转化为模2 20 2^{20}220下的最少操作次数。利用“先加后乘”的最优性质枚举 1 11的次数计算所需的× 2 \times 2×2次数取最小值。上界为20 2020保证了极低的枚举开销能够高效处理大量数据。代码简要说明常量定义L20MD 1L1048576 10485761048576。预处理若n m o d M D 0 n \bmod MD 0nmodMD0直接输出0 00。取模n ← n m o d M D n \gets n \bmod MDn←nmodMD确保n ∈ [ 1 , M D − 1 ] n \in [1, MD-1]n∈[1,MD−1]。枚举res Li从0 00到L LLx n i计算cx中2 22的幂次nd (L - c) i若nd res则更新。输出输出res。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidS(){ll n;cinn;constll L20;constll MD1LLL;if(n%MD0){cout0endl;return;}n%MD;ll resL;for(ll i0;iL;i){ll xni;ll c0;while(x%20){x/2;c;}ll nd(L-c)i;if(ndres)resnd;}coutresendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--)S();return0;}
原理与应用详解)
