题目背景
本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。
寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。
题目描述
辣鸡蒟蒻SOL是一个傻逼,他居然觉得数很萌!
好在在他眼里,并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说,101是萌的,因为101本身就是一个回文数;110是萌的,因为包含回文子串11;但是102不是萌的,1201也不是萌的。
现在SOL想知道从l到r的所有整数中有多少个萌数。
由于答案可能很大,所以只需要输出答案对1000000007(10^9+7)的余数。
输入输出格式
输入格式:
输入包含仅1行,包含两个整数:l、r。
输出格式:
输出仅1行,包含一个整数,即为答案。
输入输出样例
输入样例#1:
1 100
输出样例#1:
10
输入样例#2:
100 1000
输出样例#2:
253
说明
记n为r在10进制下的位数。
对于10%的数据,n <= 3。
对于30%的数据,n <= 6。
对于60%的数据,n <= 9。
对于全部的数据,n <= 1000,l < r
分析:
一眼数位dp
于是我就想出了这个
f[i][j][k][l][0/1][0/1][0/1][0/1]
第i位填的是j,i-1是k,i-2是l,有没有回文,1~i是不是前导0,1~i-1不是前导0,卡不卡上界
丧心病狂
在写的时候手残写错一个变量名,
查了一个半小时。。。STO
交上去60分
其余点全T
//这里写60分代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int mod=1000000007;
int f[1001][11][11][11][2][2][2][2];
//f[i][j][k][l][0/1][0/1][0/1][0/1] 第i位填的是j,i-1是k,i-2是l,有没有回文,1~i是不是前导0,1~i-1不是前导0,卡不卡上界
int a[1010],b[1010],l1,l2;
char s[1010];
int doit(int *a,int len)
{
int i,j,k,l,s,p,q,c,o;
memset(f,0,sizeof(f));
for (i=0;i<=a[1];i++) f[1][i][0][0][0][i==0 ? 1:0][1][i==a[1]]=1;
for (i=1;i<len;i++)
for (j=0;j<=9;j++)
for (k=0;k<=9;k++)
for (l=0;l<=9;l++)
for (p=0;p<=1;p++)
for (s=0;s<=1;s++)
for (o=0;o<=1;o++)
for (q=0;q<=1;q++)
if (f[i][j][k][l][p][s][o][q])
{
int tt=9;
if (q) tt=a[i+1];
for (c=0;c<=tt;c++)
{
if (s==1) //全是0
{
(f[i+1][c][j][k][0][c==0 ? 1:0][1][q&(c==a[i+1])]+=f[i][j][k][l][p][s][o][q])%=mod;
}
else
{
if (s==0&&o==1)
(f[i+1][c][j][k][p||(c==j)][0][0][q&(c==a[i+1])]+=f[i][j][k][l][p][s][o][q])%=mod;
else if (s==0&&o==0)
(f[i+1][c][j][k][p||(c==j)||(c==k)][0][0][q&(c==a[i+1])]+=f[i][j][k][l][p][s][o][q])%=mod;
}
}
}
int ans=0;
for (i=0;i<=9;i++)
for (j=0;j<=9;j++)
for (k=0;k<=9;k++)
for (l=0;l<=1;l++)
ans=(ans+f[len][i][j][k][1][0][0][l]%mod)%mod;
return ans%mod;
}
int main()
{
scanf("%s",&s);
l1=strlen(s);
for (int i=0;i<l1;i++)
a[i+1]=s[i]-'0';
scanf("%s",&s);
l2=strlen(s);
for (int i=0;i<l2;i++)
b[i+1]=s[i]-'0';
int ans=(doit(b,l2)-doit(a,l1)+mod)%mod;
bool ff=0;
for (int i=1;i<l1;i++)
if (a[i]==a[i+1]||(i+2<=l1&&a[i]==a[i+2]))
{
ff=1;
break;
}
if (ff) ans++,ans%=mod;
printf("%d",ans);
return 0;
}
正解使用了记忆化搜索
码量较小
就是时刻注意
位运算的优先级
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int mod=1000000007;
bool f[1001][11][11];
int a[1010],b[1010],l1,l2;
char s[1010];
struct node{
int sum,ff; //sum表示所有情况,ff表示已有回文
};
node ans[1001][11][11];
node doit(int *a,int len,int s1,int s2,bool f1,bool f2)
{ //f1 卡不卡边界 f2 之前填的是不是前导零
if (len==0)
{
node po;
po.sum=1;
po.ff=0;
return po;
}
if (f[len][s1][s2]&&f1==0&&f2==0) return ans[len][s1][s2];
//记忆化搜索
node po;
po.sum=po.ff=0;
int tt=f1 ? a[len]:9;
for (int i=0;i<=tt;i++)
{
node p=doit(a,len-1,f2&(i==0) ? 10:i,f2&(i==0) ? 10:s1,f1&(i==a[len]),f2&(i==0));
(po.sum+=p.sum)%=mod;
(po.ff+=p.ff%mod)%=mod;
if (i==s2||i==s1)
(po.ff+=(p.sum-p.ff+mod)%mod)%=mod;
}
if (f1==0&&f2==0)
{
f[len][s1][s2]=1;
ans[len][s1][s2]=po;
} //存储
return po;
}
int main()
{
memset(f,0,sizeof(f));
scanf("%s",&s);
l1=strlen(s);
for (int i=0;i<l1;i++)
a[l1-i]=s[i]-'0';
scanf("%s",&s);
l2=strlen(s);
for (int i=0;i<l2;i++)
b[l2-i]=s[i]-'0';
int an=(doit(b,l2,10,10,1,1).ff-doit(a,l1,10,10,1,1).ff+mod)%mod;
bool ff=0;
for (int i=1;i<l1;i++)
if (a[i]==a[i+1]||(i+2<=l1&&a[i]==a[i+2]))
{
ff=1;
break;
}
if (ff) an++,an%=mod;
printf("%d",an);
return 0;
}