简单Dp选讲

wgyhm

2022-10-13

dp, 数位dp

最近学了点简单的数位 dp。

虽然常数略大一点，但是记搜是真的好写而且还不怎么动脑子/se

P4999 烦人的数学作业

记录当前第几位，是否到上界。

没了。

P1836 数页码

同上

P6218 [USACO06NOV] Round Numbers S

记录当前是第几位，有几个 $0$ ，是否到上界，有无前导 $0$。

P4317 花神的数论题

记录当前是第几位，有几个 $1$ ，是否到上界。

P3147 [USACO16OPEN]262144 P

模拟赛原题。

似乎有更简单的做法。反正我的做法就是先从小到大枚举一下当前是第几个数，设为 $k$，然后连续且都等于 $k$ 的块合并。如果是偶数，那么这个对左边和右边都有贡献。如果是奇数，作为分割点。每次递归（分治？）的时候记录左边和右边有几个等于 $k$ 的。

然后只有一个块之类的特判一下？

比较抽象，就贴个代码好了。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,a[maxn],rt[maxn];
struct node{
	int l,r;
	node(int a=0,int b=0) {l=a;r=b;}
};
inline int solve(int deep,int l,int r,int numl,int numr) {
	if (l>r) return 0;
	assert(deep<=40);
//	gdb(deep,l,r,numl,numr);
//	if (l==r) return a[l]+(int)log2(numr+numl+1); 
	int i,tot=1,ans=0,tmp,j;
	vector<node>g;
	g.push_back(node(0,0));
	g.push_back(node(l-numl,l-1));
//	g[1].l=l-numl,g[1].r=l-1;
	for (i=l;i<=r;i++) {
		if (a[i]==deep) {
			if (g[tot].r==i-1) g[tot].r++;
			else ++tot,g.push_back(node(i,i));//g[tot].l=g[tot].r=i;
		}
	}
	if (g[tot].r==r) g[tot].r+=numr;
	else ++tot,g.push_back(node(r+1,r+numr));//g[tot].l=r+1,g[tot].r=r+numr;
	if (tot==1) return deep+(int)(log2(g[1].r-g[1].l+1));
	int las=1;
	for (i=2;i<=tot;i++) {
		if (i!=tot&&(g[i].r-g[i].l+1)%2==0) continue;
		int cnt=g[las].r;
		for (j=g[las].r+1;j<=g[i].l-1;j++) {
			if (a[j]==deep&&rt[cnt]==deep) rt[cnt]=deep+1;
			else rt[++cnt]=a[j];
		}
		for (j=g[las].r+1;j<=cnt;j++) a[j]=rt[j];
		int tmp=solve(deep+1,g[las].r+1,cnt,(g[las].r-g[las].l+1)/2,(g[i].r-g[i].l+1)/2);
		ans=max(ans,tmp);las=i;
	}
	return ans; 
}
signed main(void){
	int i;
	read(n);for (i=1;i<=n;i++) read(a[i]);
	printf("%d",solve(1,1,n,0,0));
	return 0;
}

P4127 [AHOI2009]同类分布

考虑到各位数字之和最大只有 $9\times \log_{10}N=9\times 18$ ，所以枚举各位数字之和，记为 $mod$。

记录当前在第几位，当前数字模 $mod$ 的值，当前各位数字之和，是否到上界。

P4124 [CQOI2016]手机号码

板子。

P3413 SAC#1 - 萌数

如果有回文串，那么必定有长度为 $2$ 或者 $3$ 的回文子串。

这题还需要记录是否有前导 $0$。

P6754 [BalticOI 2013 Day1] Palindrome-Free Numbers

双倍经验。

P3311 [SDOI2014] 数数

先对于集合中的数建 AC自动机。

记录当前第几位，在AC自动机上的状态，是否。如果当前在AC自动机上的状态是某个串的结尾，则直接返回 $0$。

贴个代码.

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1505
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int mod=1e9+7;
struct yyy{
	int flag,fail,nex[11];
}a[1505*10];
int root,n,m,cnt;
inline void insert(string s) {
	int i,len=s.size(),now=root;
	for (i=0;i<len;i++) {
		if (!a[now].nex[s[i]-'0']) a[now].nex[s[i]-'0']=++cnt;
		now=a[now].nex[s[i]-'0'];
	}
	a[now].flag=1;
//	gdb(now); 
}
queue<int>q;
inline void getfail(void) {
	int i;
	for (i=0;i<=9;i++) if (a[root].nex[i]) q.push(a[root].nex[i]);
	while (!q.empty()) {
		int x=q.front();q.pop();
		for (i=0;i<=9;i++) 
			if (a[x].nex[i]) a[a[x].nex[i]].fail=a[a[x].fail].nex[i],q.push(a[x].nex[i]);
			else a[x].nex[i]=a[a[x].fail].nex[i];
	}
}
string c[105];
int f[1202][1505],nums[maxn],tot;
inline int dfs(int now,int pus,int lim,int lead) {
	if (a[pus].flag) return 0;
	if (lead) pus=0;
	if (now>tot) {
		return 1;
	}
	if (!lim&&!lead&&f[now][pus]!=-1) return f[now][pus]; 
	int i,ret=0,res=lim?nums[now]:9;
	for (i=0;i<=res;i++) {
		ret+=dfs(now+1,a[pus].nex[i],lim&&i==res,lead&&i==0);ret%=mod;
	}
	return lim?ret:f[now][pus]=ret;
}
signed main(void){
	string sn;
	memset(f,-1,sizeof(f));
	int i;
	cin>>sn;read(m);
	for (i=1;i<=m;i++) cin>>c[i],insert(c[i]);
	getfail();
	for (tot=sn.size(),i=1;i<=tot;i++) nums[i]=sn[i-1]-'0';
	printf("%lld",(dfs(1,0,1,1)+mod-1)%mod);
	return 0;
}

CF1710C XOR Triangle

对于 $x,y,z$ 上同一位的 $a,b,c$ ，我们发现 $a\bigoplus b+b\bigoplus c \ge a\bigoplus c$，所以只要满足 $a\bigoplus b+b\bigoplus c > a\bigoplus c$ ，即可保证 $x\bigoplus y+y\bigoplus z > x\bigoplus z$ 。

显然这个式子是轮换的，所以说当且仅当满足三个条件的数可以被记录答案。

因为是二进制下的数，所以如果没有记忆化是否达到上界多出来的常数是不可忽略的。就多开三维分别记录一下。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int mod=998244353;
int f[maxn][2][2][2][2][2][2];
int nums[maxn],tot;
inline int dfs(int now,int flag1,int flag2,int flag3,int lim1,int lim2,int lim3) {
//	gdb(now,flag1,flag2,flag3);
	if (now>tot) return flag1&&flag2&&flag3;
	if (f[now][lim1][lim2][lim3][flag1][flag2][flag3]!=-1) return f[now][lim1][lim2][lim3][flag1][flag2][flag3]; 
	
	int ret=0,i,j,k,x,y,z;
	for (i=0;i<=(lim1?nums[now]:1);i++)
		for (j=0;j<=(lim2?nums[now]:1);j++)
			for (k=0;k<=(lim3?nums[now]:1);k++){
				x=i^j;y=j^k;z=i^k;
				ret+=dfs(now+1,flag1|(x+y>z),flag2|(x+z>y),flag3|(y+z>x),lim1&&i==nums[now],lim2&&j==nums[now],lim3&&k==nums[now]);
				ret%=mod;
			}
	return f[now][lim1][lim2][lim3][flag1][flag2][flag3]=ret;
}
signed main(void){
	memset(f,-1,sizeof(f));
	int i;string s;
	cin>>s;tot=s.size();
	for (i=1;i<=tot;i++) nums[i]=s[i-1]-'0';
//	gdb(tot);
	printf("%lld",dfs(1,0,0,0,1,1,1));
	return 0;
}

CF55D Beautiful numbers

由 $1$ 到 $9$ 之中任意选取数的 $\text{lcm}$ 只有 $48$ 个，记为 $p$ ，尝试枚举。

记录当前在第几位，当前每位的 $\text{lcm}$ ，当前数模 $p$ 的值，是否达到上界。

复杂度是 $48\times 18 \times 48\times 2520\times T\times 2$ ，还不包括上界带来的常数，所以是不可接受的。

考虑去除枚举。记录当前在第几位，当前每位的 $\text{lcm}$ ，当前数模 $2520$ 的值，是否达到上界。

只要判断模 $2520$ 的值是否能被每位的 $\text{lcm}$ 整除即可。

然后发现如果每次都初始化会 TLE。

多出来的时间复杂度不仅仅在初始化上，更在于每次都需要重新计算。

因为我的写法把最高位设为 $1$ ，因为不同数位数不一样，所以 $1$ 所代表当前第几位也就不一样，不初始化就会 WA。解决这个问题，只需要将第一位设为个位，然后记忆化搜索的时候从高位到低位即可。

似乎代码还更加简洁了。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int nums[22],tot;
int id[2525],t[2525],cnt;
inline int gcd(int x,int y) {return !y?x:gcd(y,x%y);}
inline void init(int now,int sum) {
	if (now==10) return t[++cnt]=sum,void();
	init(now+1,sum/gcd(sum,now)*now);
	init(now+1,sum);
}
int f[23][51][2525];
int mod=2520;
inline int dfs(int now,int lcm,int sum,int lim) {
//	gdb(now,lcm,sum,lim,id[lcm]);
	if (!now) {
		if (sum%lcm==0) return 1;
		return 0;
	}
	if (!lim&&f[now][id[lcm]][sum]!=-1) return f[now][id[lcm]][sum];
	int res=lim?nums[now]:9,i,ret=0;
	for (i=0;i<=res;i++) {
		if (i) ret+=dfs(now-1,lcm/gcd(i,lcm)*i,(sum*10+i)%mod,lim&&i==res);
		else ret+=dfs(now-1,lcm,sum*10%mod,lim&&i==res);
	}
	return lim?ret:(f[now][id[lcm]][sum]=ret); 
}
inline int solve(int n) {
	if (n==0) return 1;
	int nw=n;tot=0;
	while (nw) nums[++tot]=nw%10,nw/=10;
	return dfs(tot,1,0,1);
}
signed main(void){
	int i,T,l,r;
	memset(f,-1,sizeof(f));
	init(1,1);
	sort(t+1,t+1+cnt);
	cnt=unique(t+1,t+1+cnt)-t-1;
	for (i=1;i<=cnt;i++) id[t[i]]=i;
	read(T);
	while (T--) {
		read(l);read(r);
		printf("%lld\n",solve(r)-solve(l-1));
	}
	return 0;
}