HKU Provincists 1st Training

Posted on 2023-10-11 繁/简： set

题目来自 2018-2019 ACM-ICPC, NEERC, Southern Subregional Contest, Qualification Stage。link

完成率 9/12。怎么说呢，我觉得能够做得更好。还是要吸取一个教训：不要被题目的通过人数所吓到；有时候通过数较少并不一定意味着自己想不出来。另外，当卡在一个题目过久时，要及时止损开另一道题。

这次训练我们队内的交流很少，基本上是在自己打自己的。的确，用英文交流对我来说是一个挑战，有时候真的想不起来某个术语对应的英文说法。但交流起到的作用究竟大不大呢？还是接下来慢慢探索吧。

This article provides a feasible solution to a certain competitive programming problem. If you have better solutions, feel free to share with me!

Coffee Break

简单贪心。很自然的想到用 set 实现。

Gilder

实际上上升气流之间的间隔就是选择经过某个上升气流的代价。飞行轨迹一定是一段连续的区间，可以观察到这就是一个换皮滑动窗口问题。双指针轻松解决。

这个问题有个坑：当高度为 0 时，即使有上升气流也不能继续向前飞行。队友在这里卡了很久；我后来补题的时候也踩了这个坑。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 10;

struct seg {
    int x, y;
} a[MAX_N];

int main() {

    int n, h;
    cin >> n >> h;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].y;
    }

    int l = 1, r = 1;
    int ans = 0, cur = a[1].y - a[1].x, cost = h;

    while (l <= n) {
        while (r < n && cost > a[r + 1].x - a[r].y) {
            cost -= a[r + 1].x - a[r].y;
            ++r;
            cur += a[r].y - a[r - 1].y;
        }
        ans = max(ans, cur + cost);
        if (l < n) {
            cur -= a[l + 1].x - a[l].x;
            cost += a[l + 1].x - a[l].y;
        }
        ++l;
    }

    cout << ans << endl;

    return 0;
}

Masquerade strikes back

思路其实比较好想，但我硬是没找到一种优雅的实现方法。最后看了标程发现它的实现居然比较暴力，理论上的时间复杂度竟然是 \(O(n\sqrt{c})\) 的。但其实这个时间复杂度在 2s 内是可以接受的。

具体来说，使用 \(O(\sqrt{c})\) 的算法暴力枚举某数的因数，并用一个数组进行记忆。当再次遇到该数时从记忆数组中储存的位置开始枚举因数。此外还有一个小小的优化：在输出 \(\{a,b\}\) 后下次一定输出 \(\{b,a\}\)。

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_C = 1e7 + 10;
const int MAX_N = 2e5 + 10;

int d[MAX_C], p[MAX_N];
int a[MAX_N];
int ans1[MAX_N], ans2[MAX_N];
bool vis[MAX_C];

int main() {

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)    cin >> a[i];

    for (int i = 1; i <= n; ++i) {
        if (vis[a[i]]) {
            vis[a[i]] = false;
            ans1[i] = a[i] / p[a[i]], ans2[i] = p[a[i]];
            continue;
        }

        bool flag = false;
        for (int j = p[a[i]] + 1; j <= sqrt(a[i]); ++j) {
            if (a[i] % j == 0) {
                flag = true;
                p[a[i]] = j;
                if (j * j != a[i])
                    vis[a[i]] = true;
                break;
            }
        }
        if (!flag) {
            cout << "NO" << endl;
            return 0;
        }
    
        ans1[i] = p[a[i]], ans2[i] = a[i] / p[a[i]];
    }

    cout << "YES" << endl;
    for (int i = 1; i <= n; ++i)
        cout << ans1[i] << " " << ans2[i] << endl;

    return 0;
}

Painting the fence

有点难。这个真的没想出来怎么做。

首先发现一个性质：每个颜色最多只能被操作一次。在首次操作过后，之后对该颜色的操作都是无意义的。

可以把操作想象成一个缩点的过程，即首次操作某颜色 \(i\) 后，我们将 \(i\) 所对应的区间 \([l,r]\) 视作一个颜色为 \(i\) 的单独点 (具体实现中我们留下两个点，标记缩点对应区间的范围)。一次有效的缩点会令点的个数减少 \(\geq1\)，既然如此，有效操作所需的总时间是不会超过 \(O(n)\) 的。

那么问题转化为，如何快速的找到被操作的区间的位置：即，高效地找到颜色 \(i\) 所对应的 \(l,r\)。观察到颜色不超过 \(3\cdot 10^5\) 种，我们不妨开 \(3\cdot10^5\) 个 set 储存每种颜色对应栅栏的位置。

当对颜色 \(i\) 执行操作时，我们：

若 \(i\) 已经被操作过 (vis[i]=true) 或该颜色的栅栏不足两个 (set[i].size()<2)，本次操作无效。
访问 set[i]，获得颜色 \(i\) 对应的左边界 \(l\) 与右边界 \(r\)。
删除所有 \([l+1,r-1]\) 中的元素；注意处理区间内含有缩点的情况。
将 vis[i] 设为 true，标记颜色 \(i\) 所对应的区间已经成为了缩点。

最后根据 set 中存储的信息对所有栅栏进行最终染色。时间复杂度 \(O(m\log n+n)\)，确实很巧妙。

看到有别的队用 splay 过的，orz...

#include <iostream>
#include <set>

using namespace std;

const int MAX_N = 3e5 + 10;

int n, m;
int a[MAX_N];
bool vis[MAX_N];

set<int> pos[MAX_N];

int main() {

    cin >> n;

    int maxi = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        maxi = max(maxi, a[i]);
        pos[a[i]].insert(i);
    }

    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int col;
        cin >> col;
        if (vis[col] || pos[col].size() < 2) 
            continue;
        int p = *(pos[col].begin()) + 1, r = *(pos[col].rbegin()) - 1;
        while (p <= r) {
            pos[a[p]].erase(p);
            if (vis[a[p]] && !pos[a[p]].empty()) {
                p = *(pos[a[p]].begin());
                pos[a[p]].erase(p);
            }
            p++;
        }
        vis[col] = true;
    }

    
    for (int i = 1; i <= maxi; ++i) {
        if (pos[i].size() == 2 && vis[i]) {
            int l = *pos[i].begin(), r = *pos[i].rbegin();
            for (int p = l; p <= r; ++p) {
                a[p] = i;
            }
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << a[i] << " ";

    return 0;
}

Tickets

将询问离线下来排序处理即可。比较简单。

Tree Reconstruction

训练时看到过的人不多于是没有开题；实际上之后自己稍微想了下就想出来了。

首先观察到节点 \(n\) 一定会出现在所有数对中，不妨将节点 \(n\) 作为根进行构建。\(\{n,a\}\) 出现 \(x\) 次代表节点 \(a\) 在以 \(n\) 为根的树中深度为 \(x\)；贪心的将未被约束的点挪过来凑深度即可。

如果未被约束的点中有大于 \(a\) 的，那么可以断定该树不存在。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1010;

int n;
int dep[MAX_N];

pair<int, int> ans[MAX_N];

struct dt {
    int x, y;
    bool operator < (const dt& a) {
        return y > a.y;
    }
} e[MAX_N];

int main() {

    cin >> n;

    bool flag = false;
    for (int i = 1; i < n; ++i) {
        cin >> e[i].x >> e[i].y;
        if (e[i].x < e[i].y)    swap(e[i].x, e[i].y);
        if (e[i].x != n)
            flag = true;
    }

    if (flag) {
        cout << "NO" << endl;
        return 0;
    }

    sort(e + 1, e + n);
    int l = 1, r = 2, sum = 0;
    while (l < n) {
        while (r < n && e[r].y == e[l].y)
            ++r;
        int depth = r - l;
        dep[e[l].y] = depth;
        sum += depth - 1;
        l = r;
    }

    stack<int> internal;
    for (int i = 1; i < n; ++i) {
        if (!dep[i])
            internal.push(i);
    }

    if (internal.size() < sum) {
        cout << "NO" << endl;
        return 0;
    }

    int ansCnt = 0;
    for (int i = n - 1; i >= 1; --i) {
        int lst = n;
        while (dep[i] >= 2) {
            if (internal.top() > i) {
                cout << "NO" << endl;
                return 0;
            }
            ans[++ansCnt] = make_pair(lst, internal.top());
            lst = internal.top();
            internal.pop();
            dep[i]--;
        }
        if (dep[i])
            ans[++ansCnt] = make_pair(lst, i);
    }

    cout << "YES" << endl;
    for (int i = 1; i <= ansCnt; ++i)
        cout << ans[i].first << " " << ans[i].second << endl;


    return 0;
}

Theater Square

普及组第一题水平。冇野讲。

Medians and Partition

简单规律。用 \(\geq m\) 的连续区间去补 \(<m\) 连续区间，余下的 \(\geq m\) 区间全部切成长度为 1 的小块使得答案最大化。按这个算法得到的答案一定是 \(\geq m\) 数的个数减去 \(< m\) 数的个数。

Ray in the tube

整场中通过率最低的题，但实际上我觉得比 E 要简单一点。但也的确是一个非常有趣的题！

首先根据 common sense 来讲，步长越小，反射越密集，可能覆盖到的 sensors 就越多，很自然的考虑步长为 \(1\) 的情况。

很显然，步长为 \(1\) 的轨迹一定不劣于其他步长为奇数的轨迹。但它却有可能覆盖不到步长为偶数的轨迹。于是我们试图寻找步长为偶数的轨迹中是否存在某个最优轨迹。

可以发现，任何步长为 \(2^n\times a\) (\(a\) 为奇数) 的轨迹都能被步长为 \(2^n\) 的轨迹覆盖。(画个图就能明白，从下边界到上边界一定要经过奇数个步长) 因此，偶数步长是由 \(\{2, 2^2,...,2^n\}\) 这一步长集合 capture 的。

综上所述，我们只需要关注 \(\{2^0,2^1,...,2^n\}\) 这一系列步长，暴力求出它们对应的答案后取最大值即可。时间复杂度 \(O(n\log{n})\)。将答案初始化为 \(2\) 防止两个点垂直排列的情况 (即步长为 \(0\)) 产生影响。

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 1e5 + 10;
const int MAX_M = 1e9;
 
int a[MAX_N], b[MAX_N];
 
map<int, int> cnt;
 
int main() {
 
    int n, y1, m, y2;
    cin >> n >> y1;
    for (int i = 1; i <= n; ++i)    cin >> a[i];
    cin >> m >> y2;
    for (int i = 1; i <= m; ++i)    cin >> b[i];
 
    int finalAns = 2;
    for (int step = 2; step <= MAX_M; step <<= 1) {
        cnt.clear();
        int ans = 0;
        for (int i = 1; i <= m; ++i)
            cnt[(b[i] + step / 2) % step]++,
            ans = max(ans, cnt[(b[i] + step / 2) % step]);
        for (int i = 1; i <= n; ++i)
            cnt[a[i] % step]++, 
            ans = max(ans, cnt[a[i] % step]);
        finalAns = max(finalAns, ans);
    }
 
    cout << finalAns << endl;
 
    return 0;
}

-----------------------------------そして、次の曲が始まるのです。-----------------------------------