欢迎光临
我们一直在努力

Educational Codeforces Round 187 (Rated for Div. 2) C. Test Generator

C. Test Generator

题意

题目的意思大致是给我们 s 和 m ,要求我们构造一个序列,这个序列需要满足以下两个条件:1.所有元素的和等于 s。2. 每个元素与上 m 都等于其本身。即

1.\\sum_{i=1}^{n}a(i) = s

2.a(i) \\& m = a(i)

最后要求我们输出最小的序列长度 n 。

思路

既然第二个性质存在位运算,那么我们不妨将 m 二进制拆分开来先。

我们可以发现第二个性质可以表述为:假设我们将 m 拆分成多个 2 的幂次,那么我们的目标就是选择其中任意数量的 2 的幂次最终加和等于 s 。

那么这道题是不是可以转变成,我们有 k 个种类的物品,它们的价值分别为 w[i] (1<=i<=k),我们每次可以选择多个种类的物品每个拿一个,最终价值和等于 s,求最小的拿取次数 。

然后我们还可以发现:由于每次一个种类的物品只能拿一个,所以为了让我们的次数最小,我们需要让最终每个物品的个数是尽可能相等的。

这时,我们可以想到:使用二分去枚举所有物品个数的最大值,然后进行判断,尽可能缩小这个值。最后的值就是我们要找的答案 n 。

正解代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

int T;

inline bool check(int s, int m, int maxx){
for(int i=61;i>=0;i–){
if(m>>i & 1){
int tmp = (1ll<<i);
int t = min(maxx, s/tmp);
s -= t*tmp;
}
}
return s == 0;
}

inline void solve(){
int s,m;
cin>>s>>m;
int l = 0 , r = 1e18;
int ans = -1;
while(l<=r){
int mid = l+r>>1;
if(check(s,m,mid)){
ans = mid;
r = mid-1;
}
else l = mid+1;
}
cout<<ans<<'\\n';
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T–) solve();
return 0;
}

赞(0)
未经允许不得转载:171主机测评 » Educational Codeforces Round 187 (Rated for Div. 2) C. Test Generator
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址