【Codeforces 814E】An unavoidable detour for home

相关链接

题目传送门:http://codeforces.com/contest/814/problem/E
官方题解:http://codeforces.com/blog/entry/52449
神犇题解Ⅰ:https://loj.ac/article/37
神犇题解Ⅱ:http://kczno1.blog.uoj.ac/blog/2660

解题报告

我们考虑分层图的话
那每一层的一个点一定会与上一层的某个点相连,剩下的度数只能层内消化
又因为这题对祖先有严格的限制,所以每一层都是原序列中连续的一段
于是$O(n^5)$的暴力$DP$就可以写了

至于$O(n^3)$的$DP$,就是$DP$套$DP$
预处理出转移的$buf$,然后转移的时候直接乘就好了
但这个预处理的时候要讨论很多情况啊,反正我自己考场上是想不出来的_(:з」∠)_

Code

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

const int N = 52;
const int MOD = 1000000007;
const int REV2 = 500000004;

int n, f[N][N], s2[N], s3[N], buf[N][N][N], C[N][N], prm[N]; 

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

int main() {
	n = read();
	f[read() + 1][1] = 1;
	for (int i = 2; i <= n; i++) {
		s2[i] = s2[i - 1];
		s3[i] = s3[i - 1];
		if (read() == 2) {
			s2[i]++;
		} else {
			s3[i]++;
		}
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	prm[2] = 1;
	for (int i = 3; i <= n; i++) {
		prm[i] = REV2;
		for (int j = 2; j < i; j++) {
			prm[i] = (LL)prm[i] * j % MOD;
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (i == 0 && j == 0 && k == 0) {
					buf[i][j][k] = 1;
				} else if (i == 0 && j == 0) {
					for (int l = 2; l < k; l++) {
						(buf[i][j][k] += ((LL)buf[i][j][k - 1 - l] * C[k - 1][l] % MOD) * prm[l + 1] % MOD) %= MOD;
					}
				} else if (i == 0) {
					buf[i][j][k] = j > 1? (LL)(j - 1) * buf[i][j - 2][k] % MOD: 0;
					(buf[i][j][k] += k? (LL)k * buf[i][j][k - 1] % MOD: 0) %= MOD;
				} else {
					buf[i][j][k] = j? (LL)j * buf[i - 1][j - 1][k] % MOD: 0;
					(buf[i][j][k] += k? (LL)k * buf[i - 1][j + 1][k - 1] % MOD: 0) % MOD;
				} 
			}
		}
	} 
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			if (f[i][j]) {
				int t2 = s2[i] - s2[j];
				int t3 = s3[i] - s3[j];
				for (int k = i + 1; k <= n; k++) {
					f[k][i] = (f[k][i] + (LL)f[i][j] * buf[k - i][t2][t3]) % MOD;
				}
			}
		}
	} 
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = (ans + (LL)f[n][i] * buf[0][s2[n] - s2[i]][s3[n] - s3[i]]) % MOD;
	}
	cout<<ans<<endl;
	return 0;
}

【BZOJ 4070】[APIO2015] 雅加达的摩天楼

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

这个题目,第一眼看就是最短路
然而O(n^2)条边真的是过不了
于是我们分类讨论,将p小于sqrt(n)的边全部建出来,p大于的暴力建
貌似叫分层图?还是看这里吧:http://blog.csdn.net/aarongzk/article/details/51195437?hmsr=toutiao.io
然而随便出一个数据就可以把这个做法搞死QAQ
管他的,卡过就好

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define NUM(p,f) (((p)-1)*(gap+1)+(f))
using namespace std;

const int N = 30005*110;
const int M = 30005*550;
const int INF = 0x3f;
const int inf = 0x3f3f3f3f;

struct Edge{int to,nxt,cost;}e[M];
int head[N],dis[N],inq[N],S,T,n,m,gap;
queue<int> que;

inline int read(){
	char c=getchar(); int 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 AddEdge(int u, int v, int c){
	static int TT = 0; e[++TT].cost = c; 
	e[TT].to = v; e[TT].nxt = head[u]; head[u] = TT;
}

inline int SPFA(int u, int v){
	memset(dis,INF,sizeof(dis));
	dis[u] = 0; que.push(u); inq[u] = 1;
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=e[i].nxt) if (dis[w]+e[i].cost < dis[e[i].to]) {
			int to = e[i].to;
			dis[to] = dis[w] + e[i].cost;
			if (!inq[to]) que.push(to), inq[to] = 1;
		}
	} 
	if (dis[v] == inf) return -1;
	else return dis[v];
}

int main(){
	n = read(); m = read(); gap = max(1,min(100,(int)sqrt(n))); 
	for (int i=1;i<=n;i++) for (int j=1;j<=gap;j++) AddEdge(NUM(i,j),NUM(i,0),0);
	for (int i=1;i<n;i++) for (int j=1;j<=gap;j++) if (i+j <= n) AddEdge(NUM(i,j),NUM(i+j,j),1); else break;
	for (int i=2;i<=n;i++) for (int j=1;j<=gap;j++) if (i-j > 0) AddEdge(NUM(i,j),NUM(i-j,j),1); else break; 
	for (int i=1,pos,rag;i<=m;i++) {
		pos = read()+1; rag = read();
		if (i == 1) S = NUM(pos,0); if (i == 2) T = NUM(pos,0);
		if (rag > gap) {
			for (int j=pos+rag,t=1;j<=n;j+=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
			for (int j=pos-rag,t=1;j>0;j-=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
		} else AddEdge(NUM(pos,0),NUM(pos,rag),0);
	} printf("%d\n",SPFA(S,T)); 
	return 0;
}