牛客小白月赛32 C.消减整数 思维规律

链接：https://ac.nowcoder.com/acm/contest/11163/C

Problem Analysis

给出一个正整数H，从1开始减，第一次必须减1，每次减的数字都必须和上一次相同或者是上一次的两倍，请问最少需要几次能把H恰好减到0。数据范围不小，到 1 e 9 1e9 1e9了。因此考虑十进制下的减法和倍乘运算意义不大。

①.第一次必须减一，这里我们不妨联想到二进制单个数位的规律：我们规定减数为1

1. 要使 1 1 1变成 0 0 0，那么需要做减法 1 1 1次；
2. 要使 0 0 0变成 0 0 0，那么需要先借位 1 1 1次，然后再做减法 2 2 2次。(前提是有位可借，即 H ≠ 0 H≠0 H​=0)

②.往后每次可以翻两倍或不翻倍，考虑翻倍的问题：

减数 1 1 1对应二进制下 1 1 1；翻倍后 2 2 2对应二进制下 10 10 10；再次翻倍后对应二进制下 100... 100... 100...

不难发现：减数有效减法位每翻倍一次左移一位。那么我们可以得出这样一种思路：

对于数 H H H我们可以固定一位进行分析–即最低位。对最低位做①中的“-1”运算，将最低位减为零后整个数字右移一位，将最低位抛弃。这里的右移对应先前②分析中的“有效减法位”规律。

这样，我们可以不考虑减数的翻倍问题，每次只对最低位 − 1 -1 −1，如果最低位是 0 0 0，那么需要 2 2 2次减法操作；如果最低位为 1 1 1，那么需要 1 1 1次减法操作。

这里用一个手模的样例来展示以上的过程：

如图，橙色代表抛弃的位，绿色代表当前数的最低位，那么经过分类讨论，共需要9次。

Accepted Code

代码附带硬核水印~自行去除

#include 
#define ll long long
#pragma GCC optimize("no-stack-protector")
#define rnt register int
#define IOF ios_base::sync_with_stdio(false)
using namespace std;
/*
__          __                                                                     
 \ \        / /                              /\                                     
  \ \  /\  / /_ __  ___   _ __    __ _      /  \    _ __   ___ __      __ ___  _ __ 
   \ \/  \/ /| '__|/ _ \ | '_ \  / _` |    / /\ \  | '_ \ / __|\ \ /\ / // _ \| '__|
    \  /\  / | |  | (_) || | | || (_| |   / ____ \ | | | |\__ \ \ V  V /|  __/| |   
     \/  \/  |_|   \___/ |_| |_| \__, |  /_/    \_\|_| |_||___/  \_/\_/  \___||_|   
                                  __/ |                                             
                                 |___/                                              
*/
/*
  _______  _       ______ 
 |__   __|| |     |  ____|
    | |   | |       | |__   
    | |   | |     |  __|  
    | |   | |____ | |____ 
    |_|   |______||______|                       
*/
/*
  __  __  _       ______ 
 |  \/  || |     |  ____|
 | \  / || |     | |__   
 | |\/| || |     |  __|  
 | |  | || |____ | |____ 
 |_|  |_||______||______|
                         
                         
*/
/*
  _____  _                                              _          _      _             _               
 |_   _|( )                                            | |        | |    | |           | |              
   | |  |/ _ __ ___     __ _  __   __ ___   __ _   ___ | |_  __ _ | |__  | |  ___    __| |  ___    __ _ 
   | |    | '_ ` _ \   / _` | \ \ / // _ \ / _` | / _ \| __|/ _` || '_ \ | | / _ \  / _` | / _ \  / _` |
  _| |_   | | | | | | | (_| |  \ V /|  __/| (_| ||  __/| |_| (_| || |_) || ||  __/ | (_| || (_) || (_| |
 |_____|  |_| |_| |_|  \__,_|   \_/  \___| \__, | \___| \__|\__,_||_.__/ |_| \___|  \__,_| \___/  \__, |
                                            __/ |                                                  __/ |
                                           |___/                                                  |___/ 
*/


signed main(){
    IOF; 
    int t = 0; cin >> t;
    while(t--){
        int h = 0; cin >> h;
        int cnt = 0, dec = 1;
        while(h){
            if(h & 1 == 1) cnt++, h >>= 1;
            else if(h) cnt += 2, h -= 1, h >>= 1;
        }
        cout