P6584 重拳出击

写在前面

来给 zrm 大佬的题写一篇题解。

这题代码实现难度不高，但是比较锻炼思维，而且应该有不少种解法。着实是一道质量很高的题目。

算法思路

首先呢，显然当小 Z 向当前节点的一棵子树走去时，这棵子树上的 youyou 会与小 Z 的距离减 \(2\) 或者减 \(1\)（减 \(1\) 当且仅当小 Z 的射程与 youyou 的距离为 \(1\)）。而其余节点上的 youyou 与小 Z 的相对距离不会发生变化。

其次，小 Z 在一棵子树上花的所有时间，只和这棵子树上最深的有 youyou 的节点有关。

所以，小 Z 只需要去迎上离出发点最深的 youyou，然后在消灭这只 youyou 后再去迎离当前节点最深的 youyou，其余的 youyou 一定能在这个过程中被全部消灭。

用类似于求树的直径的方法，通过 dfs 找到最深 youyou 的深度、最远的两只 youyou 的距离，那么消灭第一只 youyou 后，这时最深的 youyou 深度就是最远距离 \(-\) 第一只 youyou 的深度。

时间复杂度 \(\Theta(n)\)。

Tips

算出两次需要移动的距离来之后直接让距离减去射程 \(k\) 可以让思考简单一些。（下文的距离指减去射程后的距离）
处理好两次移动距离的奇偶性。如果是奇数，距离为 \(1\) 后直接原地等一回合就好，这样答案不会变劣。并且将次远的 youyou 的距离减 \(1\)。
注意特判一下一回合就能消灭全部 youyou 的情况和次远的 youyou 在射程范围内的情况。
注意一回合是先射击在移动，因此消灭最后的 youyou 的回合是一个额外的回合。

Code

#include<bits/stdc++.h>

using namespace std;

const int Maxn = 4e5 + 5;

int n, m, x, y, k, T, ans;

struct e {

	int to, next;

} b[Maxn << 1];

int head[Maxn], cnt;

bool vis[Maxn];

bool yy[Maxn];

int dep1st, id1st, dep2nd, id2nd;

int Maxdep, Maxid;

void add(int u, int v)

{

	cnt++;

	b[cnt].next = head[u];

	b[cnt].to = v;

	head[u] = cnt;

}

inline int read()

{

	int f = 1, w = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');

	return f * w;

}

void dfs(int t, int dep)

{

	if(vis[t]) return;

	vis[t] = 1;

	if((dep > Maxdep) && yy[t])

	{

		Maxdep = dep;

		Maxid = t;

	}

	for(int i = head[t]; i; i = b[i].next)

	{

		int tto = b[i].to;

		if(vis[tto]) continue;

		dfs(tto, dep + 1);

	}

}

int main()

{

	n = read() - 1;

	while(n--)

	{

		x = read(); y = read();

		add(x, y); add(y, x);

	}

	m = read();

	while(m--)

	{

		x = read();

		yy[x] = 1;

	}

	k = read(); T = read();

	dfs(T, 0);

	dep1st = Maxdep; id1st = Maxid;

	memset(vis, 0, sizeof(vis));

	Maxdep = 0; Maxid = 0;

	dfs(id1st, 0);

	dep2nd = Maxdep - dep1st; id2nd = Maxid;

	dep1st -= k; dep2nd -= k;

	if((dep1st) <= 0 && (dep2nd <= 0))

	{

		printf("%d", 1);

	}

	else if((dep2nd <= 0))

	{

		printf("%d", (dep1st/2) + (int)(dep1st & 1) + 1);

	}

	else

	{

		if(dep1st & 1)

		{

			dep2nd--;

			ans++;

		}

		printf("%d", ans + (dep1st/2) + (dep2nd/2) + (int)(dep2nd & 1) + 1);

	}

	return 0;

}

巴特西

P6584 重拳出击

写在前面

算法思路

Tips

Code

最新文章

热门文章