如果一个数字满足以下条件,我们就称它为奇异数:
1、这个数字至少有两位
2、这个数的最低两位是相同的
比如: 1488是一个奇异数,而3、112不是。
牛牛现在给出一个一个区间[L,R],让你计算出在区间内有多少个奇异数
输入包括两个正整数L和R(1 ≤ L ≤ R ≤ 10^12),以空格分割。
输出一个正整数,即区间内的奇异数的个数。
10 20
1
//利用 0 ~ R 之间的数量与 0 ~ L-1 之间的数量做差 /* 0 ~ n之间的数量比较容易算, n/100*10 : 比如说1314,就是1300之前的奇异数的个数, n%100/11+1 : 就是上面的14以内的奇异数的个数, 这样算的话其实0也算,不过在做减法的时候消掉了 */ #include<stdio.h> int main() { long L, R; scanf("%ld%ld", &L, &R); printf("%ld", (R / 100 - L / 100) * 10 + R % 100 / 11 - (L - 1) % 100 / 11); //前面的L忘记减1,可能没测试那个的用例所以AC了.(比如[100,100]) return 0; }
#include <bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMAX_N=2e5+5;ll dp[30][10];inta[30];intres[30];ll n,m;inttpos;ll dfs(intpos,intpre,boollead,boollimit){///最高位,前一位,前导零,是否限制if(pos==-1){// if(tpos==3&&res[1]==0&&res[0]==0&&res[2]==1) cout <<"GOOD" << endl;intcnt0=0;for(inti=tpos-1;i>=0;i--){if(res[i]==0) cnt0++;else break;}// for(int i=tpos-1;i>=0;i--) printf("%d",res[i]);// cout << endl;// cout << "cnt0="<<cnt0 << endl;// cout <<"tpos-cnt0="<<tpos-cnt0<<endl;// cout <<"*********"<<endl;if(tpos-cnt0<2) return0;return(res[0]==res[1]);}if(!limit && !lead && dp[pos][pre]!=-1) returndp[pos][pre];intup=limit?a[pos]:9;ll ans=0;for(inti=0;i<=up;i++){// if(pos==tpos&&i==0) continue;// if(tpos==3&&pos==0&&i==0 &&res[1]==0&& res[2]==1) cout <<"GOOD" << endl;res[pos]=i;ans+=dfs(pos-1,i,lead&&i==0,limit&&i==a[pos]);}if(!limit && !lead) dp[pos][pre]=ans;returnans;}ll solve(ll t){if(t<=10) return0;intpos=0;while(t){a[pos++]=t%10;t/=10;}tpos=pos;// cout <<"pos=" << pos <<endl;returndfs(pos-1,-500,true,true);///最高位,前一位,前导零,是否限制}intmain(void){cin>>n>>m;// cin >> m ;//cout << n <<" "<<m<<endl;memset(dp,-1,sizeof(dp));// cout << solve(m) << endl;// cout << solve(n-1) << endl;printf("%lld\n",solve(m)-solve(n-1));