洛谷P3413 P6754

双倍经验题

由于我先做的 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;

}

巴特西

洛谷P3413 P6754

P6754 Description

Solution

Code

P3413 Description

Solution

Code

最新文章

热门文章