题意:给出[L,R],定义x为合法 当x的最高为和最低位相同 例如1021,9
L,R<=1e18 问[L,R]内有多少个数合法?
现在求<=n的合法数f(n). ans=f(R)-f(L-1).
只关心最高位和最低位 现在枚举位数m.n的最高位hi
当m小于n的位数 则开头有9种方案.每种对应中间有10^(m-2).
当m==n的位数时
当最高位<hi时 类似上面的分析方法.
当最高位==hi时 此时还要在分最低位是否>=hi 比如n=2451和n=2453 这两种情况.
n=2453 则2..2 中间有46种方案 .n=2451 2..2 中间有46-1种方案 2(00..44)2.
坑点:不要用系统自带pow 会有精度误差.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
ll l,r,f[N],pw10[N];
int a[N];
void init()
{
f[0]=0;
pw10[0]=1;
for(int i=1;i<=18;i++)
pw10[i]=pw10[i-1]*10ll;
f[1]=f[2]=9;
for(int i=3;i<=18;i++)
f[i]=9ll*pw10[i-2];
}
ll solve(ll n)
{
if(n==0)
return 0;
ll m=n,pos=0,ans=0;
while(m)
{
a[++pos]=m%10;
m/=10;
}
for(int i=1;i<=pos-1;i++)
ans+=f[i];
for(int i=1;i<a[pos];i++)
ans+=pw10[max(0ll,pos-2)];
ll sum=0;
for(int i=pos-1;i>=2;i--)
sum=sum*10+a[i];
ans+=sum+1;
if(a[1]<a[pos])
ans--;
return ans;
}
int main()
{
init();
while(cin>>l>>r)
cout<<solve(r)-solve(l-1)<<endl;
return 0;
}
题意:n张牌,正面为数字a[i],背面为b[i].操作:翻转第i张牌.
n<=1e5,a[i],b[i]<=1e9.问最少需要多少次操作 使得正面向上的数字至少有一半(上取整)相同.
把出现次数>=n/2次的,提取出来 明显不超过4个 每个O(n)判定一下即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,inf=0x3f3f3f3f;
int n,a[N],b[N],c[N],pn=0;
map<int,int> mp,vis;
int main()
{
cin>>n;
int cnt=n/2;
if(n%2) cnt++;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
mp[a[i]]++,mp[b[i]]++;
if(mp[a[i]]>=cnt&&!vis[a[i]])
vis[a[i]]=1,c[++pn]=a[i];
if(mp[b[i]]>=cnt&&!vis[b[i]])
vis[b[i]]=1,c[++pn]=b[i];
}
int ans=inf;
for(int i=1;i<=pn;i++)
{
int fre=0,x=c[i],num=0,res=0;
for(int k=1;k<=n;k++)
{
if(a[k]==x)
fre++,num++;
else if(b[k]==x)
fre++;
}
// cout<<x<<' '<<fre<<' '<<num<<endl;
if(fre>=cnt)
{
if(num>=cnt)
res=0;
else
res=cnt-num;
ans=min(ans,res);
}
}
if(ans>=inf)
ans=-1;
cout<<ans<<endl;
return 0;
}