Tests for Haybales (USACO Gold 2022 January)

这是一个构造题，一种办法是用差分约束来解，另一种办法是构造树来解。总体上，不等式的约束关系这样的题，用图或树的方式来表达关系，是一个比较通用的解决构造问题的方法。

题目核心条件是： $j_i$ 是 $x_{j_i} \leq x_i+K$ 成立的最大索引，这个换过来讲，就是 $x_{j_i+1} > x_i + K$ ，所以在纸上画一画，可以理解到，这些不等式基本形成两类约束关系，一是多个 $j_i$ 之间串起来，形成互相之间的距离要大于K，最长的串有多长，应该就需要至少多少个K；另一个是对于 $j_i$ 都是同一个值的多个相邻点，就要求这些点都单调增而且都要在 $x_{j_i}-K$ 到 $x_{j_i}$ 的范围内。这样两类约束关系关系，可以想到是一个二维的结构，可以构造出一棵树出来，就是 $i$ 的父亲是 $j_i+1$ ，比如对题中例子：

然后我们需要给他们assign数字，这有多种办法，比如一种比较简单的，就是父亲是儿子最大编号加上K+1，而K=N。容易验证这样产生的结果是正确的。对于例子来说就是：

           7
          / \
      5(15) 6(17)
     /        |
    3(8)    4(10)
   /   \
1(0)   2(1)

此题对思维能力有一定要求，代码写出来是非常简单的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// <= 1e5
int n;
int j[100005];
vector<int> adj[100005];    // i's parent is j[i]+1, root is N+1
int height[100005];
ll K;
ll x[100005];
 
int idx = 0;
void dfs(int s) {
    for (int u: adj[s]) {
        height[u]=height[s]-1;  // calc heights of children
        dfs(u);
    }
    x[s] = height[s]*K + idx++;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &j[i]);
        j[i]--;
        int fa = j[i]+1;
        adj[fa].push_back(i);
        height[fa] = max(height[fa], height[i]+1);  // calc height of root
    }
 
    K = n;
    dfs(n);     // assign x[i]
 
    printf("%d\n", K);
    for (int i = 0; i < n; i++)
        printf("%lld\n", x[i]);
 
}