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

yizibi · 2025-08-24 19:16:42 · 题解

题目大意

把一个数 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，取不了就拆剩下的。

大佬们勿喷码风：

#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;
}

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