Solution Set - 咋提玄坛 | 说无可说

说无可说。

I have nothing to say.

Mi havas nenion por diri.

J'ai rien à dire.

说无可说

Link。

我说，我去，暴力 dp 一次就是 \(O(|S| ^ 2)\) 的了，直接起飞！

题目说，我只要求相似度为 \(1 \sim 8\) 的字符串对数，there must be a reason。

我说，原来可以 dfs，太神奇啦！但是这要怎么搜啊？那么其实类似 dp 那么记录端点，，每次 dfs 转移下一个状态就是先暴力匹配，找到第一个依次推下去不相等的字符，从这里开始按照 dp 那样转移即可，具体可见代码。为了提升效率加一条最优性剪枝，因为当前答案一定不小于目前搜索的答案加上需要处理的字符串的长度之差（用加减字符达成同样长度）。

我说，有一个小细节，string 的长度是 unsigned 类型的，如果减的话可能会爆炸，要强转 int。

namespace liuzimingc {
const int N = 205;
#define endl '\n'

int n, i, j, res, ans[10];
string s[N];

void dfs(int x, int y, int step) {
	if (step >= res) return;
	while (x < s[i].length() && y < s[j].length() && s[i][x] == s[j][y]) x++, y++;
	if (x >= s[i].length() && y >= s[j].length()) {
		res = min(res, step);
		return;
	}
	if (x < s[i].length()) dfs(x + 1, y, step + 1);
	if (y < s[j].length()) dfs(x, y + 1, step + 1);
	if (x < s[i].length() && y < s[j].length()) dfs(x + 1, y + 1, step + 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (i = 1; i <= n; i++)
		for (j = i + 1; j <= n; j++) {
			res = 9;
			dfs(0, 0, 0);
			ans[res]++;
		}
	for (int i = 1; i <= 8; i++) cout << ans[i] << " \n"[i == 8];
	return 0;
}
#undef int
} // namespace liuzimingc

我说，这里算的是起点，dp 算的是一端的终点，本质相同。

我说，我不会傻逼爆搜。说无可说。

消防

首先，枢纽一定在树的直径上。

那么我们随便拉出来一条直径，那么所有点到路径的距离就分成两种情况：

• 点在直径上。只能是路径的两个端点。可以用双指针 \(O(n)\) 维护长度和不大于 \(s\) 的路径（显然越大越好）
• 点不在直径上。从直径上的点对其他点 dfs 一下就好了，每个点只会遍历一次所以是 \(O(n)\) 的。

然后综合两种情况就做完了！

namespace liuzimingc {
const int N = 3e5 + 5;
#define endl '\n'

int n, s, dep[N], x, fa[N], ans = 0x3f3f3f3f;
vector<pair<int, int>> e[N];
bool vis[N];

void dfs(int u, int f) {
	fa[u] = f;
	if (dep[u] > dep[x]) x = u;
	for (const auto &i : e[u]) {
		int v = i.first, w = i.second;
		if (v == f || vis[v]) continue;
		dep[v] = dep[u] + w;
		dfs(v, u);
	}
} // dep 得到从某一点开始到所有点的距离 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> s;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back(make_pair(v, w));
		e[v].push_back(make_pair(u, w));
	}
	x = 1;
	dfs(1, 0);
	dep[x] = 0;
	dfs(x, 0); // 两次都找距离最远的点，求直径
	int begin = x; // 这条直径的最底端（抽象说法），fa[x] 就是跳上去
	for (int i = begin, j = begin; i; i = fa[i]) {
		while (dep[j] - dep[i] > s) j = fa[j];
		ans = min(ans, max(dep[i], dep[begin] - dep[j]));
	}
	for (int i = begin; i; i = fa[i]) vis[i] = true;
	for (int i = begin; i; i = fa[i]) {
		x = i;
		dep[i] = 0;
		dfs(i, fa[i]);
	}
	for (int i = 1; i <= n; i++) ans = max(ans, dep[i]);
	cout << ans << endl;
	return 0;
}
#undef int
} // namespace liuzimingc

以及顺便学到了两次 bfs / dfs 求直径，以前不知道。。。

小凸玩密室

龙门对决

咕咕。