337

又被打爆了 \(\dots\) 补题!

C - Lining Up 2

给出一个数组 \(a\)，其中

• \(a_{i}=-1\),则 \({i}\) 在最前面
• \(a_{i}\neq-1\),则 \(i\) 的前面是 \(a_{i}\)

输出从前到后的数字。

我连 ABC C 题都写不出了 \(\dots\) 我的水平退化挺严重的，或者是说根本就没有水平过 \(\dots\)

Solution

暴力是 \(n^2\) 过不了。

因此我就想通过 upper_bound 直接来找到相应的索引并输出，但是发现排序后的数组的索引就变化了。

void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n + 1);
    int head;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
        if (a[i].first == -1)
            head = i, cout << i << " ";
    }
    sort(a.begin() + 1, a.begin() + 1 + n);

    for (int i = 2; i <= n; i++)
    {
        int j = upper_bound(a.begin() + 1, a.begin() + 1 + n, make_pair(head, -1)) - a.begin();
        cout << j << " ", head = j;    }
}

水平太低导致的🤣

官方题解：

void solve()
{
    int N;
    cin >> N;
    vector<int> B(N, N); // B[i] 表示人 i 的下一个人（如果不存在则为 N）
    int front;
    for (int i = 0; i < N; ++i)
    {
        int A;
        cin >> A;
        --A; // 将其转换为从0开始编号
        if (A < 0)//A==-2
            front = i;
        else
            B[A] = i; // 第 i 个人的前一个是 A ⇔ A 的后一个人是 i
    }
    while (front < N)
    { // 直到达到 N（= 没有下一个人）为止一直重复向后移动。
        cout << front + 1 << " ";
        front = B[front];
    }
    cout << endl;
}

D - Cheating Gomoku Narabe

(待更 \(\dots\))