美团2018年CodeM大赛-初赛B轮 C题低位值

本文主要是介绍美团2018年CodeM大赛-初赛B轮 C题低位值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://www.nowcoder.com/acm/contest/151/C
来源：牛客网

题目描述

思路：

看了下公式，很明显对于给定的一个l,r,f(l,r)是有一个确定的值

那么知道确定l,r,就能算出最大值；

因为l,r都不确定，所以我把n设成100，暴力跑了区间内所有的l,r,

最后发现f(l,r)取最大值的时候，l永远是1；

确定了l之后,接下去就是确定r；

分析一下公式，因为知道了l=1，公式里的otherwise的情况是 r-lowbit(r)<l<r,既r-lowbit(r)=0的情况。

然后暴力跑了一个r-lowbit(r)=0，发现此时的r全是2的幂次；

大概直到f(1,r)是怎么跑的了。

对于一个2进制的r=1011101,它的变化情况是这样的：

1011101->1011100->1011000->1010000->1000000->111111->...

用文字表示就是:

(1)给一个二进制，把最右边的那个1变成0，直到这个数只有第一位是1，其它位是0；（公式里第二个条件）

(2)然后第一位变成0，后面全变成1;(公式里第三个条件)

重复执行（1）,(2)，直到1>=r,;(公式里第一个条件)

然后就是找r的过程，很明显应该挑[1,n]中二进制1最多的数，作为r;

假设n=10110001,那么r=10011111；也就是吧第二1变成0，后面全变成1

或者n=11111111,那么r=10000000;全是1，r就是n；

或者n=10000000,那么r=10000000；除了首位全是0，r=n;

int main()
{string str;cin >> str;int ans = 0;int num1 = 0;int num2 = 0;if (str == "1"){cout << "1" << endl;return 0;}for (int i = 1; i < str.size(); i++){if (str[i] == '1')num1++;}if (num1 == 1)		num2 = 1;else if (num1 == 0)	num2 = 0;else{for (int i = 1; i < str.size(); i++){if (str[i] == '1'){num2 = str.size() - (i+1);break;}}}ans = max(num1,num2)+(1 + str.size() - 1)* (str.size() - 1)/ 2;cout << ans << endl;return 0;
}

这篇关于美团2018年CodeM大赛-初赛B轮 C题低位值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---