牛客网-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

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

智能推荐

Linux系统下DNS配置指南_linux 服务器修改网络dns-程序员宅基地

文章浏览阅读548次，点赞10次，收藏6次。Linux系统下DNS配置指南_linux 服务器修改网络dns

Springboot/java/node/python/php基于springboot+vue手机售后管理系统【2024年毕设】-程序员宅基地

文章浏览阅读779次，点赞19次，收藏24次。springboot微信小程序的小疾病问诊服务系统的设计与实现。springboot基于spring的物业管理系统的设计与实现。springboot基于Java的高校学生请假系统。ssm基于Android的购物商场APP设计与实现。springboot基于微信小程序的智慧校园系统。ssm基于Android的英语词典的设计与开发。ssm基于SSM+Vue的学生实践管理平台开发。ssm基于android的企业员工考勤系统。ssm基于web的暗香小店系统的设计与实现。ssm基于Web的高等学校公费医疗管理系统。

css中hover属性的使用技巧_css hover的用法-程序员宅基地

文章浏览阅读2.3w次，点赞15次，收藏63次。hover属性用不同的书写方式，来改变不同关系的元素样式。元素:hover 表示聚焦后改变自己元素:hover 元素表示聚焦后改变其子元素元素:hover + 元素表示聚焦后改变其指定的“亲兄弟”（条件是该兄弟元素与其相邻）元素元素:hover ~ 元素表示聚焦后改变其指定的兄弟元素，两个元素相不相邻都行。示例：.first:hover {color: white;}/* 聚焦我改变自己 */.three:hover .three-son {font-size: 20px._css hover的用法

coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习_pca反向压缩-程序员宅基地

文章浏览阅读6k次，点赞3次，收藏15次。coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习1聚类算法clutering1聚类算法简介2K-means21kmeans的目标函数22随机初始化23选择类别数3考试quiz维数约减 dimensionality reduction1数据压缩2数据可视化3维度约简-主成分分析法PCA1 PCA_pca反向压缩

vim插件安装及常用技巧_bxbx.vim-程序员宅基地

文章浏览阅读5.2k次。一、插件安装Vundle是vim的一个插件管理器，同时它本身也是vim的一个插件。插件管理器用于方便、快速的安装、删除、Vim更新插件。mkdir -p ~/.vim/bundlegit clone https://github.com/gmarik/Vundle.vim.git ~/.vim/bundle/Vundle.vim管理器安装完成后，vim ~/.vimrc命令创建.vimrc文件syntax on" tab宽度和缩进同样设置为4set tabstop=4set softta_bxbx.vim

java.lang.ClassNotFoundException：如何解决-程序员宅基地

文章浏览阅读7.2w次，点赞10次，收藏41次。本文适用于当前面临java.lang.ClassNotFoundException挑战的Java初学者。它将为您提供此常见Java异常的概述，这是一个示例Java程序，可支持您的学习过程和解决策略。如果您对与更高级的类加载器相关的问题感兴趣，我建议您复习有关java.lang.NoClassDefFoundError的文章系列，因为这些Java异常密切相关。 java.lang..._java.lang.classnotfoundexception:

随便推点

【全开源】JAVA婚恋相亲红娘牵线系统源码支持微信小程序+微信公众号+H5+APP-程序员宅基地

文章浏览阅读530次，点赞23次，收藏10次。springboot+mybatisplus+mysql 用户端 uniapp（vue语法）管理后台 vue+elementUi。后台服务 springboot+mybatisplus+mysql。一、我们技术使用JAVA后台服务前后端分离。管理后台 vue+elementUi。用户端 uniapp（vue语法）适配小程序+H5+公众号。私信客服获取演示地址。私信客服获取演示地址。

6.python输入整数年份，判断对应整数年份是否为闰年并输出结果_判断闰年的python程序直接输入一个代表年份的正整数-程序员宅基地

文章浏览阅读3.3k次，点赞3次，收藏5次。# -*- coding: UTF-8 -*-year = int(input("输入一个年份："))if year % 100 == 0: if year % 400 == 0: print('%d年是闰年' % year) else: print('%d年不是闰年' % year)else: if year % 4 == 0: print('%d年是闰年' % year) else: print('%d_判断闰年的python程序直接输入一个代表年份的正整数

【图像去噪】偏微分方程PDE图像去噪（含SNR）【含Matlab源码 1890期】_pdnet 深度学习偏微分方程去噪-程序员宅基地

文章浏览阅读987次，点赞20次，收藏19次。偏微分方程PDE图像去噪（含SNR）完整的代码，方可运行；可提供运行操作视频！适合小白！_pdnet 深度学习偏微分方程去噪

Ubuntu18.04安装教程（很详细）_ubuntu18安装-程序员宅基地

文章浏览阅读6.6w次，点赞128次，收藏962次。Ubuntu18.0详尽版安装教程下载Ubuntu18.04下载VMware Workstation安装虚拟机下载Ubuntu18.04官方网站：http://old-releases.ubuntu.com/releases/18.04.4/?_ga=2.44113060.1243545826.1617173008-2055924693.1608557140下载VMware Workstation这个在网上有很多教程下载，这里我就不写了，我用的版本是14 pro。如下图：安装虚拟机1、打开_ubuntu18安装

Android四大组件之Activity--管理方式_android activityrecord中的activitytype-程序员宅基地

文章浏览阅读1.7k次。1. 概览Activity的管理有静态和动态两层涵义：静态是指Activity的代码组织结构，即Application中声明的Activity的集合，这些Activity被组织在一个APK中，有特定的包名。在编写应用程序时，Activity对应到用户界面，它定义了用户界面的布局、交互行为、启动方式等，最重要的，是Activity的生命周期函数。在应用进程看来，只需要按照Android定义的规范，实现生命周期函数的具体逻辑即可，所有的用户界面都遵循同一个规范。编写完一个应用程序的所有用户界面_android activityrecord中的activitytype

[LINUX]sed查找不包含某个字符串的行，并进行替换_sed不包含字符串-程序员宅基地

文章浏览阅读5.5k次，点赞3次，收藏7次。sed 查找不包含某个特性 sed -i "/src/!s/xxx/bbb/g" xxx将不包含src的行中的xxx替换为bbb_sed不包含字符串