题解【洛谷P5959】[POI2018]Plan metra

题面

一道比较神仙的构造题。

首先确定 \(1\) 到 \(n\) 的路径长度，不妨设其长为 \(m\) 。

通过观察发现，\(m\) 就是 \(\min_{1<i<n}\{dist_{1,i} + dist_{i,n}\}\)。

如果所有的 \(| dist_{1, i} - dist_{i, n} |\) 都相等，那么可以特判一下：

首先将 \(1\) 与 \(n\) 连接起来，路径长度为 \(| dist_{1, i} - dist_{i, n} |\) ；
对于每一个 \(\forall 1<i<n\) ：
- 如果\(dist_{1,i}>dist_{i,n}\)，那么将 \(i\) 与 \(1\) 连接，长度为 \(dist_{1,i}\) ；
- 如果\(dist_{1,i} \leq dist_{i,n}\) ，那么将 \(i\) 与 \(n\)连接，长度为 \(dist_{i, n}\) 。

若点 \(i\) 满足 \(dist_{1,i} + dist_{i,n} = m\)，则 \(i\) 在 \(1\) 到 \(n\) 的路径上。

否则可以求出 \(i\) 到 \((1, n)\) 路径的距离和 \(i\) 在路径上的“投影”的

位置，查找位置可以使用二分查找。

将 \(i\) 挂在路径上对应的点上即可。

如果找不到可以挂起的位置或者 \(1\) 到 \(n\) 的路径上有几个点重复就无解。

注意特判 \(n=2\) 的情况。

代码如下（刚好 \(100\) 行…）：

#include <bits/stdc++.h>

#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)

#define itn int

#define gI gi

#define mk make_pair

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 500003;

int sz, ddd, len, n, m = 1000000007, d1[maxn], dn[maxn], dis[maxn], jlx[maxn];

struct Node

{

	int id, dis;

} a[maxn];

struct Ans

{

	int u, v, w;

} ans[maxn];

inline bool cmp(Node x, Node y) {return x.dis < y.dis;}

inline void sub1_getans()

{

	puts("TAK");

	printf("1 %d %d\n", n, len);

	for (int i = 2; i < n; i+=1)

	{

		if (d1[i] < dn[i]) printf("1 %d %d\n", i, d1[i]);

		else printf("%d %d %d\n", n, i, dn[i]);

	}

	return;

}

inline int Binary_Search(int x)

{

	int l = 1, r = sz;

	while (l <= r)

	{

		int mid = (l + r) >> 1;

		if (a[mid].dis == x) return mid;

		else if (a[mid].dis < x) l = mid + 1;

		else r = mid - 1;

	}

	return -1;

}

int main()

{

	n = gi();

	if (n == 2) //特判

	{

		puts("TAK\n1 2 1");

		return 0;

	}

	d1[1] = dn[n] = 0;

	for (int i = 2; i < n; i+=1) d1[i] = gi();

	for (int i = 2; i < n; i+=1) dn[i] = gi(), jlx[i] = abs(d1[i] - dn[i]);

	bool fl = true;

	for (int i = 3; i < n; i+=1) if (jlx[i] != jlx[i - 1]) {fl = false; break;}

	if (fl) {len = jlx[2]; sub1_getans(); return 0;} //特判

	for (int i = 2; i < n; i+=1) m = min(m, d1[i] + dn[i]);

	a[++sz] = (Node){1, 0};

	d1[n] = dn[1] = m;

	for (int i = 2; i < n; i+=1)

		if (d1[i] + dn[i] == m) a[++sz] = (Node){i, d1[i]};

	a[++sz] = (Node){n, d1[n]};

	sort(a + 1, a + 1 + sz, cmp);

	for (int i = 2; i < n; i+=1)

	{

		dis[i] = d1[i] - (d1[i] + dn[i] - m) / 2;

	}

	for (int i = 1; i < sz; i+=1)

	{

		if (a[i].dis == a[i + 1].dis) {puts("NIE"); return 0;}

		ans[++ddd] = (Ans){a[i].id, a[i + 1].id, a[i + 1].dis - a[i].dis};

	}

	for (int i = 2; i < n; i+=1)

	{

		int nowlen = d1[i] + dn[i];

		if (nowlen != m)

		{

			int find_jl = Binary_Search(dis[i]); //二分挂起的位置

			if (((d1[i] + dn[i] - m) & 1) || find_jl == -1) {puts("NIE"); return 0;}

			ans[++ddd] = (Ans){a[find_jl].id, i, (d1[i] + dn[i] - m) / 2};

		}

	}

	puts("TAK");

	for (int i = 1; i <= ddd; i+=1) printf("%d %d %d\n", ans[i].u, ans[i].v, ans[i].w);

	return 0;

}

另：这份代码在洛谷上 AC 了，但是在 BZOJ 上会 WA，不知道为什么……

巴特西

题解【洛谷P5959】[POI2018]Plan metra

最新文章

热门文章