题解 | Bob的蛋糕店

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    // 步骤1：输入蛋糕数量n和拿走的数量k
    ll n,k;
    cin>>n>>k;
    // 存储每块蛋糕的质量（下标从1开始，对应横坐标i）
    vector<ll>m(n+1);
    
    // 步骤2：计算初始质心的分子和分母
    // 初始质心公式：xc = (Σ m[i] * i) / (Σ m[i])
    double a_sum=0,b_sum=0;  // a_sum = Σ m[i]*i，b_sum = Σ m[i]
    for(ll i=1;i<=n;i++){
        cin>>m[i];
        a_sum += m[i] * i;    // 累加分子项：质量×横坐标
        b_sum += m[i];        // 累加分母项：总质量
    }
    double xc = a_sum / b_sum;  // 初始质心位置
    
    // 步骤3：状压枚举所有“拿走蛋糕”的子集（核心算法）
    // 用整数i的二进制位表示“是否拿走第j块蛋糕”：
    // - 二进制第j位为1 → 拿走第j+1块蛋糕（j从0开始）
    // - 枚举范围：1 ~ (1<<n)-1，覆盖所有非空子集（至少拿走1块）
    for(ll i=1;i<=(1<<n)-1;i++){
        ll cnt=0;  // 记录当前子集拿走的蛋糕数量
        // 初始化剩余质心的分子和分母（先等于初始值，再减去拿走的部分）
        double ta_sum = a_sum, tb_sum = b_sum;
        
        // 遍历每一位，判断是否拿走对应蛋糕
        for(ll j=0;j<n;j++){
            if((i>>j)&1){  // 第j位为1 → 拿走第j+1块蛋糕
                cnt++;
                // 从分子和分母中减去被拿走蛋糕对应的项
                ta_sum -= m[j+1] * (j+1);  // 减去 m[i]*i
                tb_sum -= m[j+1];          // 减去 m[i]
            }
        }
        
        // 步骤4：筛选出“拿走k块蛋糕”的子集，判断剩余质心是否不变
        if(cnt == k){  // 只考虑拿走k块蛋糕的情况
            // 计算剩余质心：ta_sum / tb_sum
            if(xc == ta_sum / tb_sum){  // 剩余质心与初始质心相同 → 满足条件
                cout<<"Yes";
                return 0;  // 找到解，直接输出并结束程序
            }
        }
    }
    
    // 步骤5：所有子集都不满足条件 → 输出No
    cout<<"No";

	return 0;
}