NC19327. 好朋友
描述
输入描述
第一行一个整数t,表示询问个数
接下来t行,每行两个整数li,ri
输出描述
一行一个整数表示答案
示例1
输入:
3 1 1000 233 666 999 999
输出:
0
说明:
在0~1000范围内不存在与题目要求相符的含有“007”的数,所以三次询问的答案都是0示例2
输入:
3 10000 10086 2333 23333 6666 66666
输出:
132
C++11(clang++ 3.9) 解法, 执行用时: 63ms, 内存消耗: 508K, 提交时间: 2020-04-03 14:56:25
#include<bits/stdc++.h> using namespace std; #define ll long long ll l,r,ans,f[20][4],d[20]; int t,m,i,j,k,x,a[20]; ll work(ll n) { if(n<1000) return 0; for(m=0;n;n/=10) a[m++]=n%10; reverse(a,a+m); memset(f,0,sizeof(f)); f[1][0]=a[0]-1; x=0; for(i=1;i<m;i++) { f[i+1][0]=f[i][0]*9; f[i+1][1]=f[i][0]+f[i][1]*9; f[i+1][2]=f[i][1]+f[i][2]*9; f[i+1][3]=f[i][2]+f[i][3]*10; f[i+1][x]+=a[i]-1; f[i+1][x+(x<2&&a[i]||x==2&&a[i]>7)]++; if(x<2&&!a[i]||x==2&&a[i]==7) x++; } return d[m-1]+f[m][3]; } int main() { for(i=0,l=1;i<=18;i++,l*=10) d[i]=work(l-1); scanf("%d",&t); while(t--) { scanf("%lld%lld",&l,&r); ans^=work(r+1)-work(l); } cout<<ans<<endl; return 0; }