P1831 杠杆数
题目描述
如果把一个数的某一位当成支点,且左边的数字到这个点的力矩和等于右边的数字到这个点的力矩和,那么这个数就可以被叫成杠杆数。
比如4139就是杠杆数,把3当成支点,我们有这样的等式:4 2 + 1 1 = 9 * 1。
给定区间[x,y],求出在[x,y]中有几个杠杆数。
输入输出格式
输入格式:
两个数,表示x,y。
输出格式:
一个输出,表示区间[x,y]中杠杆数的个数。
输入输出样例
输入样例#1:
7604 24324
输出样例#1:
897
说明
对于40%的数据,x<=y<=x+100000
对于100%的数据,1<=x<=y<=10^18
#include<iostream>
#include<cstdio>
using namespace std;
long long l,r,ans;
int a[];
bool check(long long now){
int len=;
while(now){
a[++len]=now%;
now/=;
}
int L=,R=;
for(int i=;i<=len;i++){//枚举支点
L=;R=;
for(int j=;j<i;j++)L+=(i-j)*a[j];
for(int j=i+;j<=len;j++)R+=(j-i)*a[j];
if(L==R)return ;
}
return ;
}
int main(){
scanf("%lld%lld",&l,&r);
for(long long i=l;i<=r;i++){
if(check(i))ans++;
}
cout<<ans;
}
40分 暴力(枚举每个数再枚举支点)
/*
数位dp,写的记忆化搜索
应该算数位dp中的简单题吧,套路都在
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long a,b,dp[][][];
int bit[],len;
long long dfs(int pos,int central,int pre,int limit){
if(pos<=)return pre==;
if(pre<)return ;
if(!limit&&dp[pos][central][pre]!=-)return dp[pos][central][pre];
int end=limit?bit[pos]:;
long long ans=;
for(int i=;i<=end;i++){
ans+=dfs(pos-,central,pre+i*(pos-central),limit&&i==end);
}
if(!limit)dp[pos][central][pre]=ans;
return ans;
}
long long solve(long long x){
len=;
while(x){
bit[++len]=x%;
x/=;
}
long long ans=;
for(int i=;i<=len;i++)ans+=dfs(len,i,,);
return ans-len+;
}
int main(){
memset(dp,-,sizeof(dp));
scanf("%lld%lld",&a,&b);
printf("%lld",solve(b)-solve(a-));
}
100分 数位dp