双倍经验题
由于我先做的 P6754，所以一切思路基于 P6754 的题目
“ P6754 这题就是 P3413 的究极弱化版 ” --By Aliemo.
P6754 Description
在给定的 ([a,b]) 区间内求长度 (ge) (2) 的非回文串的个数
Solution
设 (f[i][j][k]) 表示长度为 (i)，最高位为 (j) ，次高位为 (k) 的非回文串的个数
显然有状态转移方程式
[f[i][j][k]=sum_{j/k/l=0}^9f[i-1][k][l]mid j!=k&&j!=l&&k!=l
]
对于答案的统计，就是在求出所有的非回文串个数后，通过给定的边界来判断
对于 (ans_{l,r}) 可以转化为 (ans_{1,r}-ans_{1,l-1})
注意，本题的求解，对于区间端点的处理，最好将其转化为字符串操作
便于求非回文串的个数
像这样
for(int i = len;i >= 1;i --) {
a[i] = x[len - i] - '0';
sum = sum * 10 + a[i];
}
其他的注意事项放在代码里
Code
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#define int long long
#define rr register
using namespace std;
char A[1010],B[1010];
int f[1010][20][20];
int a[1010];
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
void init(){
for(rr int i=2;i<=1000;i++)
for(rr int j=0;j<=9;j++)
for(rr int k=0;k<=9;k++){
if(j==k) continue;
for(rr int l=0;l<=9;l++)
if(k!=l&&j!=l) f[i][j][k]+=f[i-1][k][l];//
if(i==2) f[i][j][k]++;
}
}
int solve(char x[]){
bool t=1;memset(a,0,sizeof a);
int ans=0,cnt=0,sum=0,len=strlen(x),ll1=-1,ll2=-1;
for(rr int i=len;i>=1;i--){a[i]=x[len-i]-'0';sum=sum*10+a[i];}
sum++;ans+=10;if(len==1) return sum;//长度为 1 的 10 个数直接加//如果长度为 1 ，不符合规定
for(rr int i=2;i<len;i++)
for(rr int j=1;j<=9;j++)//排除前导 0
for(rr int k=0;k<=9;k++)
ans+=f[i][j][k];
for(rr int i=len;i>=2;i--){
for(rr int j=0;j<a[i];j++){
if(i==len&&j==0) continue;
for(rr int k=0;k<=9;k++)
if(j!=k&&ll1!=k&&ll1!=j&&ll2!=j) ans+=f[i][j][k];
}
if(ll1==a[i]||ll2==a[i]){t=0;break;}//判断前一位与前两位
ll2=ll1;ll1=a[i];
}
if(t==1)for(rr int i=0;i<=a[1];i++)if(i!=ll1&&i!=ll2)ans++;//最后一位单独处理
return ans;
}
signed main(){
init();cin>>A;cin>>B;
int Ans=solve(B)-solve(A);
int len=strlen(A),vis=0;
for(rr int i=1;i<len;i++)
if(A[i]==A[i-1]||(A[i]==A[i-2]&&i>1)){vis=1;break;}
if(!vis) Ans++;printf("%lld",Ans);
return 0;
}
P3413 Description
在给定的 ([a,b]) 区间内求长度 (ge) (2) 的非回文串的个数
Solution
按照上面的思路，比较两位上相同的
比较麻烦
换个角度，如果用总串数减去非回文串数，那不就是回文串数了
思考过程与原理同上
注意取模
代码一改就行
Code
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#define int long long
#define rr register
#define Mod 1000000007
using namespace std;
char A[1010],B[1010];
int f[1010][20][20];
int a[1010];
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
void init(){
for(rr int i=2;i<=1000;i++)
for(rr int j=0;j<=9;j++)
for(rr int k=0;k<=9;k++){
if(j==k) continue;
for(rr int l=0;l<=9;l++)
if(k!=l&&j!=l) f[i][j][k]=(f[i][j][k]+f[i-1][k][l])%Mod;
if(i==2) f[i][j][k]=(f[i][j][k]+1)%Mod;
}
}
int solve(char x[]){//sum 统计总串数，减去 ans 即可
bool t=1;memset(a,0,sizeof a);
int ans=0,cnt=0,sum=0,len=strlen(x),ll1=-1,ll2=-1;
for(rr int i=len;i>=1;i--){a[i]=x[len-i]-'0';sum=(sum*10+a[i])%Mod;}
sum++;ans+=10;if(len==1) return 0;
for(rr int i=2;i<len;i++)
for(rr int j=1;j<=9;j++)
for(rr int k=0;k<=9;k++)
ans=(ans+f[i][j][k])%Mod;
for(rr int i=len;i>=2;i--){
for(rr int j=0;j<a[i];j++){
if(i==len&&j==0) continue;
for(rr int k=0;k<=9;k++)
if(j!=k&&ll1!=k&&ll1!=j&&ll2!=j) ans=(ans+f[i][j][k])%Mod;
}
if(ll1==a[i]||ll2==a[i]){t=0;break;}
ll2=ll1;ll1=a[i];
}
if(t==1)for(rr int i=0;i<=a[1];i++)if(i!=ll1&&i!=ll2)ans=(ans+1)%Mod;
return (sum-ans+Mod)%Mod;
}
signed main(){
init();cin>>A;cin>>B;
int len=strlen(A),Ans=solve(B)-solve(A);
for(rr int i=1;i<len;i++)
if(A[i]==A[i-1]||(A[i]==A[i-2]&&i>1)){Ans=(Ans+1)%Mod;break;}
printf("%lld",(Ans+Mod)%Mod);
return 0;
}