一道比较神仙的构造题。
首先确定 (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
", __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, len);
for (int i = 2; i < n; i+=1)
{
if (d1[i] < dn[i]) printf("1 %d %d
", i, d1[i]);
else printf("%d %d %d
", 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
1 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
", ans[i].u, ans[i].v, ans[i].w);
return 0;
}
另：这份代码在洛谷上 AC 了， 但是在 BZOJ 上会 WA， 不知道为什么……