Codeforces Round #247 (Div. 2) D. Random Task
Codeforces div round Task Random
2023-09-27 14:27:22 时间
题意:
求一个n,使得n+1到2n这些数的二进制中恰好有k个1的数有m个。
思路:
在k同样的情况下,打表之后发现单调性,能够二分。
问题转化为n+1到2n二进制表示之后1的个数为k的有多少个?
进一步统一,假设知道区间[0,x]内的二进制表示之后1的个数为k有cal(x)个,那么答案就是cal(2n)-cal(n)了。
如今要 求cal(x)。
假设x为 101101 。k=3;
由于求比小于等于x的数二进制表示之后1的个数为k的有多少个,所以当第一位为0的时候。后面5位中须要3位为0才干满足条件,C[5][3]。前两位同样,第三位为0的时候。前面已经有2个1。后面三位仅仅需1个1就可以,C[3][1]...
从样例中你应该能得出结论了吧。
逐位枚举。假设前d为同样,已有num个1,该位为1。我们能够将该位置0(由于求的是[0,x]内的二进制表示之后1的个数为k有多少个),那么后面还须要k-num个1,后面还有i为的话,那么ans+= C[i][k-num]。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 15
#define MAXN 100005
#define OO (1LL<<35)-1
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
ll n,m,k,d,ans,tot,flag,cnt;
ll C[70][70];
ll cal(ll x)
{
ll i,j,res=0,num=0;
for(i=62;i>=0;i--)
{
if(x&(1LL<<i))
{
if(k-num>=0) res+=C[i][k-num];
num++;
}
}
return res;
}
int main()
{
ll i,j,t,le,ri,mid,cnt;
for(i=0;i<=64;i++) C[i][0]=1;
for(i=1;i<=64;i++)
{
for(j=1;j<=i;j++)
{
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
while(cin>>m>>k)
{
le=1; ri=1LL<<62;
while(le<=ri)
{
mid=(le+ri)>>1;
cnt=cal(2*mid)-cal(mid);
if(m<=cnt)
{
ans=mid;
ri=mid-1;
}
else le=mid+1;
}
cout<<ans<<endl;
}
return 0;
}
相关文章
- Codeforces Round #307 (Div. 2) D. GukiZ and Binary Operations (矩阵高速幂)
- Codeforces Round #277 (Div. 2)---C. Palindrome Transformation (贪心)
- Codeforces Round #821 (Div. 2) D1. Zero-One (Easy Version)
- CodeCraft-22 and Codeforces Round #795 (Div. 2) C. Sum of Substrings
- Codeforces Round #760 (Div. 3) D. Array and Operations
- Codeforces Round #817 (Div. 4) D. Line
- Codeforces Round #820 (Div. 3) C Jumping on Tiles
- Codeforces Round #828 (Div. 3) E1 E2
- Codeforces Round #182 (Div. 2)
- Educational Codeforces Round 137 (Rated for Div. 2)(C和D)
- Codeforces Round #809 (Div. 2)(C和D1两题)
- Codeforces Round #789 (Div. 2) C (求四元组数)
- Codeforces Round #263 (Div. 1) A B C
- Codeforces Round #221 (Div. 2) D
- Codeforces Round #274 (Div. 2) C. Exams
- Codeforces Round #273 (Div. 2)
- Codeforces Round #271 (Div. 2)