VEXOBEN
Vexoben
Apr 3, 2019
It takes 40 minutes to read this article.

终于意识到动规的水平差得一批了。这边开个小专题练一下。

题目列表是学长 frank_c1 的博客。这样一来可以保证质量,二来也有自己能看懂的题解。

事实上很多题意也是贺的

这里还是挂个链接吧:orz

(刷新以获取数学公式)

[APIO 2014] Beads and wires

题意

在达芬奇时代,有一个流行的儿童游戏称为连珠线。当然,这个游戏是关于珠子和线的。线是红色或蓝色的,珠子被编号为。这个游戏从一个珠子开始,每次会用如下方式添加一个新的珠子:

  • :一个新的珠子 和一个已经添加的珠子 用红线连接起来。
  • :一个新的珠子 插入到用红线连起来的两个珠子 , 之间。具体过程是删去 , 之间红线,分别用蓝线连接 ,,

每条线都有一个长度。游戏结束后,你的最终得分为蓝线长度之和。

给你连珠线游戏结束后的游戏局面,只告诉了你珠子和链的连接方式以及每条线的长度,没有告诉你每条线分别是什么颜色。

你需要写一个程序来找出最大可能得分。即,在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的,然后输出最大可能得分。

数据范围:

题解

如果确定一个点为根,我们可以且仅可以进行一个操作:选择两条有父子关系的边,将他们同时染蓝。

就是枚举根,表示这棵子树中,到它父亲这条边 用了/没用 能产生的最大贡献。

方程列出来发现可以换根,操作一下就做完了。

(事实上我一开始用点分治做了换根做的事情,虽然本质上一样,但是一个上午都没调出来)

#include<bits/stdc++.h>
#define LL long long
#define pii pair<LL, LL>
using namespace std;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;

int n, m, E;
int fir[N], nex[N << 1], arr[N << 1], len[N << 1], flen[N];
LL ans, f[N][2];
set<pii> Set[N];

void Add_Edge(int x, int y, int l) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y; len[E] = l;
}

void dfs(int x, int fa) {
	f[x][0] = f[x][1] = 0;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		int y = arr[i];
		flen[y] = len[i];
		dfs(y, x);
		f[x][1] += max(f[y][0], f[y][1]);
		Set[x].insert(make_pair(max(f[y][0], f[y][1]) - flen[y] - f[y][1], arr[i]));
	}
	if (Set[x].size()) {
		f[x][0] = f[x][1] - (Set[x].begin() -> first) + flen[x];
	}
}

void dfs2(int x, int fa) {
	ans = max(ans, f[x][1]);
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		int y = arr[i];
		LL f0 = f[y][0], f1 = f[y][1];
		f[x][1] -= max(f0, f1);
		Set[x].erase(make_pair(max(f0, f1) - len[i] - f[y][1], y));
		f[x][0] = 0;
		if (Set[x].size()) {
			f[x][0] = f[x][1] - (Set[x].begin() -> first) + len[i];
		}
		f[y][1] += max(f[x][0], f[x][1]);
		f[y][0] = f[y][1];
		Set[y].insert(make_pair(max(f[x][0], f[x][1]) - len[i] - f[x][1], x));
		dfs2(y, x);
		Set[y].erase(make_pair(max(f[x][0], f[x][1]) - len[i] - f[x][1], x));
		f[y][1] = f1;
		f[y][0] = f0;
		f[x][1] += max(f0, f1);
		Set[x].insert(make_pair(max(f0, f1) - len[i] - f[y][1], y));
		f[x][0] = f[x][1];
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int x, y, l;
		scanf("%d%d%d", &x, &y, &l);
		Add_Edge(x, y, l);
		Add_Edge(y, x, l);
	}
	dfs(1, 0);
	dfs2(1, 0);
	cout << ans << endl;
	return 0;
}

[ZJOI 2017] 仙人掌

题意

给定边的简单无向连通图。

现在要在图上加若干边,要求加边后还是一个简单无向连通图,且每条边至多属于一个简单环。

求加边方案数对取模的值。

,

题解

如果原图是不是仙人掌,答案为

一张图为仙人掌当且仅当树上的边最多被非树边覆盖次。

已经被覆盖过的树边不能再次被覆盖。直接断开这些边,问题就转化为树上的情况。

因为不能有重边,所以问题就相当于:选出若干长度不小于的路径,每条边不能被覆盖超过次,求方案数。

这里一个关键的转化是,上述问题等价于:用若干条长度不小于的路径,覆盖每条边恰好一次。

表示子树的答案,表示子树中,存在且仅存在一条从引下的链,其余边都被覆盖的方案数。

这里我转移时又糊了假算法。我加入一棵子树后直接转移,如果保留了来自的链,现在加入子树,要么连转移到,要么连转移到,但是忽略了可以同时保留两条链,分别和后面两条相连的情况,于是过不了大样例

转移时先处理出一个数组表示棵子树,每棵子树有条从引下的链,处理到所有边都被覆盖的方案数。

转移就很显然了,设的儿子个数为

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int M = 2e6 + 10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;

int n, m, E;
int h[N], f[N], g[N], vis[N], tag[N];
int fir[N], nex[M], arr[M], del[M], dep[N];

inline void Add_Edge(int x, int y) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y; del[E] = 0;
}

int dfs(int x, int pre) {
	int res = 0;
	vis[x] = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (!vis[arr[i]]) {
			dep[arr[i]] = dep[x] + 1;
			res += dfs(arr[i], i);
		}
		else if ((i ^ 1) != pre && vis[arr[i]] && dep[x] > dep[arr[i]]) {
			++res, --tag[arr[i]];
			del[i] = 1;
			del[i ^ 1] = 1;
		}
	}
	res += tag[x];
	if (res) {
		del[pre] = 1;
		del[pre ^ 1] = 1;
	}
	if (res > 1) return -inf;
	return res;
}

int add(register int x, register int y) {
	static int z;
	return ((z = (x + y)) >= mod) ? z - mod : z;
}

void dfs2(int x) {
	vis[x] = 1;
	int cnt = 0, s = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (vis[arr[i]] || del[i]) continue;
		dfs2(arr[i]);
		++cnt;
		s = 1LL * s * g[arr[i]] % mod;
	}
	if (!cnt) {
		f[x] = 1;
		g[x] = 1;
	}
	else if (cnt) {
		f[x] = 1LL * s * h[cnt] % mod;
		g[x] = add(f[x], 1LL * cnt * h[cnt - 1] % mod * s % mod);
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	memset(tag, 0, sizeof(int) * (n + 1));
	memset(vis, 0, sizeof(int) * (n + 1));
	memset(fir, 0, sizeof(int) * (n + 1));
	E = 1;
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		Add_Edge(x, y);
		Add_Edge(y, x);
	}
	if (dfs(1, 0) < 0) return (void) (puts("0"));
	memset(vis, 0, sizeof(int) * (n + 1));
	int ans = 1;
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		dfs2(i);
		ans = 1LL * ans * f[i] % mod;
	}
	printf("%d\n", ans);
}

int main() {
	int T;
	cin >> T;
	h[0] = h[1] = 1;
	for (int i = 2; i < N; ++i) {
		h[i] = add(h[i - 1], 1LL * (i - 1) * h[i - 2] % mod);
	}
	while (T--) solve();
	return 0;
}

[ZJOI 2012] 波浪

垃圾出题人卡我空间卡我常数卡我题意卡我精度。

虽然题目本身不错但是输出位小数不取模是几个意思?

题意

阿米巴和小强是好朋友。

阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮,他兴奋地叫个不停。而阿米巴则很淡定,他回想起曾经的那些日子,事业的起伏,情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来,简直什么都不算。

于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个的排列。定义波动强度等于相邻两项的差的绝对值的和,即:

给你一个,问:随机一个的排列,它的波动强度不小于的概率有多大?

答案请保留小数点后位输出,四舍五入。

数据范围:当时,;当时,

题解

考虑拆掉那个绝对值。这只需要从小到大依次加入每个数,每次加入时确定这个数旁边有几个数已经被加入计算贡献即可(例如加入时,它左边已经有数就会产生的贡献,右边还没有数就会产生的贡献)。

表示已经加入了前个数,加入的数形成了个连续段,当前产生的贡献是,左右边界中有个已经填了数。

需要注意的是,除了那些顶到左右边界的段,其它段我们只关心它们的相对位置。也就是说段是可以滑动的。

  1. 加入一个数时,有这样几种情况要考虑:
  2. 加入的数自成一段,且没有顶到左右边界,方案有种。因为这个新段不能插入左端点左边或右端点右边。
  3. 加入的数自成一段,且顶到左右边界中的一个,方案有种.
  4. 加入的数在某一段的左右端点,且没有顶到左右边界,方案有种。
  5. 加入的数在某一段左右端点,且顶到左右边界,方案有种。
  6. 加入的数链接了相邻的两段,方案有

因为出题人的毒瘤,在时要用才能不被卡常,在时要用才能不被卡精。

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC optimize("-ffast-math")
#include<bits/stdc++.h>
#define R register
using namespace std;
const int N = 101;
const int S = 5005;

int n, m, k;
long double g[2][N][S * 2][3];
__float128 f[2][N][S * 2][3];

void write(__float128 x) {
	int a[100];
	a[0] = (int) x;
	for (int i = 1; i <= k + 1; ++i) {
		x -= (int) x;
		x *= 10;
		a[i] = (int) x;
	}
	if (a[k + 1] >= 5) ++a[k];
	for (int i = k; i >= 1; --i) {
		if (a[i] == 10) {
			a[i] = 0;
			++a[i - 1];
		}
	}
	printf("%d", a[0]);
	putchar('.');
	for (int i = 1; i <= k; ++i) printf("%d", a[i]);
	puts("");
}

template <typename T> void solve(T f[2][N][S * 2][3]) {
	int now = 1;
	f[0][0][S][0] = 1;
	R T v;
	for (int i = 1; i <= n; ++i) {
		memset(f[now], 0, sizeof f[now]);
		for (int j = 0; j <= n; ++j) {
			for (R int k = 0; k < 2 * S; ++k) {
				for (R int l = 0; l < 3; ++l) {
					v = f[now ^ 1][j][k][l];
					if (v == 0) continue;
					f[now][j + 1][k - i * 2][l] += v * (j + 1 - l);
					if (l < 2) {
						f[now][j + 1][k - i][l + 1] += v * (2 - l);
						f[now][j][k + i][l + 1] += v * (2 - l);
					}
					if (j) {
						f[now][j][k][l] += v * (j * 2 - l);
						f[now][j - 1][k + i * 2][l] += v * (j - 1);
					}
				}
			}
		}
		now ^= 1;
	}
	__float128 ans = 0;
	for (int i = m + S; i < 2 * S; ++i) {
		ans += f[now ^ 1][1][i][2];
	}
	for (int i = 1; i <= n; ++i) ans /= i;
	write(ans);
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	if (n == 1) {
		write(1);
		return 0;
	}
	if (m >= n * (n + 1) / 2) {
		write(0);
		return 0;
	}
	if (k <= 8) solve(g);
	else solve(f);
	return 0;
}

[ZJOI 2013] 蚂蚁寻路

题意

给定一个的带权网格。

要求在网格中选出一个封闭图形。具体可以用一条路线描述。

开始位置在某一格点上,方向朝向北。接着右转两次,左转两次,右转两次,左转两次…… 最后再右转一次。规定这条路线上,不能连续旋转两次,不能经过重复的点,最后需要回到起始点,且左转的次数除以等于

求所有能选出的图形中,点权和最大的是多少。

题解

可以发现,原问题相当于选出个矩形,这些矩形的底边在一条直线上,且高度高低起伏,最大化他们的权值和。

枚举一个底边,设表示做到第列,当前矩形高度为,用了个矩形的方案数。下一个矩形应变高还是变低可以通过的奇偶性确定。

表示左上角在,右下角在矩形的价值,只考虑变高的情况,一个直观的转移是:

然而复杂的转移是阻碍优化的根源。如果我们把矩阵数量这一维的贡献算在这个矩阵的第一列上,可以得到更简洁的转移方程:

这显然可以前缀和优化,得到的优秀算法(这里认为同阶)

#include<bits/stdc++.h>
#define R register
using namespace std;
const int N = 105;
const int inf = 0x3f3f3f3f;

int n, m, k;
int a[N][N], sum[N][N];
int f[N][N][25], g[N][N][25], h[N][N][25];

void upd(int &x, int y) {
	x = max(x, y);
}

int solve(int n) {
	for (int i = 0; i <= m; ++i) {
		for (int j = 0; j <= n + 1; ++j) {
			for (int l = 0; l <= k; ++l) {
				f[i][j][l] = -inf;
				g[i][j][l] = -inf;
				h[i][j][l] = -inf;
			}
		}
		f[i][n + 1][0] = 0;
	}
	for (int i = 0; i < m; ++i) {
		for (int l = 0; l <= k; ++l) {
			g[i][0][l] = -inf;
			for (int j = 1; j <= n; ++j) {
				upd(g[i][j][l], g[i][j - 1][l]);
				upd(g[i][j][l], f[i][j - 1][l]);
			}
		}
		for (int l = 0; l <= k; ++l) {
			h[i][n + 1][l] = -inf;
			for (int j = n; j >= 1; --j) {
				upd(h[i][j][l], h[i][j + 1][l]);
				upd(h[i][j][l], f[i][j + 1][l]);
			}
		}
		for (int j = 1; j <= n; ++j) {
			for (int l = 1; l <= k; ++l) {
				f[i + 1][j][l] = f[i][j][l];
				if (l & 1) upd(f[i + 1][j][l], h[i][j][l - 1]);
				else if (~l & 1) upd(f[i + 1][j][l], g[i][j][l - 1]);
				f[i + 1][j][l] += sum[j][i + 1] - sum[n + 1][i + 1];
			}
		}
	}

	int ans = -inf;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			upd(ans, f[i][j][k]);
		}
	}
	return ans;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	k = k * 2 + 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		for (int j = n; j >= 1; --j) {
			sum[j][i] = sum[j + 1][i] + a[j][i];
		}
	}
	int ans = -inf;
	for (int i = 2; i <= n; ++i) ans = max(ans, solve(i));
	cout << ans << endl;
	return 0;
}

[ZJOI2013]话旧

题意

有一个长度为的序列,满足下列条件。

  1. 对于

  2. 对于所有极小值点,有

我们还规定了个位置的值。

求满足条件的序列个数 和 序列最大值的最大值。第一问的答案对取模。

数据范围:

题解

思维难度不是很高,主要在于分讨非常多。

表示到第个关键点,最后一次是向下/向上的方案数;表示到第个关键点,最后一次是向下/向上的最大值。

转移就不想写了。看看代码就好了。要特别注意关键点纵坐标是的情况;计算时,有些可以在坐标轴上平移直线来简化计算(大不了就是解个二元一次方程)

#include<bits/stdc++.h>
#define pii pair<int, int>
#define R register
using namespace std;
const int N = 1e6 + 10;
const int mod = 19940417;

int n, m;
int f[N][2], mx[N][2];
pii a[N];

inline void upd(int &x, int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

inline void chmax(int &x, int y) {
	x = max(x, y);
}

int Qpow(int x, int p) {
	if (p < 0) return 0;
	int ans = 1;
	while (p) {
		if (p & 1) ans = 1LL * ans * x % mod;
		x = 1LL * x * x % mod;
		p >>= 1;
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	a[++m] = make_pair(0, 0);
	a[++m] = make_pair(n, 0);
	sort(a + 1, a + m + 1);
	m = unique(a + 1, a + m + 1) - a - 1;
	f[1][1] = 1;
	for (int i = 2; i <= m; ++i) {
		int x0 = a[i - 1].first + a[i - 1].second;
		int x1 = a[i].first - a[i].second;
 		int d = (x1 - x0) / 2;
		int ds = a[i].first - a[i - 1].first;
		int dh = a[i].second - a[i - 1].second;
		if (a[i].second == 0) {
			if (a[i - 1].second == 0) {
				upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d - 1) % mod);
				chmax(mx[i][1], mx[i - 1][1]);
				chmax(mx[i][1], d);
			}
			else {
				if (d == 0) {
					upd(f[i][1], f[i - 1][0]);
					chmax(mx[i][1], mx[i - 1][0]);
				}
				else {
					upd(f[i][1], 1LL * f[i - 1][0] * Qpow(2, d - 1) % mod);
					chmax(mx[i][1], mx[i - 1][0]);
					chmax(mx[i][1], d);
				}
				upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d) % mod);
				chmax(mx[i][1], mx[i - 1][1]);
				chmax(mx[i][1], a[i - 1].second + d);
			}
		}
		else {
			if (a[i - 1].second == 0) {
				if (d == 0) {
					upd(f[i][1], f[i - 1][1]);
					chmax(mx[i][1], mx[i - 1][1]);
				}
				else {
					upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d - 1) % mod);
					chmax(mx[i][1], mx[i - 1][1]);
					chmax(mx[i][1], a[i - 1].second + d);
				}
				upd(f[i][0], 1LL * f[i - 1][1] * Qpow(2, d - 1) % mod);
				chmax(mx[i][0], mx[i - 1][1]);
				chmax(mx[i][0], a[i - 1].second + (ds + dh) / 2);
			}
			else {
				if (a[i - 1].second - a[i - 1].first == a[i].second - a[i].first) {
					upd(f[i][1], f[i - 1][1]);
					chmax(mx[i][1], mx[i - 1][1]);
					chmax(mx[i][1], a[i].second);
				}
				else {
					upd(f[i][0], f[i - 1][1]);
					chmax(mx[i][0], mx[i - 1][1]);
					chmax(mx[i][0], a[i - 1].second + (ds + dh) / 2);
				}
				if (a[i - 1].second - a[i].first == a[i].second - a[i - 1].first) {
					upd(f[i][0], f[i - 1][0]);
					chmax(mx[i][0], mx[i - 1][0]);
				}
				if (d >= 0) {
					upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d) % mod);
					chmax(mx[i][1], mx[i - 1][1]);
					chmax(mx[i][1], a[i - 1].second + d);
					upd(f[i][0], 1LL * f[i - 1][1] * (Qpow(2, d) - 1) % mod);
					if (d > 0) {
						chmax(mx[i][0], mx[i - 1][1]);
						chmax(mx[i][0], a[i - 1].second + (ds + dh) / 2);
					}
					if (d == 0) upd(f[i][1], f[i - 1][0]);
					else upd(f[i][1], 1LL * f[i - 1][0] * Qpow(2, d - 1) % mod);
					chmax(mx[i][1], mx[i - 1][0]);
					chmax(mx[i][1], d);
					upd(f[i][0], 1LL * f[i - 1][0] * Qpow(2, d - 1) % mod);
					chmax(mx[i][0], mx[i - 1][0]);
					chmax(mx[i][0], (a[i].second + a[i].first - x0) / 2);
				}
			}
		}
	}
	cout << (f[m][1] % mod + mod) % mod << ' ' << mx[m][1] << endl;
	return 0;
}

[NOI 2015] 寿司晚宴

题意

的正整数划分为三个集合,,,使得,求方案数,对一个读入的取模输出。

数据范围:

题解

注意到一个性质:一个数只会有一个大于等于的质因子,而在本题中不大于的质因子不超过个。

一个思路是暴力搜出这个质因子归属于谁,然后对于大于含有一个的质因子的数根据这个质因子分类计算。但是我操作一下之后总是会有重复计算的情况。

考虑状压。如果只有的数(即最大质因子为那个),可以表示考虑到前个数,集合中包含的质因子集合为,集合中包含质因子集合为的方案数。显然这里要求

对于含有至少一个的质因子的数,我们把它们按照这个质因子排序,这个质因子相同的一起处理。设表示把这个质因子分给集合,集合中包含的质因子集合为,集合中包含质因子集合为的方案数。显然这里要求

但是两个数组都会包含均不包含该质因子的情况,设这段数对应的区间是,那么

总复杂度可以做到,但这里写的是

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
const int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};

int n, mod;
int f[N][N], g[2][N][N];

struct number {
	int x, p, s;
	bool operator < (const number b) const {
		if (p != b.p) return p < b.p;
		else return x < b.x;
	}
} a[N];

inline void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

int main() {
	cin >> n >> mod;
	for (int i = 1; i < n; ++i) {
		a[i].x = i + 1;
		int y = i + 1;
		for (int j = 0; j < 8; ++j) {
			if (y % pri[j] == 0) a[i].s |= (1 << j);
			while (y % pri[j] == 0) y /= pri[j];
		}
		if (y > 1) a[i].p = y;
	}
	sort(a + 1, a + n);
	f[0][0] = 1;
	for (int i = 1; i < n;) {
		if (a[i].p == 0) {
			int s = a[i].s;
			for (int j = 255; j >= 0; --j) {
				for (int k = 255; k >= 0; --k) {
					if (j & k) continue;
					if ((s & k) == 0) {
						upd(f[j | s][k], f[j][k]);
					}
					if ((s & j) == 0) {
						upd(f[j][k | s], f[j][k]);
					}
				}
			}
			++i;
		}
		else {
			for (int j = 0; j < 256; ++j) {
				for (int k = 0; k < 256; ++k) {
					g[0][j][k] = f[j][k];
					g[1][j][k] = f[j][k];
				}
			}
			int nowp = a[i].p;
			while (a[i].p == nowp) {
				int s = a[i].s;
				for (int j = 255; j >= 0; --j) {
					for (int k = 255; k >= 0; --k) {
						if ((s & k) == 0) {
							upd(g[0][j | s][k], g[0][j][k]);
						}
						if ((s & j) == 0) {
							upd(g[1][j][k | s], g[1][j][k]);
						}
					}
				}
				++i;
			}
			for (int j = 0; j < 256; ++j) {
				for (int k = 0; k < 256; ++k) {
					f[j][k] = (g[0][j][k] + g[1][j][k] - f[j][k]);
					if (f[j][k] >= mod) f[j][k] -= mod;
					if (f[j][k] < 0) f[j][k] += mod;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < 256; ++i) {
		for (int j = 0; j < 256; ++j) {
			upd(ans, f[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}