企业官网建设流程全解析

一道难题

时间限制：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）。
  • 计算新的tight：new_tight = tight && (d == up)。
  • 计算新的连续1个数nc：若d == 1，则nc = c + 1；否则nc = 0。
  • 计算新的ok：new_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≤24，c cc有 3 种，tight和ok各 2 种，总状态数约24 × 3 × 2 × 2 = 288 24 \times 3 \times 2 \times 2 = 28824×3×2×2=288。
• 每个状态最多枚举 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的数字都能被统一处理。该方法高效且代码简洁。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;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 lt=l;ll ot=o;if(f[p][c][lt][ot]!=-1)returnf[p][c][lt][ot];ll res=0;ll up=l?(S[p]-'0'):1;for(ll d=0;d<=up;d++){if(d>=2)continue;ll nl=l&&(d==up);ll nc;if(d==1)nc=c+1;elsenc=0;ll no=o||(nc>=3);if(nc>=3)nc=0;res+=dfs(p+1,nc,nl,no);}returnf[p][c][lt][ot]=res;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>S;memset(f,-1,sizeof(f));ll ans=dfs(0,0,1,0);cout<<ans<<endl;return0;}