[编程|1000分] 低位值

时间限制:C/C++ 1秒,其他语言 2秒
空间限制:C/C++ 262144K,其他语言 524288K
64bit IO Format: %lld

题目描述

定义lowbit(x) =x&(-x),即2^(p-1) (其中p为x的二进制表示中,从右向左数第一个1的位置),例如lowbit(10)=2,lowbit(3)=1。
定义函数f(l, r)为(其中0 <= l, r <= n):
301312_1529635925563_722E3A0115F9553EFC8967A62B4C4A7E.png
输入n,求f(l, r)的最大值。

输入描述:

n以二进制形式给出,一行一个二进制01串n,表示l,r的上界。
1 <= 字符串n的长度 <= 20,000
数据保证没有前缀0。

输出描述:

一行一个整数表示答案。

示例1

输入

11

输出

2

说明

二进制串“11”对应的十进制数为“3”

题解

中档题/结论题。当n=1时,r=1,l=0得到的答案为1最大,当n=0时,答案为0。当n大于2时,易知l=1时答案最大。r的取值有两种情况,一是直接取n,二是取n的从左往右第二个1为0,之后均为1.在这两者中取1数量最多的即为符合要求的r。根据此l,r的值算出结果即可。

代码

#include<iostream>
#include<bitset>
#include<string>
#include<string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
#include <set>
#include <queue>
#include <stack>
using namespace std;
long long ans,ans1,num;
string s;
int main() {
    cin >> s;
    if (s.length() == 1) {
        if (s[0] == '0') {
            cout << 0;
            return 0;
        }
        if (s[0] == '1') {
            cout << 1;
            return 0;
        }
    }
    for (auto i : s) {
        if (i == '0')ans--;
    }
    for (long long i = 2; i <= s.length(); i++) {
        ans += i;
    }

    for (int i = 0; i < s.length();i++) {
        if (s[i] == '1')num++;
        if (num == 2) { s[i] = '0'; num++; }
        else if (num >= 2) { s[i] = '1'; num++; }
    }
    for (auto i : s) {
        if (i == '0')ans1--;
    }
    for (long long i = 2; i <= s.length(); i++) {
        ans1 += i;
    }
    
    

cout << max(ans,ans1);
}

标签: none

添加新评论