标签：二分 map int long cats 答案
- 可以证明在k次二分后区间长度最多只有两种，且差最多为1（符合直觉的结论）
- 可以将二分视为对数的划分，而与l和r的取值无关
- 用unordered_map时常会出现奇怪的问题，改成map就好了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
long long K;
map<long long,long long>q[105];
long long dfs(long long x,long long k)
{
if(k<0||x==0)
{
return 0;
}
if(q[k].find(x)!=q[k].end())
{
return q[k][x];
}
if(x==1)
{
return 1;
}
if(x%2==0)
{
return q[k][x]=dfs(x/2-1,k-1)+dfs(x/2,k)+1;
}
else
{
return q[k][x]=dfs(x/2,k-1)+dfs(x/2,k)+1;
}
}
long long s[105];
void update()
{
for(long long i=1;i<=K;i++)
{
s[i-1]+=s[i];
}
}
long long calc()
{
long long sum=0;
for(long long i=0;i<=K;i++)
{
sum+=s[i];
}
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
long long T;
cin>>T;
while(T--)
{
long long l,r,sum=0;
cin>>l>>r>>K;
K=min(K,65ll);
for(int i=0;i<=K;i++)
{
q[i].clear();
}
long long len=r-l+1;
cout<<dfs(len,K)<<endl;
}
return 0;
}
//k的数据范围是假的
标签：二分,
map,
int,
long,
cats,
答案
From： https://www.cnblogs.com/watersail/p/18355920