【HDU 1693】Eat the Trees

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1693

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 5000;

LL f[12][12][MAXN];
int MX,n,m,mat[12][12];

int main(){
	int TT; cin>>TT;
	for (int T=1;T<=TT;T++) {
		scanf("%d%d",&m,&n); MX =1<<n+1;
		for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) 
			scanf("%d",&mat[i][j]),memset(f[i][j],0,sizeof(f[i][j]));
		
		
		if (mat[1][1]) f[1][1][3] = 1;
		else f[1][1][0] = 1;
		for (int j=1;j<=m;j++) { 
			for (int i=1;i<n;i++) {
				for (int k=0;k<MX;k++) if (f[i][j][k]) {
					bool up=k&(1<<i+1), left=k&(1<<i);
					if (mat[i+1][j]) {
			 			if (up && left) f[i+1][j][k^(1<<i)^(1<<i+1)] += f[i][j][k];
						else if (up || left) {
							f[i+1][j][k] += f[i][j][k];
							f[i+1][j][k^(1<<i+1)^(1<<i)] += f[i][j][k];	
						} else {
							f[i+1][j][k^(1<<i+1)^(1<<i)] += f[i][j][k];
						}
					} else {
						if (!up && !left) f[i+1][j][k] += f[i][j][k];
					} 
				} 
			}
			for (int k=0;k<MX;k++) if (f[n][j][k] && (k&(1<<n)) == 0) {
				int up = k & 1;
				if (mat[1][j+1]) {
					if (up) {
						f[1][j+1][((k^1)<<1)^1] += f[n][j][k];
						f[1][j+1][((k^1)<<1)^2] += f[n][j][k];
					} else {
						f[1][j+1][(k<<1)^3] += f[n][j][k];
					}
				} else {
					if (!up) f[1][j+1][k<<1] += f[n][j][k];
					else continue;
				}
			}
		}  
		printf("Case %d: There are %I64d ways to eat the trees.\n",T,f[n][m][0]);
	} 
	return 0;
} 

【POJ 2411】Mondriaan’s Dream

题目传送门:http://poj.org/problem?id=2411

轮廓线dp

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = (1<<12)+9;

int n,m;
LL f[2][MAXN];

int main(){
	while (scanf("%d%d",&n,&m) && (n || m)) {
		int now=1, pre=0, MX=1<<n;
		memset(f[now],0,sizeof(f[now]));
		f[now][0] = 1;
		
		for (int j=1;j<=m;j++) {
			for (int i=1;i<=n;i++) {
				swap(now, pre);
				memset(f[now],0,sizeof(f[now]));
				for (int k=0;k<MX;k++) if (f[pre][k]) {
					f[now][k^(1<<i-1)] += f[pre][k];
					if (i > 1 && k&(1<<i-2) && !(k&(1<<i-1)))
						f[now][k^(1<<i-2)] += f[pre][k];
				}
			}
		}
		printf("%lld\n",f[now][0]);
 	}
	return 0;
} 

【HDU 2089】不要62

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2089

还是数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 10;

int f[MAXN][MAXN];

inline void prework(){
	for (int i=0;i<=9;i++) f[1][i] = (i != 4);
	for (int k=2;k<=6;k++) {
		for (int i=0;i<=9;i++) {
			if (i == 4) continue;
			else for (int j=0;j<=9;j++) 
				if (i == 6 && j == 2) continue;
				else f[k][i] += f[k-1][j];
		}
	}
}

inline int cal(int w){
	if (!w) return 0;
	
	int ret=0,tot=0,arr[MAXN];
	memset(arr,0,sizeof(arr));
	while (w) arr[++tot] = w % 10, w /= 10;
	
	for (int i=tot-1;i;i--) for (int j=1;j<=9;j++) ret += f[i][j];
	for (int i=tot;i;i--) {
		for (int j=(i==tot?1:0);j<arr[i];j++) 
			if (arr[i+1] == 6 && j == 2) continue;
			else ret += f[i][j];
		if ((arr[i] == 2 && arr[i+1] == 6) || arr[i] == 4) break;
		else if (i == 1) ret ++;
	}
	return ret;
} 

int main(){
	prework(); int a,b;
	while (scanf("%d%d",&a,&b) && (a || b)) 
		printf("%d\n",cal(b)-cal(a-1));	
	return 0;
}

【BZOJ 1833】[ZJOI2010] count 数字计数

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

仍然是数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 20;

LL f[MAXN][MAXN][MAXN],ans[MAXN],p[MAXN];

inline void prework(){
	p[0] = 1; p[1] = 10; 
	for (int i=2;i<=12;i++) p[i] = p[i-1]*10;
	for (int i=0;i<=9;i++) f[1][i][i] = 1;
	for (int k=2;k<=12;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=0;j<=9;j++) {
				for (int h=0;h<=9;h++) {
					f[k][i][h] += f[k-1][j][h];
				}
			}
			f[k][i][i] += p[k-1];
		}
	}
}

inline void cal(LL w, int t){
	if (!w) return;
	else {
		int tot = 0, arr[20]; LL tmp = w;
		memset(arr,0,sizeof(arr));
		while (w) arr[++tot] = w % 10, w /= 10;
	
		for (int i=tot-1;i;i--) for (int j=1;j<=9;j++) 
			for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
		for (int i=tot;i;i--) {
			for (int j=(i==tot?1:0);j<=arr[i]-(i==1?0:1);j++) 
				for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
			if (i>1) ans[arr[i]] += (tmp % p[i-1] + 1)*t;
		}
	}
}

int main(){
	prework();
	LL a,b; cin>>a>>b;
	cal(b,1); 
	cal(a-1,-1);
	for (int i=0;i<9;i++) printf("%lld ", ans[i]);
	printf("%lld",ans[9]);
	return 0;
} 

【HDU 3555】Bomb

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3555

数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;

const int MAXN = 30;

LL f[MAXN][MAXN][2];

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;
}

inline void prework(){
	for (int i=0;i<=9;i++) f[1][i][0] = 1;
	for (int k=2,tmp=0;k<=28;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=0;j<=9;j++) {
				if (i == 4 && j == 9) f[k][i][1] += f[k-1][j][0];
				else f[k][i][0] += f[k-1][j][0];
				f[k][i][1] += f[k-1][j][1];
			}
		}
	}
}

inline LL cal(LL w){
	if (!w) return 0;
	else { 
		int tot = 0, arr[20]; LL ret = 0, tmp = w, t2;
		memset(arr,0,sizeof(arr));
		while (w) arr[++tot] = w % 10, w /= 10;
	
		for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j][1];
		for (int i=1;i<arr[tot];i++) ret += f[tot][i][1];
		for (int i=tot-1;i;i--){
			for (int j=0;j<arr[i];j++) ret += f[i][j][1];
			if (arr[i+1] == 4 && arr[i] == 9) {
				ret += tmp%(LL)(pow(10,i-1)+0.1)+1;
				break;
			}
		}
		return ret;
	}
}

int main(){
	prework();
	int T; T = read();
	while (T--) {
		LL a=read();
		cout<<cal(a)<<endl;
	}
	return 0;
} 

【BZOJ 1026】[SCOI2009] windy数

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

数位DP

#include<iostream>
#include<cstdio>
#include<cstring>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 20;

int f[MAXN][MAXN],a,b;

inline void prework(){
	for (int i=0;i<=9;i++) f[1][i] = 1;
	for (int k=2;k<=10;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=i+2;j<=9;j++) f[k][i] += f[k-1][j];
			for (int j=i-2;j>=0;j--) f[k][i] += f[k-1][j];
		}
	}
}

inline int cal(int w){
	int tot=0,arr[MAXN],ret=0;
	memset(arr,0,sizeof(arr));
	while (w) arr[++tot] = w % 10, w /= 10;
	
	for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j];
	for (int i=1;i<arr[tot];i++) ret += f[tot][i];
	for (int i=tot-1;i>0;i--) {
		for (int j=0;j<=arr[i]-(i==1?0:1);j++)if (abs(j-arr[i+1]) >= 2) ret += f[i][j];
		if (abs(arr[i]-arr[i+1]) < 2) break;
	}
	return ret+(tot==1);
}

int main(){
	prework();
	scanf("%d%d",&a,&b); 
	printf("%d",cal(b)-cal(a-1));
	return 0;
} 

【BZOJ 1076】[SCOI2008] 奖励关

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1076
数据生成器:http://paste.ubuntu.com/20577780/

概率DP第一题! 撒花~ *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
虽然想了很久很久,做了一个下午,但彻底懂啦!

设f[i][k]为状态为i,走了k步时到终点的期望得分
根据全期望公式,得到以下转移方程:
\(f[i][k] = \sum\limits_{j = 1}^n {{p_j} \cdot \max ((f[i|{2^{j – 1}}][k + 1] + val[j]) \cdot ((i\& \lim [j]) = = \lim [j]),f[i][k + 1])}\)
其中直接取max的正确性在于:只要是合法的状态,那么最后都会被计入答案
然后根据DAG的性质,倒着递推即可。

但今天想了一下午,不仅相同了这个,还有更重要的收获:
为什么不能正着推?
不是网上说的会推出无效的状态,而是:
题目上只给了\({P_{(u \to v)}}\),而没有给\({P_{(v \to u)}}\)
而且\({P_{(v \to u)}}\)你还算不出来,因为分母不确定(受转移的影响)。
所以你只能按照上面的方式列方程,进而只能倒推

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 80000;
const int KK = 100+9;

int val[MAXN],n,K,ty[MAXN],MX,lim[MAXN];
double f[KK][MAXN];

int main(){
	scanf("%d%d",&K,&n);
	for (int i=1;i<=n;i++) ty[i] = 1<<(i-1);
	for (int i=1,tmp;i<=n;i++) {
		scanf("%d",&val[i]);
		while (scanf("%d",&tmp) && tmp)
			lim[i] |= ty[tmp];
	}
	MX = ty[n]*2-1;
	
	for (int k=K;k;k--) for (int i=0;i<=MX;i++) for (int j=1;j<=n;j++) 
		f[k][i] += max((f[k+1][i|ty[j]]+val[j])*((i&lim[j]) == lim[j]),f[k+1][i])/n;
	
	printf("%.6lf",f[1][0]);
	return 0;
}	

【NOI六连测】[D6T1] 互质

题目传送门:http://pan.baidu.com/s/1eR1sqXk
离线版题目:http://paste.ubuntu.com/18699825/
数据传送门:http://pan.baidu.com/s/1o8pgYZg

这个题目,暴力的状压很容易想到,然而质因数太多,数组开不下 QAQ
于是考试的时候,码个暴力就闪人了。一看题解,真的是好妙啊!o( ̄▽ ̄)ブ

我们只拆分33以内的质因数,这里只有12个,可以承受。
这么干,还有一个好处:对于一个1k以内的数,超过33的质因数只可能有一个
也就是说,我们对于任意一个数,分两种情况讨论:
1)只有33以内的质因数:这样的话,直接暴力转移即可
2)有33以上的质因数:将拥有相同的、大于33的质因数的数存成一组,像分组背包一样一起转移
因为大于33的质因数只可能有一个,而相同的存在了一起,所以只要保证小于34的质因数不重合即可

此题真的是妙啊!

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 5000;
const int LIM = 4500;
const int N = 12;

int sed[]={0,2,3,5,7,11,13,17,19,23,29,31,33};
int n,que[MAXN][MAXN],cnt[MAXN];
int t1[MAXN],t2[MAXN],*f,*g;

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

int main(){
	freopen("prime.in","r",stdin);
	freopen("prime.out","w",stdout);
	n = read();
	f=t1; g=t2;
	
	for (int i=1,a;i<=n;i++){
		a = read();
		int tmp = a, buf = 0;
		for (int i=1;i<=N;i++) if (!(tmp%sed[i])) {
			while (!(tmp%sed[i])) tmp /= sed[i];
			buf |= 1<<(i-1);
		} 
		if (tmp != 1) que[tmp][++cnt[tmp]] = buf;
		else for (int i=1;i<=LIM;i++) if (!(i&buf)) 
			f[i|buf] = max(f[i|buf], f[i]+1);
	}
	
	for (int i=1;i<=1000;i++){
		for (int k=1;k<=LIM;k++) g[k] = f[k];
		for (int j=1;j<=cnt[i];j++)	for (int k=1;k<=LIM;k++)
			if (!(k&que[i][j])) g[k|que[i][j]] = max(g[k|que[i][j]], f[k]+1);		
		swap(g,f);
	}
	
	int vout = 1;
	for (int i=1;i<=LIM;i++)
		vout = max(vout, f[i]);
	printf("%d\n",vout);
	
	return 0;
}	

—————————— UPD 2017.2.1 ——————————
总感觉这个题DLX可以暴力过的样子
有没有同学有空写写啊!

【NOI六连测】[D4T1] 数学

题目传送门:http://pan.baidu.com/s/1eRRG6Wy
离线版题目:http://paste.ubuntu.com/18459243/
数据传送门:http://pan.baidu.com/s/1miarNuS

这一道题目,真的是十分可惜。考试前一个小时,码完了O(K*n^2) 的暴力DP,但一直到考试结束前9分钟才推出斜率DP的式子。
本来以为斜率DP可以随便切了QAQ,现在来看,代码实现确实不恼火了,但是推式子还是很恼火啊!
这一道题目,式子推出来之后,也就没什么好说的了。先贴一贴斜率DP的代码,后续再来更决策单调,和神奇的二分的代码。

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int K = 50+9;

double x[K][MAXN/2],y[K][MAXN/2],rev[MAXN],ret,arr[MAXN];
int AA[MAXN],n,k,l[K],r[K],pos[K][MAXN/2]; 

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

#define slope(t,b,a) (y[t][a]-y[t][b])/(x[t][a]-x[t][b])

inline void update(int t, double X, double Y, int i){
	int tmp = r[t]+1; x[t][tmp]=X; y[t][tmp]=Y;
	while (l[t] < r[t]) if (slope(t,r[t],tmp) > slope(t,r[t]-1,r[t])) r[t]--;
		else break;
	x[t][++r[t]] = X; y[t][r[t]] = Y; pos[t][r[t]] = i;
}

inline double Get(int t, int w){
	while (l[t] < r[t]) if (slope(t,l[t],l[t]+1) > rev[w+1]) l[t]++;
		else break;
	return (arr[w]-arr[pos[t][l[t]]])*rev[w+1]+y[t][l[t]];
}

int main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	n = read(); k = read()-1;
	for (int i=1;i<=n;i++) AA[i] = read();
	for (int i=1;i<=n;i++) arr[i] = (double)AA[i]+arr[i-1];
	for (int i=n;i;i--) rev[i] = rev[i+1] + (double)1/AA[i]; 
	for (int i=1;i<=n;i++) ret += (double)AA[i]*rev[i];
	for (int i=0;i<=k;i++) l[i] = 1;
	
	for (int w=1;w<n;w++){
		for (int i=1;i<k;i++) if (r[i]) 
			update(i+1,arr[w],Get(i,w),w);
		update(1,arr[w],arr[w]*rev[w+1],w);
	} 
	double vout = 0;
	for (int i=l[k];i<=r[k];i++)
		vout = max(vout, y[k][i]);
	printf("%.15lf\n",ret - vout);
	return 0;
} 

【NOI六连测】[D3T1] 炉石

题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版数据:http://paste.ubuntu.com/18386939/
数据传送门:http://pan.baidu.com/s/1i5fN2IT

首先,没玩过炉石的同学表示很受伤:考试的时候一直以为95颗星就算赢
其次,不会概率DP or 高斯消元的同学表示很受伤:因为要爆零啊!QAQ
好吧,高斯消元不会,所以来说一说lcr用的模拟吧:
设arr[i][j]表示走了k步后,位于当前有i颗星,已经连胜j场这个状态的概率
于是转移一下,再加上P>0.48保证了最多的步数就是1000多的样子
所以我们暴力转移1e5次的样子,基本上其他地方的DP值就为0了。
然后就是NOIP的模拟题水平的代码就可以了! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
哎,概率太弱不对,是完全不会
迟早是要找个时间好好学一学啊!

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100;
const int T = 100000;

double win,lose,arr[MAXN][4],tmp[MAXN][4],ans;
int n;

int main(){
	freopen("hearthstone.in","r",stdin);
	freopen("hearthstone.out","w",stdout);
	scanf("%d%lf",&n,&win);
	lose = 1 - win;
	arr[96-n][0] = 1;
	for (int k=1;k<=T;k++){
		for (int i=0;i<=10;i++){
			tmp[i][0] += arr[i][0]*lose;
			tmp[i][0] += arr[i][1]*lose;
			tmp[i][0] += arr[i][2]*lose;
			tmp[i][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=11;i<=70;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=71;i<=95;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+1][3] += arr[i][2]*win;
			tmp[i+1][3] += arr[i][3]*win;
		}
		ans += (tmp[96][0]+tmp[96][1]+tmp[96][2]+tmp[96][3])*k; 
		memcpy(arr,tmp,sizeof(tmp));
		memset(tmp,0,sizeof(tmp));
	}
	printf("%.2lf\n",ans);
	return 0;
} 

【BZOJ 3790】神奇项链

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3790
离线版题目:http://paste.ubuntu.com/17470379/
吐槽:板题,直接上代码不解释

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 120000;

char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];

namespace FenwickTree{
	#define BIT FenwickTree
	#define low(x) (x&(-x))
	#define INF 1000000000
	int arr[MAXN],buf[MAXN];

	inline void init(){
		for (int i=1;i<=n;i++)
			arr[i] = buf[i] = INF;
	}

	inline int query(int left, int right){
		if (right < left) return INF; else { int ret = INF; while (right >= left){
				if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
				else ret = min(ret,buf[right]), right--;
			}
			return ret;
		}
	}

	inline void modify(int pos, int nv){
		if (buf[pos] > nv) {
			buf[pos] = nv;
			for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
				else break;
		} else return;
	}
};

inline bool sort_cmp(const int &A, const int &B){
	return r[A] < r[B];
}

inline int manacher(){
	int m=n*2+1,itr=0;
	for (int i=1;i<=n;i++)
		chr[i*2-1] = '@',
		chr[i*2] = pat[i];
	chr[m] = '@'; chr[m+1] = '#'; chr[0] = '$';

	for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i)  len[i] = min(len[2*itr-i],itr+len[itr]-i);
		else len[i] = 0;
		p1 = i-len[i]; p2 = i+len[i];
		while (chr[--p1] == chr[++p2]) len[i]++;
		if (itr+len[itr] < i+len[i]) itr = i;
	}

	for (int i=1;i<=m;i++)
		r[i] = i+len[i],
		l[i] = i-len[i],
		ord[i] = i;
	sort(ord+1,ord+m,sort_cmp);

	n = m; BIT::init(); BIT::modify(1,0);
	for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
		tmp = BIT::query(l[i],r[i]-1)+1;
		BIT::modify(r[i],tmp);
	}

	return BIT::query(m-1,m)-1;
}

int main(){
	while (~scanf("%s",pat+1)){
		n = strlen(pat+1);
		printf("%dn",manacher());
	}
	return 0;
}