一道难题【牛客tracker 每日一题】

一道难题时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一个数字n nn求出1 − n 1 - n1−n中只由0 00或1 11组成的且至少有三个1 11相连的数不含前导零有多少个。输入描述第一行一个整数n ( 1 ≤ n ≤ 10 23 ) n\ (1 \le n \le 10^{23})n(1≤n≤1023)。输出描述一个整数表示满足条件的数的个数。示例 1输入2001输出3说明1 − 2001 1 - 20011−2001中满足条件的有111 , 1110 , 1111 111,\ 1110,\ 1111111,1110,1111。数据范围与提示1 ≤ n ≤ 10 23 1 \le n \le 10^{23}1≤n≤1023最多24 2424位十进制数核心思路数位 DP。状态设计为已处理到的位置i ii末尾连续1 11的个数c取值0 / 1 / 2 0/1/20/1/2≥ 3 \ge 3≥3时直接标记为已满足是否已经出现过连续的111布尔标记ok是否紧贴n nn的对应前缀tight是否已经开始填数started用于处理前导零与「不含前导零」的约束。转移时每一位只能选0 00或1 11当tight为真时该位可选范围受n nn对应数字限制由于n nn可能很大把n nn当作字符串逐位处理即可。最终统计所有满足ok true且started true的合法数的个数。由于长度不超过24 2424位、每位仅2 22种取值答案规模不会超过2 24 2^{24}224用 64 位整数即可容纳若用 Python/C 实现也可直接递归记忆化map或数组求解。时间复杂度约为O ( 位数 × 3 × 2 × 2 × 2 ) O(\text{位数} \times 3 \times 2 \times 2 \times 2)O(位数×3×2×2×2)常数极小。解题思路解题思路本题是数位 DP的经典应用。要求统计1 ∼ n 1 \sim n1∼n中十进制表示仅由0和1组成且至少包含连续三个1的数的个数。由于n nn最大可达10 23 10^{23}1023最多 24 位无法暴力枚举需要按位进行动态规划。1. 问题等价转化将n nn视为字符串S SS其长度为L LL。我们需要统计所有长度不超过L LL的、仅含0和1的字符串允许前导零因为前导零不影响数字的值且该字符串中至少出现过一次111并且其数值不超过n nn。允许前导零意味着我们可以统一处理所有长度≤ L \le L≤L的数字长度不足L LL的数字等价于在最高位补前导零这不影响其是否包含连续的1。因此只需在长度为L LL的 01 串上进行数位 DP同时通过tight标记保证不超过n nn。2. 状态设计定义dfs(p, c, tight, ok)p当前处理到第p pp位从 0 开始共L LL位。c当前末尾连续1的个数取值范围为0 , 1 , 2 0, 1, 20,1,2若达到 3 则立即标记ok true并将c重置为 0以便继续统计后续位。tight布尔值表示当前位是否受到S SS对应位的限制。若为true则当前位最大只能取S[p] - 0否则可取0 00或1 11。ok布尔值表示从最高位到当前位是否已经出现过连续三个1。3. 状态转移若p L则返回ok ? 1 : 0。若当前状态已计算过直接返回记忆化结果。确定当前位可选的最大数字up若tight为真up S[p] - 0否则up 1。枚举当前位数字d从 0 到up若d 2跳过因为只能填 0 或 1。计算新的tightnew_tight tight (d up)。计算新的连续1个数nc若d 1则nc c 1否则nc 0。计算新的oknew_ok ok || (nc 3)。若nc 3将nc重置为 0因为已经满足条件后续连续1的计数重新开始。累加递归结果res dfs(p 1, nc, new_tight, new_ok)。记忆化数组f[p][c][tight][ok]记录结果初始化为 -1。4. 最终答案调用dfs(0, 0, 1, 0)即可得到1 ∼ n 1 \sim n1∼n中满足条件的数的个数。5. 复杂度分析状态数L ≤ 24 L \le 24L≤24c cc有 3 种tight和ok各 2 种总状态数约24 × 3 × 2 × 2 288 24 \times 3 \times 2 \times 2 28824×3×2×2288。每个状态最多枚举 2 个数字转移常数级。时间复杂度O ( L × 3 × 2 × 2 × 2 ) O(L \times 3 \times 2 \times 2 \times 2)O(L×3×2×2×2)可忽略不计。空间复杂度O ( L × 3 × 2 × 2 ) O(L \times 3 \times 2 \times 2)O(L×3×2×2)极小。总结利用数位 DP 逐位构造只含0和1的数字同时跟踪末尾连续1的个数和是否已出现过111。通过tight参数保证不超过n nn允许前导零使得所有长度不超过L LL的数字都能被统一处理。该方法高效且代码简洁。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;string S;ll f[25][3][2][2];lldfs(ll p,ll c,ll l,ll o){if(p(ll)S.size())returno?1:0;ll ltl;ll oto;if(f[p][c][lt][ot]!-1)returnf[p][c][lt][ot];ll res0;ll upl?(S[p]-0):1;for(ll d0;dup;d){if(d2)continue;ll nll(dup);ll nc;if(d1)ncc1;elsenc0;ll noo||(nc3);if(nc3)nc0;resdfs(p1,nc,nl,no);}returnf[p][c][lt][ot]res;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinS;memset(f,-1,sizeof(f));ll ansdfs(0,0,1,0);coutansendl;return0;}