列表

详情


NC19327. 好朋友

描述

BLUESKY007有很多关系很好的朋友,他们无一例外,名字均由数字组成(首字符不为0)且含有"007"(例如“10007”,“10707”就是她的好朋友,而“97037”,“70709”不是),即对于字符串s存在i,j,k(i< j< k)满足.
虽然BLUESKY007眼力极佳,一眼就能看出一个人是不是自己的好朋友,但BLUESKY007是个蒟蒻,她并不擅长数数,但她又想知道在[li,ri]内有多少人是自己的好朋友,所以就找到了你来帮忙.
她会向你询问t次,由于询问次数可能很多,所以你只需要告诉她t次询问答案的异或和即可.

输入描述

第一行一个整数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;
}

上一题