牛客网-2018 美团 CodeM 编程大赛-初赛 B 轮-3-低位值_美团编程大赛决赛牛客网-程序员宅基地

描述

这里写图片描述

题解

一个规律题。默认， $l$ 取 $0$ ，考虑取 $r$ ，首先，如果有非最高位 $1$ 存在 $x$ 个，有第二个部分公式得答案加上 $x$ ，然后根据第三个公式得答案加 $1$ 并且获取一个新的二进制串 $r'$ （全是 $1$ ），以此类推，直到 $r = 0$ 。

对于 $r$ 我们需要考虑两种情况，因为上述循环的第一次取的 $r$ 不一定全是 $1$ 。如果 $n$ 二进制存在至少两个一，例如 $100100110…$ ，那么从高位开始查找到第二个 $1$ ，假如说第一个 $1$ 的权值是 $2^k$ ，第二个 $1$ 的权值是 $2^{k'}$ ，然后取 $r$ 为 $2^k + 2^{k'} - 1$ ，此时二进制是 $100011111…$ ，也就是说初始存在 $x = k$ 个非最高位 $1$ ，这是第一种情况；我们还需要考虑一下 $r$ 取 $n$ 的情况，计数有多少个非最高位 $1$ ，然后在这两种情况中取最优。这样我们就处理完第一轮的运算了，后续的类推，都保证是全 $1$ 二进制，所以我们可以通过预处理来确定不同长度的全 $1$ 二进制通过多少次运算可以得到 $r = 0$ 的状态。

这个题仔细模拟一下，很容易找到规律的，一开始以为是数论题，着实有些虚。

代码

#include <iostream>
#include <string>

using namespace std;

const int MAXN = 2e4 + 10;

string num;
long long temp[MAXN] = {
   0, 1, 1};

void init()
{
    for (int i = 3; i < MAXN; i++)
    {
        temp[i] = temp[i - 1] + i - 1;
    }
}

int main(int argc, const char * argv[])
{
    init();

    cin >> num;

    long long ans = 0;
    for (int i = 1; i < num.length(); i++)
    {
        if (num[i] == '1')
        {
            ans = (num.length() - 1) - i;
            break;
        }
    }

    long long cnt = 0;
    for (int i = 1; i < num.length(); i++)
    {
        if (num[i] == '1')
        {
            cnt++;
        }
    }

    ans = max(ans, cnt);
    ans += temp[num.length()];

    cout << ans << '\n';

    return 0;
}

本文链接：https://blog.csdn.net/f_zyj/article/details/80792391

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

系统端口被占用解决方法_系统空闲进程占用端口-程序员宅基地

文章浏览阅读6.8k次，点赞10次，收藏97次。端口被占用解决方法1 Windows环境1 启动windows命令窗口2 查看系统当前所有端口使用情况3 查询指定的端口使用情况4 可通过进程id号查询进程名称5 根据进程id或进程名称杀死进程2 Linux1 查看所有端口号2 查看指定端口号3 查看端口号被那个进程使用4 杀死进程因博主在windows环境下,IDEA突然崩溃,导致程序异常终止,再次启动程序时,提示端口被占用,故记录一下解决该类问题的方法参考资料:https://jingyan.baidu.com/article/fdffd1f_系统空闲进程占用端口

IDEA使用tomcat插件不加载Maven项目，IDEA添加tomcat插件详解_idea tomcat无法加载项目-程序员宅基地

文章浏览阅读1.1k次。IDEA使用tomcat插件不加载Maven项目，tomcat启动后自动结束tomcat不加载项目的解决方法方法1：方法2：IDEA配置tomcat步骤1：步骤2：步骤3：步骤4：tomcat不加载项目的解决方法下面有两种方法使用其中任意一种即可解决该问题方法1：pom.xml配置文件中加入项目的打包方式。<packaging>war</packaging>方法2：pom.xml 配置文件中，增加 tomcat 的配置，忽略打包，build 放在 project 标_idea tomcat无法加载项目

Quartz项目搭建与任务执行源码分析_quartz源码-程序员宅基地

文章浏览阅读251次。Quartz执行任务主要涉及到数据库中的QRTZ_TRIGGERS和QRTZ_FIRED_TRIGGERS，关注其中的STATE变化是重点。_quartz源码

rtthread使用uart外设（不需要bsp和env工具）_rtthread uart-程序员宅基地

文章浏览阅读1k次。图中的控制台就是调试用的终端，单片机调试常用printf()，rtthread中使用rt_kprintf()，在上图的界面配置好就可以使用PA9、PA10的串口看到如下调试用到的信息：1、rt_kprint()调试信息2、LOG日志信息也可以执行finsh命令，rtt studio有一个putty终端，如下上面介绍了一会终端，言归正传，怎么使用uart外设？drv_common.c里有硬件uart初始化函数rt_hw_usart_init()，进入函数定义，将可以看到for循环里面注册所有._rtthread uart

Matlab_回归分析_逐步回归_hald水泥问题-程序员宅基地

文章浏览阅读4.1w次，点赞39次，收藏212次。例：（Hald,1960）Hald 数据是关于水泥生产的数据。某种水泥在凝固时放出的热量 Y（单位：卡/克）与水泥中 4 种化学成品所占的百分比有关：在生产中测得 12 组数据，见表5，试建立 Y 关于这些因子的“最优”回归方程。对于例 4 中的问题，可以使用多元线性回归、多元多项式回归，但也可以考虑使用逐步回归。从逐步回归的原理来看，逐步回归是以上两种回归方法的结合，可以自动使得方程的_hald水泥问题

MATLAB入门-程序员宅基地

文章浏览阅读162次，点赞2次，收藏2次。MATLAB零基础入门教程

随便推点

深度学习与自然语言处理中的语义理解-程序员宅基地

文章浏览阅读905次，点赞25次，收藏15次。1.背景介绍1. 背景介绍自然语言处理(NLP)是计算机科学和人工智能领域的一个分支，旨在让计算机理解、生成和处理人类语言。语义理解是自然语言处理中的一个关键问题，它涉及到计算机对于自然语言文本的深度理解，以便进行有意义的信息抽取和推理。深度学习是一种人工智能技术，它通过模拟人类大脑中的神经网络结构，使计算机能够从大量数据中自动学习复杂的模式和特征。深度学习在自然语言处理领域取得了显著..._深度学习语义理解

探讨：UDP广播还有前途吗？（代码验证）-程序员宅基地

文章浏览阅读1.2k次，点赞39次，收藏20次。探讨：UDP广播还有前途吗？（代码验证）

表达式求值用python_用栈进行表达式求值-程序员宅基地

文章浏览阅读1.6k次。上一节课，我们介绍了栈，并且在习题里使用栈计算了后缀表达式(最后一道题，这道题一定要先完成。如果那道题做不出来，这节课的内容就更加难以理解)。我们今天继续看一下，如何使用栈完成标准的四则混合运算表达式求值。不同于后缀表达式，遇到一个运算符就可以直接从栈里取两个数进行运算。在标准的四则混合运算表达式中(或者我们称之为中缀表达式)，遇到一个操作符是不能直接计算的，因为计算的顺序要取决于后面的运算符。多..._python用栈实现表达式求值

探秘精彩纷呈的《Awesome AI Cheatsheets》仓库：一站式学习人工智能宝典-程序员宅基地

文章浏览阅读390次，点赞5次，收藏9次。探秘精彩纷呈的《Awesome AI Cheatsheets》仓库：一站式学习人工智能宝典项目地址:https://gitcode.com/ShowMeAI-Hub/awesome-AI-cheatsheets项目简介在深入学习和人工智能领域中，有一款极具价值的资源库——Awesome AI Cheatsheets。这是一个由ShowMeAI维护的开源项目，旨在为开发者、研究人员和学生提供全...

Vue cli3 打包时开启gzip文件压缩_vue3 使用gz压缩之后打包之后的文件没有gz文件-程序员宅基地

文章浏览阅读897次。Vue cli3 打包时开启gzip文件压缩webpack在打包时可以借助 compression webpack plugin 实现gzip压缩，首先需要安装该插件： npm install --save-dev compression-webpack-plugin如果出现tapPromise undefined 的错误时，可在后面加上版本号，降低版本 npm install --save-dev [email protected].在v_vue3 使用gz压缩之后打包之后的文件没有gz文件

CMake的CTest方法_cmake test-程序员宅基地

文章浏览阅读1.2w次，点赞5次，收藏12次。参考：http://hahack.com/codes/cmake/Demo目录结构如下：Test/├── add.cpp└── CMakeLists.txtadd.cpp#include #include int main(int argc, char *argv[]){ if (argc != 3) { std::cout << "pa_cmake test