【LGR-071】洛谷 4 月月赛 & MdOI Round 2 Div.1 题解

【LGR-071】洛谷 4 月月赛 & MdOI Round 2 Div.1

Odyssey

首先预处理所有数的分解式，次数模上 $k$。

然后 DP，设 $f_{i,j}$ 为到点 $i$ 且上一条边的权值为 $j$ 的最短路，DAG 转移即可，有效的状态数只有 $\mathcal O(m)$ 个，用一个 map 或者 unordered_map 存即可。

const int N = 1e5 + 7, M = 1e6 + 7;
int n, m, k, W, d[N], v[M], ans;
unordered_map<int, int> f[N];
vector<pi> p[M];
vector<pair<int, pi>> e[N];
queue<int> q;

inline void init(int n) {
	for (int i = 1; i <= n; i++) v[i] = i;
	for (int i = 2; i <= n; i++) {
		if (v[i] > 1)
			for (int x = v[i], j = x; j <= n; j += x) {
				p[j].pb(mp(x, 0));
				while (!(v[j] % x)) ++p[j].back().se, v[j] /= x;
				p[j].back().se %= k;
				if (!p[j].back().se) p[j].pop_back();
			}
		for (auto o : p[i])
			for (int t = o.se; t; t--)
				v[i] *= o.fi;
	}
}

int main() {
	rd(n, m, k);
	for (int i = 1, x, y, w, z; i <= m; i++)
		rd(x, y), rd(w, z), e[x].pb(mp(y, mp(w, z))), ++d[y], W = max(W, w);
	init(W);
	for (int x = 1; x <= n; x++)
		if (!d[x]) q.push(x);
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (auto o : e[x]) {
			int y = o.fi, w = v[o.se.fi], z = o.se.se;
			ll g = 1;
			for (auto p : ::p[w]) {
				for (int t = k - p.se; t; t--) {
					g *= p.fi;
					if (g > W) break;
				}
				if (g > W) break;
			}
			if (g <= W) z += f[x][g];
			ans = max(ans, f[y][w] = max(f[y][w], z));
			if (!--d[y]) q.push(y);
		}
	}
	print(ans);
	return 0;
}

Resurrection

AtCoder 型的小清新计数题。

首先转化题意，题意相当于除了根之外的每个点都像祖先连一条线，要求线与线之间没有交点。

这玩意儿可以拿到 $40$ 分。

然后进一步转化题意，显然最终是一棵以 $n$ 为根的树。

我们在最后形成的树上标上深度，根据上面的性质我们可以发现，深度序列与这棵树一一对应。

其中点 $i$ 向其在原树上的祖先中离 $i$ 最近且深度 $-1$ 的点连边。

于是问题转化成深度序列的个数，这个树形 DP 然后前缀和优化一下就好了。

const int N = 3e3 + 7;
int n;
vi e[N];
modint f[N][N];

void dfs(int x) {
	for (int i = 0; i < n; i++) f[x][i] = 1;
	for (int y : e[x]) {
		dfs(y);
		for (int i = 0; i < n; i++) f[x][i] *= f[y][i+1];
	}
	if (x != n) f[x][0] = 0;
	for (int i = 1; i <= n; i++) f[x][i] += f[x][i-1];
}

int main() {
	rd(n);
	for (int i = 1, x, y; i < n; i++) rd(x, y), e[max(x,y)].pb(min(x, y));
	dfs(n);
	print(f[n][0]);
	return 0;
}

Quo Vadis

垃圾题。

Little Goth

题目太神仙了，先咕咕咕着。