题目大意

把一个数 n 拆成 k 个数，且拆分所得到的 b[i] >=2，令sum为每个数的二进制中 1 的数量，求sum的最大值。

思路推导

先考虑每一位都为 1 的情况：

1=1
11=3
111=7
1111=15

……

易发现（1111……1（n个1））= 2^n-1，则我们需要尽量将n拆为k个 2^t-1 。

考虑贪心：

当 $b_i$ =3，可以提供2个1；
当 $b_i$ =7，可以提供3个1，与此同时耗费多了 $7-3=4$ 。
当 $b_i$ =15，可以提供4个1，与此同时耗费多了 $15-7=8$ 。

……

则提供1的数量tmp为 线性增长，而

b_i

却是近似 指数级增长。明显2个3提供的1的数量大于一个7提供的数量，则我们尽量取最小的2^t-1：3 。

解题策略

能取3就取3，取不了就拆剩下的。

大佬们勿喷码风：

CPP

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int read(){
    char c=getchar();
    bool b=0;
    while(c<'0'||c>'9'){
        if(c=='-'){
            b=1;
        }
        c=getchar();
    }
    int res=0;
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
    if(b){
        return -res;
    }
    return res;
}

signed main(){
	int T=read();
	while(T--){
		int n=read();
		if(n%3==0){
            cout<<(n/3)*2<<'\n';
        }else if(n%3==1){
            cout<<((n-4)/3)*2+2<<'\n';
        } else {
            cout<<((n-2)/3)*2+1<<'\n';
        }
	} 
    return 0;
}

本蒟蒻第一篇题解，求赞~

题解：P13830 【MX-X18-T2】「FAOI-R6」二进制与一 III（bit）

文章操作

题目大意

思路推导

解题策略

相关推荐

评论

题解：P13830 【MX-X18-T2】「FAOI-R6」二进制与一 III（bit）