明七暗七
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
今天是个特殊的日子，CSL和他的小伙伴们围坐在一张桌子上玩起了明七暗七的游戏。游戏规则是这样的：
一个人报出一个起始数，接下来按照逆时针的顺序轮流报数，如果碰到数是7的倍数或含有7，则拍手，下一个人接着报数。直到有一个人报错了数字或者没有及时拍手为止。
玩游戏嘛，当然得有惩罚。这么简单的游戏对CSL的学霸小伙伴而言实在是太无脑了，轻轻松松数到上万根本不在话下。但是对于数学是体育老师教的CSL来说，实在是太难了。快帮他算算什么时候应该拍手吧。
输入描述:
输入两个整数m和n。(1 ≤ m, n ≤ 1012)
输出描述:
输出一个整数，表示m以后第n个需要拍手的数字。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[20][8];
int digit[25];
ll dfs(int deep,ll state,bool lmt){
if (!deep) return state?1:0;
if (!lmt&&dp[deep][state]>=0) return dp[deep][state];
int i,up=lmt?digit[deep]:9;
ll cnt=0;
for (i=0;i<=up;i++)
{
if (i==7) continue;
cnt+=dfs(deep-1,(state*10+i)%7,lmt&&i==up);
}
return lmt?cnt:dp[deep][state]=cnt;
}
ll cal(ll num){
int k=1;
while (num){
digit[k++]=num%10;
num/=10;
}
return dfs(k-1,0,true);
}
int main(){
ll n,m,left,right,mid,tmp;
while (~scanf("%lld%lld",&m,&n)){
memset(dp,-1,sizeof(dp));
left=0;right=1LL*1e18;
tmp=m-cal(m);
while (left<=right){
mid=(left+right)>>1;
if (mid-cal(mid)>=tmp+n)
right=mid-1;
else
left=mid+1;
}
printf("%lld\n",left);
}
return 0;
}
好朋友
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
BLUESKY007有很多关系很好的朋友,他们无一例外,名字均由数字组成(首字符不为0)且含有"007"(例如“10007”,“10707”就是她的好朋友,而“97037”,“70709”不是),即对于字符串s存在i,j,k(i< j< k)满足
¯¯¯¯¯¯¯¯¯¯¯¯¯
s
i
s
j
s
k
=
¯¯¯¯¯¯¯¯
007
sisjsk¯=007¯.
虽然BLUESKY007眼力极佳,一眼就能看出一个人是不是自己的好朋友,但BLUESKY007是个蒟蒻,她并不擅长数数,但她又想知道在[li,ri]内有多少人是自己的好朋友,所以就找到了你来帮忙.
她会向你询问t次,由于询问次数可能很多,所以你只需要告诉她t次询问答案的异或和即可.
输入描述:
第一行一个整数t,表示询问个数
接下来t行,每行两个整数li,ri
输出描述:
一行一个整数表示答案
#include<cstdio>
#include<iostream>
#include<cstring>
#define lint long long
using namespace std;
lint t,l,s,ch,r,ans,arr[20],res[20][4];
inline lint read(){
s=0,ch=getchar();
while (ch==' '||ch=='\n') ch=getchar();
while ('0'<=ch&&ch<='9')
s=s*10+ch-'0',
ch=getchar();
return s;
}
lint dfs(lint pos,lint cmd,lint led,lint lim){
if (pos==0) return cmd==3;
if (!led&&!lim&&res[pos][cmd])
return res[pos][cmd];
lint maxn=lim?arr[pos]:9,tmp=0;
for (lint i=0;i<=maxn;++i){
if (cmd==0)
tmp+=dfs(pos-1,!i&!led,led&!i,lim&(i==arr[pos]));
else if (cmd==1)
tmp+=dfs(pos-1,(i==0)+1,0,lim&(i==arr[pos]));
else if (cmd==2)
tmp+=dfs(pos-1,(i==7)+2,0,lim&(i==arr[pos]));
else if (cmd==3)
tmp+=dfs(pos-1,3,0,lim&(i==arr[pos]));
}
if (!led&&!lim) res[pos][cmd]=tmp;
return tmp;
}
inline lint sol(lint x){
memset(arr,0,sizeof(arr));
memset(res,0,sizeof(res));
lint cnt=0;
while (x!=0){
arr[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,1,1);
}
int main(){
t=read();
while (t--){
l=read(),r=read();
ans^=(sol(r)-sol(l-1));
}
printf("%lld\n",ans);
}
[AHOI2009]SELF 同类分布
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。
输入描述:
输入a,b
输出描述:
输出[a,b]中各位数字之和能整除原数的数的个数
示例1
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define N 203
#define LL long long
using namespace std;
LL f[21][N][N][2],l,r;
int cnt,a[N];
LL solve(LL x){
if (x==0) return 0;
cnt=0;
while (x){
a[++cnt]=x%10;
x/=10;
}
reverse(a+1,a+cnt+1);
LL ans=0;
for (int sum=1;sum<=18*9;sum++){
memset(f,0,sizeof(f));
f[0][0][0][1]=1;
for(int i=0;i<=cnt;i++)
for (int j=0;j<=18*9;j++)
for (int k=0;k<=18*9;k++)
for (int l=0;l<=1;l++)
if (f[i][j][k][l]){
for (int t=0;t<=9;t++){
if (l==1&&t>a[i+1]) break;
f[i+1][j+t][(k*10+t)%sum][(l==1&&t==a[i+1])?1:0]+=f[i][j][k][l];
}
}
ans+=f[cnt][sum][0][0]+f[cnt][sum][0][1];
}
return ans;
}
int main(){
scanf("%lld%lld",&l,&r);
printf("%lld\n",solve(r)-solve(l-1));
}
链接：https://ac.nowcoder.com/acm/problem/19945
来源：牛客网
[CQOI2016]手机号码
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号 码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数 量。
工具需要检测的号码特征有两个：号码中要出现至少3个相邻的相同数字，号码中不能同时出现8和4。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、 23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。 手机号码一定是11位数，前不含前导的0。工具接收两个数L和R，自动统计出[L,R]区间 内所有满足条件的号码数量。L和R也是11位的手机号码。
输入描述:
输入文件内容只有一行，为空格分隔的2个正整数L,R。
10^10 ≤ L ≤ R < 10^11
输出描述:
输出文件内容只有一行，为1个整数，表示满足条件的手机号数量。
#include<cstdio>
#include<cstring>
#include<string>
#define LL long long
using namespace std;
LL L,R,A[20],B[20],f[20][20][20][2][2][2][2][2],ans;
int main(){
scanf("%lld%lld",&L,&R);
for (int i=11;i>=1;--i)
{A[i]=L%10,L/=10;
B[i]=R%10,R/=10;
}
for(int i=A[1];i<=B[1];i++)
f[1][i][1][0][i==4?1:0][i==8?1:0][i==A[1]?1:0][i==B[1]?1:0]=1;
for (int i=1;i<=10;++i)
for (int j=0;j<=9;++j)
for (int k=1;k<=11;k++)
for (int p=0;p<=1;++p)
for (int a=0;a<=1;a++)
for (int b=0;b<=1;b++)
for (int c=0;c<=1;c++)
for (int d=0;d<=1;d++)
if (f[i][j][k][p][a][b][c][d]){
int l,r;
if (c&&d) l=A[i+1],r=B[i+1];
else if (!c&&!d) l=0,r=9;
else if (!c) l=0,r=B[i+1];
else l=A[i+1],r=9;
for (int t=l;t<=r;t++){
int x=(j==t)?k+1:1;
f[i+1][t][x][p|(x>=3?1:0)][a|(t==4?1:0)][b|(t==8?1:0)][c&(t==A[i+1]?1:0)][d&(t==B[i+1]?1:0)]+=f[i][j][k][p][a][b][c][d];
}
}
for (int j=0;j<=9;j++)
for (int k=1;k<=12;k++)
for (int c=0;c<=1;c++)
for (int d=0;d<=1;d++)
ans+=f[11][j][k][1][0][1][c][d]+f[11][j][k][1][1][0][c][d]+f[11][j][k][1][0][0][c][d];
printf("%lld\n",ans);
}
京公网安备 11010502036488号