题解 | Bob的蛋糕店

技能树上状压枚举加了这道题，所以就用状压枚举写一下

思路

通过给出的质心计算公式，计算未拿走质点时的质心，再计算拿走k个质点后的质心，若在若干拿走k个质点的方案里，有一种方案可以让拿前和拿后的质心相等，则输出Yes，若所有方案都不行就输出No

状压枚举

如何枚举所有拿走k个质点的方案呢？可以使用状压枚举：

每个质点都有两种状态：被拿走与不被拿走，故我们可以想到二进制，让1表示被拿走，0表示不被拿走

则总共的方案数有种，我们使用一个整数二进制来表示，称其为 mask()，则这个二进制数里的1和0就可以存储当前方案对应哪几块蛋糕会被拿走的信息

Code

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> arr(n+1);
  for (int i = 1; i<=n; i++) cin >> arr[i];
  // 计算未拿走时的质心
  int m1 = 0, m2 = 0;
  for (int i = 1; i<=n; i++)
  {
    m1+=arr[i]*i;
    m2+=arr[i];
  }
  for (int i = 0; i<(1<<n); i++)
  {
	// 要选择正好拿走k个的方案
    if (__builtin_popcount(i)!=k) continue;
	// 统计拿走的部分的和
    int km1 = 0, km2 = 0;
    for (int j = 1; j<=n; j++)
    {
      if (i&(1<<(j-1)))
      {
        km1+=arr[j]*j;
        km2+=arr[j];
      }
    }
	// 将拿走若干质点后的质心与未拿走的比较
    if (m1*(m2-km2)==m2*(m1-km1))
    {
      cout << "Yes"<<endl;
      return ;
    }
  }
  cout <<"No"<<endl;
 
}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  // cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}

代码中，

__builtin_popcount(i)!=k计算的是当前方案对应整数二进制中1（被拿走质点数）的个数，因为题目要求拿k个

i&(1<<(j-1))是用来判断当前方案对应整数二进制中，第j位是不是1，若是证明该位对应的质点会被拿走

m1*(m2-km2)==m2*(m1-km1)将拿走的质点减去，并判断计算的质心是否与未拿走时相同，这里需要将除法转为乘法，防止精度问题