题解归档 - cf535B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf535B
• 本地来源：problems/cf535B/idea.md
• 题目链接：https://codeforces.com/contest/535/problem/B
• 原始标题：cf535B — Tavas and SaDDas

思路

cf535B — Tavas and SaDDas

题意

给定仅由 4、7 组成的幸运数 n（1 ≤ n ≤ 10^9），求它在所有幸运数从小到大排序后的 1-based 下标。

做法

把 4 看成二进制 0，7 看成 1，则长度为 L 的幸运数与 L 位二进制一一对应。

• 长度小于 L 的幸运数共有 2^1 + 2^2 + … + 2^{L-1} = 2^L - 2 个。
• 当前串按位转二进制得 v，在同长度中排第 v+1。
• 答案：ans = (2^L - 1) + v，其中 v 由左到右 ans = ans*2 + (c=='7') 累加得到。

验证

结论

经典二进制映射；O(位数) 实现即可。

代码

来源：problems/cf535B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:20:31
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
ll i,ans;
int main(){
    cin>>s;
    ans=0;
    for(i=0;i<(ll)s.size();i++){
        ans=ans*2;
        if(s[i]=='7') ans++;
    }
    ans+=(1LL<<(ll)s.size())-1;
    cout<<ans<<endl;
    return 0;
}