【BZOJ 3019】[Balkan2012] handsome

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3019
神犇题解:http://www.cnblogs.com/clrs97/p/6371367.html

解题报告

因为字典序大小这个东西实在是没有办法
所以我们根据它给的排列顺序来填数

这在原数列上的填充顺序是离散的
但考虑已经填了$i$个数,现在填第$i+1$个数
这大概是把一个空白的区间分成两份
于是我们预处理$f_{i,l,r}$表示长度为$i$,左右端点的字符分别为$l,r$的合法序列的方案数
这样我们就可以使用线段树在$O(\log n)$的时间复杂度内快速维护答案了

于是我们还是类比传统的数位DP,然后按照排列顺序往里加字符,使用线段树来维护答案
预处理的时间复杂度:$O(n)$,主程序的时间复杂度:$O(n \log n)$

【BZOJ 1442】[POI2006] Crystal

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1442
中文题解:http://www.shuizilong.com/house/archives/poi-xiii-stage-3-problem-crystals/

解题报告

首先我们定义“折越”:

这一位上可以选1,但选了0

如果我们从高位到低位考虑的话,如果有一位发生了折越,那之后的东西就可以随便取了
于是我们考虑在每一种方案第一次发生折越的时候将其统计进入答案
对每个数我们分情况讨论:

  1. 第i位只能填0
    那么剩下的位数的可能情况就有a & (1<<i)种辣
  2. 第i位可以发生折越
    那么不发生折越的情况同第一类
    发生折越之后,因为可以随便取,所以得乘上1<<i

这样的话,我们类似数位DP一样,从高位到低位依次DP就好
另外,此题没有取模的操作,需要用unsigned long long才能通过本题

Code

#include<bits/stdc++.h>
#define LL unsigned long long
using namespace std;

const int N = 59;

LL n,arr[N],vout;

int main() {
	cin>>n;
	for (int i=1;i<=n;i++) cin>>arr[i];
	for (int t=31;~t;t--) {
		LL f[3],t1,t2,od; od = 0;  
		f[0] = 1; f[1] = f[2] = 0;
		for (int i=1,tmp;i<=n;i++) {
			tmp = (arr[i] & ((1LL<<t) - 1)) + 1;
			if (arr[i] & (1LL<<t)) {
				od ^= 1;
				t1 = f[0] + (f[2] << t);
				t2 = f[1] << t; 
				f[0] *= tmp;
				(f[1] *= tmp) += t1;
				(f[2] *= tmp) += t2;
			} else {
				f[0] *= tmp;
 				f[1] *= tmp;
				f[2] *= tmp;
			}
		}
		if (od) {vout += f[1] - 1; break;}
		else vout += f[2];
	}
	cout<<vout;
	return 0;
}

【Codeforces 747F】Igor and Interesting Numbers

相关链接

题目传送门:http://codeforces.com/contest/747/problem/F
优雅的暴力:http://codeforces.com/blog/entry/49171?#comment-331886
官方题解:http://codeforces.com/blog/entry/49171
神犇代码:http://codeforces.com/contest/747/submission/23125896

解题报告

首先这题推一推式子发现答案最多9位的样子
于是我们就可以暴力搜索,用Meet in Middle来做就好

当然这题有更加清真的、类似数位DP的做法
假定我们能够做到给定字符串长度和每个数字可以用多少次,求有多少种合法情况的话
显然可以像数位DP一样,从高位到低位逐位确定每一位的数字应该是多少

现在问题转化为如何求的合法情况。
依次考虑每一种数字,显然对答案的贡献只与有多少个空位有关
于是f[i][j]表示现在考虑到第i种数字,还剩j个空位的方案数
这样的话,暴力转移即可。
时间复杂度:O(16^3+16*9)

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int k,t,C[21][21],res[21];
char ori[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline LL solve(int len, bool ty) {
	static LL f[2][20]; bool w,p;
	memset(f,0,sizeof(f));
	f[p=0][ty] = 1; w = 1; 
	for (int i=0;i<16;i++,w^=1,p^=1) {
		memset(f[w],0,sizeof(f[w]));
		for (int j=len;~j;j--) 
			for (int k=min(len-j,res[i]-(ty&(i==0)));~k;k--) 
				f[w][j+k] += f[p][j] * C[k][len-j];
	}
	return f[p][len];
}

int main() {
	for (int i=0;i<=20;i++) {
		C[0][i] = C[i][i] = 1;
		for (int j=1;j<i;j++) 
			C[j][i] = C[j-1][i-1] + C[j][i-1];
	}
	k = read(); t = read();
	for (int i=0;i<=15;i++) 
		res[i] = t;
	LL tmp; int len=1;
	while ((tmp = solve(len,0) - solve(len,1)) < k) 
		k -= tmp, len++;
	for (int i=len,ret=1;i;ret=0,i--) {
		res[ret]--;
		while ((tmp = solve(i-1,0)) < k) 
			res[ret++]++, res[ret]--, k -= tmp;
		printf("%c",ori[ret]);
	}
	return 0;
}

【算法笔记】数位DP

昨天以专题的形式再一次加强了数位DP
主要是以zky神犇的这一篇讲稿作为主线:
https://oi.qizy.tech/wp-content/uploads/2016/10/number_dp_by_zky.ppt

这一次最主要的收获就是学到了新的代码实现方式
之前一直是以预处理+询问的方式来写代码
这样的话,对于多组询问来讲,时间复杂度还不错
但代码实现复杂度简直没法接受
且对于部分题目,这样写起来会超级麻烦

新的写法无论实在时间复杂度还是编程复杂度上都很优越
以后应该会以这种代码作为主力辣!
给个参考:https://oi.qizy.tech/?p=1519

至于解题能力的话,似乎数位DP的要求不高?
不过能和AC自动机搞一起还是挺好玩哒:https://oi.qizy.tech/?p=1534

【CodeChef FAVNUM】Favourite Numbers

题目传送门:https://www.codechef.com/problems/FAVNUM
中文题面:number_dp_by_zky

这个题目还是挺好玩的!
数位DP配上AC自动机!别有一番风味!

然而这个傻Ⅹ的AC自动机写炸了
调试了3个小时! (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char pat[20];

namespace AC_Automaton{
	#define AC AC_Automaton
	LL f[20][2000][2];
	int ch[2000][10],tag[2000],cnt,fail[2000],sta[20];
	queue<int> que;
	
	inline void insert(char *s){
		int n = strlen(s+1), w = 0;
		for (int i=1,c;i<=n;i++) {
			c = s[i] - '0';
			if (!ch[w]) {
				ch[w] = ++cnt;
			}
			w = ch[w];
		}
		tag[w] = 1;
	}
	
	inline void Build(){
		for (int i=0;i<=9;i++) if (ch[0][i]) {
			que.push(ch[0][i]);
		}
		
		while (!que.empty()) {
			int w = que.front(); que.pop();
			for (int c=0;c<=9;c++) if (ch[w]) {
				int nv = ch[w], pv = fail[w];
				while (pv && !ch[pv]) pv = fail[pv];
				fail[nv] = ch[pv];
				tag[nv] |= tag[fail[nv]];
				que.push(nv);
			} else {
				ch[w] = ch[fail[w]];
			}
		}
	}
	
	LL DFS(int t, int w, bool lim, bool leg) {
		if (!t) {
			return leg;
		} else if (!lim && ~f[t][w][leg]) {
			return f[t][w][leg];
		} else {
			LL ret = 0;
			for (int i=0,ty=lim?sta[t]:9;i<=ty;i++) {
				ret += DFS(t-1, ch[w][i], lim&&i==sta[t], leg|tag[ch[w][i]]);
			}
			return lim? ret: f[t][w][leg] = ret;
		}
	}
	
	inline LL query(LL lim) {
		int cnt = 0;
		while (lim) {
			sta[++cnt] = lim % 10;
			lim /= 10;
		}
		memset(f,-1,sizeof(f));
		return DFS(cnt,0,1,0);
	}
};

int main(){	
	LL L,R,k,n,bas,w,stp;
	cin>>L>>R>>k>>n;
	for (int i=1;i<=n;i++) {
		scanf("%s",pat+1);
		AC::insert(pat);
	}
	
	AC::Build();
	k += AC::query(L - 1);
	if (AC::query(R) < k) {
		puts("no such number");
		exit(0);
	}
	
	stp = 1; w = L - 1; 
	while (stp < (R - L + 1)) stp <<= 1;
	while (stp) {
		if (AC::query(w + stp) < k) {
			w += stp;
		}
		stp >>= 1;
	}
	printf("%lld\n",w+1);
	return 0;
}

【BZOJ 1799】[Ahoi2009] self 同类分布

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1799

就是枚举模数然后搞一搞数位DP
%NanoApe,随便减一下枝就可以Rank1了:http://nanoape.is-programmer.com/posts/193348.html

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int MOD,sta[20];
LL f[20][170][170];

LL DFS(int t, int sum, int mod, bool lim) {
	if (sum > MOD) return 0;
	else if (!t) {
		return sum == MOD && !mod;		
	} else if (!lim && ~f[t][sum][mod]) {
		return f[t][sum][mod];
	} else {
		LL ret = 0;
		for (int i=0,ty=(lim?sta[t]:9);i<=ty;i++) {
			ret += DFS(t-1, sum+i, (mod*10+i)%MOD, lim&&i==sta[t]);
		}
		return lim? ret: f[t][sum][mod] = ret;
	}
}

inline LL cal(LL lim) {
	int cnt = 0;
	while (lim) {
		sta[++cnt] = lim % 10;
		lim /= 10;
	}
	if (cnt*9 < MOD) return 0;
	else return DFS(cnt,0,0,1);
}

int main(){
	LL a,b,vout=0; cin>>a>>b;
	for (int i=1;i<=162;i++) {
		memset(f,-1,sizeof(f));
		MOD = i;
		vout += cal(b);
		vout -= cal(a-1);
	}
	printf("%lld\n",vout);
	return 0;
}

【HDU 3709】Balanced Number

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3709
中文题面:http://blog.csdn.net/to_be_better/article/details/50731499

就是枚举一下平衡点,然后dp一下
另外……
我似乎真的爱上这种递归的写法了…..
7`XEKOC~R{6W$L~J1UPP9MX

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int sta[20];
LL f[20][20][1500];

inline LL read(){
	char c=getchar(); LL ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret;
}

LL DFS(int t, int crt, int val, bool ruf) {
	if (val < 0) return 0;
	else if (!t) {
		return !val;
	} else if (~f[t][crt][val] && !ruf) {
		return f[t][crt][val];
	} else {
		LL ret = 0;
		for (int i=0,lim=ruf?sta[t]:9;i<=lim;i++) {
			ret += DFS(t-1,crt,val+(t-crt)*i,ruf&&i==sta[t]);
		}
		return ruf? ret: f[t][crt][val] = ret;
	}
}

inline LL cal(LL lim) {
	int cnt = 0;
	while (lim) {
		sta[++cnt] = lim % 10;
		lim /= 10;
	}
	LL ret = 0;
	for (int i=1;i<=cnt;i++) {
		ret += DFS(cnt,i,0,1);
	}
	return ret - cnt + 1;
}

int main(){
	memset(f,-1,sizeof(f));
	for (int T=read();T;--T) {
		LL l = read(), r = read();
		printf("%I64d\n",cal(r)-((l>0)?cal(l-1):0));
	}
	return 0;
}

【Codeforces 55D】Beautiful numbers

题目传送门:http://codeforces.com/contest/55/problem/D
官方题解:http://codeforces.com/blog/entry/1109
中文题面:number_dp_by_zky

之前做数位dp的题目,一直强调数位间的独立性
然而现在看来,不独立也是可以上数位dp的

题解直接看上面给的“中文题面”里的题解吧,zky的题解真的是超级棒(๑•̀ㅂ•́)و✧
我来说一说代码实现的三种方式:

1)像之前的代码一样,先预处理,然后查询的时候在数组上搞一搞
优点:对于多组询问特别好用
缺点:因为是预处理,所以对于有些题目可能很麻烦,甚至不能预处理

2)对于每一次询问单独dp,记录是否达到上限
优点:代码好写(不用于处理,直接写一个dp就成)
缺点:多组询问没法处理

3)对于每一次询问DFS,如果这一位没有受到任何限制就记忆化
这种方法是我在看这位神犇的代码的时候看到的:http://codeforces.com/contest/55/submission/3692033
优点:代码更好写,且对于多组询问相对友好(仔细想一想,他的查询次数应该不会劣于方法1?)
缺点:如果位数特别大(什么1e5,1e6之类的),则效果可能不太好

总的来说,我似乎爱上了第三种写法 = ̄ω ̄=
以后数位dp的题应该是首选第三种吧!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int MOD[]={1,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520};
int pos[2530],lcm[50][50],sta[20]; 
LL f[20][50][2530];

LL GCD(LL a, LL b) {return b?GCD(b,a%b):a;}
LL LCM(LL a, LL b) {return a/GCD(a,b)*b;}


LL DFS(int t, int lm, int mod, bool top) {
	if (t == 0) {
		return !(mod % MOD[lm]);
	} else if (~f[t][lm][mod] && !top) {
		return f[t][lm][mod];	
	} else {
		LL ret = 0;
		for (int i=0,ty=(top>0?sta[t]:9),tmp;i<=ty;i++) {
			tmp = lcm[lm][i];
			ret += DFS(t-1,tmp,(mod*10+i)%2520,top&&i==sta[t]);
		}
		return top?ret:f[t][lm][mod] = ret;
	}
}

inline LL cal(LL lim) {
	int cnt = 0;
	while (lim) {
		sta[++cnt] = lim % 10;
		lim /= 10;
	}
	return DFS(cnt,1,0,1);
}

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	memset(f,-1,sizeof(f));
	for (int i=1;i<=48;i++) {
		pos[MOD[i]] = i;
	}
	for (int i=0;i<=48;i++) {
		for (int j=0;j<=48;j++) {
			lcm[i][j] = pos[LCM(MOD[i],MOD[j])];
		}
	} 
	for (int T=read();T;--T) {
		LL l = read(), r = read();
		printf("%I64d\n",cal(r)-cal(l-1));
	}
	return 0;
}

【BZOJ 4513】[SDOI2016] 储能表

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4513

先来%一波Menci的强行找规律(:з」∠)https://dn-menci.qbox.me/sdoi2016-table/
然后就是std用的数位DP:http://www.ruiker1997.tk/bzoj-4513

一直感觉这个题目的数位DP很牵强
于是一直尝试使用以前的数位DP的写法来写
然后发现,嘴巴ac还是挺容易的,但真要写出来,还真心不好写
于是代码就算了吧。

—– UPD 2016.9.29 —–
还是补一份代码吧
以前数位DP都不是这么写的
不过感觉这么写,如果没有多组询问还是挺清真的

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL f[62][2][2][2],g[62][2][2][2],n,m,MOD,k; 

int main(){
	int T; cin>>T; while (T--) {
		cin>>n>>m>>k>>MOD;
		memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
		g[61][0][0][0] = 1;
		for (int i=60;~i;i--) {
			int t1 = (n>>i)&1, t2 = (m>>i)&1, t3 = (k>>i)&1;
			for (int a=0;a<2;a++) for (int b=0;b<2;b++) for (int c=0;c<2;c++) if (g[i+1][a][b]) {
				for (int x=0,w,wa,wb,wc;x<2;x++) for (int y=0;y<2;y++) {
					if (w=x^y, (!a&&x>t1) || (!b&&y>t2) || (!c&&w<t3)) continue;
					wa = (a||x<t1); wb = (b||y<t2); wc = (c||w>t3);
					(g[i][wa][wb][wc] += g[i+1][a][b]) %= MOD;
					(f[i][wa][wb][wc] += ((f[i+1][a][b] + (((w-t3)*((1LL<<i)%MOD))%MOD)*g[i+1][a][b]%MOD)%MOD + MOD) % MOD) %= MOD;
				}
			}
		}	
		cout<<f[0][1][1][1]<<endl;
	}
	return 0;
}

【BZOJ 4521】[Cqoi2016] 手机号码

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4521
数据生成器:http://paste.ubuntu.com/23135878/
官方数据:http://pan.baidu.com/s/1hsqc4Va

这个题,瞄一眼就知道是数位DP
然而转移比较恶心,在考场上代码就写了两个小时
然而最后因为一个局部变量没有清零,结果wa得只剩一个点
为什么本机对拍不wa (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

LL f[12][10][5][5],l,r;

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

inline void prework(){
	for (int i=0;i<=9;i++) if (i != 4 && i != 8) f[1][i][1][0] = 1;
	f[1][4][1][1] = f[1][8][1][2] = 1;
	for (int i=2;i<=11;i++) for (int j=0;j<=9;j++) {
		if (j == 4) {
			for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) for (int ty=0;ty<=1;ty++) 
				f[i][j][1][1] += f[i-1][p][k][ty];
			f[i][j][2][1] = f[i-1][4][1][1];
			f[i][j][3][1] = f[i-1][4][2][1];
			for (int p=0;p<=9;p++) for (int ty=0;ty<=1;ty++)
				f[i][j][3][1] += f[i-1][p][3][ty];
		} else if (j == 8) {
			for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) f[i][j][1][2] += f[i-1][p][k][0] + f[i-1][p][k][2]; 
			f[i][j][2][2] = f[i-1][8][1][2];
			f[i][j][3][2] = f[i-1][8][2][2];
			for (int p=0;p<=9;p++) f[i][j][3][2] += f[i-1][p][3][0] + f[i-1][p][3][2];
		} else for (int t=0;t<=2;t++) {
			for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) f[i][j][1][t] += f[i-1][p][k][t];
			f[i][j][2][t] = f[i-1][j][1][t];
			f[i][j][3][t] = f[i-1][j][2][t];
			for (int p=0;p<=9;p++) f[i][j][3][t] += f[i-1][p][3][t];
		}
	}
}

inline bool judge(LL w) {
	static int dig[15]; bool t1=0,t4=0,t8=0;
	for (int i=1;i<=11;i++) dig[i] = w % 10, w /= 10;
	for (int i=1;i<=11;i++) if (dig[i] == 4) t4 = 1;
	for (int i=1;i<=11;i++) if (dig[i] == 8) t8 = 1;
	for (int i=3;i<=11;i++) if (dig[i] == dig[i-1] && dig[i-1] == dig[i-2]) t1 = 1;
	return t1 && !(t4 && t8);
}

inline LL cal(LL lim) {
	LL ret = 0; bool t4=0, t8=0, CNT=0; static int dig[15];
	for (int i=1;i<=11;i++) dig[i] = lim % 10, lim /= 10;
	
	for (int i=1;i<dig[11];i++) for (int ty=0;ty<=2;ty++) ret += f[11][i][3][ty];
	for (int k=10;k;k--) {
		if (dig[k+1] == 4) t4 = 1; if (dig[k+1] == 8) t8 = 1;
		if (t4 && t8) break;
		
		int cnt = 1; for (int w=k+2;w<=11;w++) if (dig[w] != dig[k+1]) break; else cnt++;
		if (cnt >= 3) CNT = 1;
		
		for (int j=0,tmp=(k!=1);j<=dig[k]-tmp;j++) 
			if (CNT) for (int t=1;t<=3;t++) {
				ret += f[k][j][t][0];
				if (!t4) ret += f[k][j][t][2];
				if (!t8) ret += f[k][j][t][1];
			} else {
				if (dig[k+1] == j) {
					int stp = max(1,3-cnt);
					for (int t=stp;t<=3;t++) {
						ret += f[k][j][t][0];
						if (!t4) ret += f[k][j][t][2];
						if (!t8) ret += f[k][j][t][1];
					}
				} else {
					ret += f[k][j][3][0];
					if (!t4) ret += f[k][j][3][2];
					if (!t8) ret += f[k][j][3][1];
				}
			}
	} 
	return ret;
}

int main(){
	prework();
	l = read(); r = read();
    cout<<cal(r)-cal(l)+judge(l);
	return 0;
}