Before

本文章在洛谷博客同步发布

Contest-Link

预期 \(20 + 10 + 30 + 10 = 70\)。

实际 \(100 + 30 + 35 + 0 = 165\)。

挂分 \(-95\)。

rk8/totrk9。菜。

T1 鉴定，5min 写完测了几组数据没问题就跳了；T2 一眼丁真鉴定为线段树，风风火火打了个线段树结果 \(x \le 10^9\)，立即想题，结果发现区间无交，随便写了个二分对拍过了。

然后看第三题，鉴定为神秘线段树，然后发现绝对值没有分配律，好像分块，不会，寄。打了个暴力跑路。因为没开龙龙导致暴力一分没拿，寄。

第四题看了一眼，鉴定为图论，但是不太清楚有什么东西能维护，打了个暴力跑路。

然后开始摆摆摆摆摆摆摆摆摆摆摆摆摆，T3 好像可以直接线段树维护前后缀最大最小！然后就没时间写了。哈哈。

T1

Description

给定一条水平直线和两个点，求经过水平线的两点的最短距离。

输入一行五个整数 \(k,x_1,y_1,x_2,y_2\)。

一行一个自然数，表示平方后的答案。

\(0 \le |k|,|x1|,|y1|,|x2|,|y2|\le 5×10^8\)。

Solution

经典将军饮马，不会的看这里。

考场想法：将军饮马。

考场寄因：没寄。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Code

\(\text{100pts:}\)

// 2023/10/9 PikachuQAQ

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

ll k, xa, ya, xb, yb;

ll dist(ll xa, ll ya, ll xb, ll yb) {
    return (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> k >> xa >> ya >> xb >> yb;
    if (ya >= k && yb <= k || ya <= k && yb >= k) {
        cout << dist(xa, ya, xb, yb) << '\n';
    } else {
        cout << dist(xa, 2 * k - ya, xb, yb) << '\n';
    }

    return 0;
}

T2

Description

数轴上有一些靶子，对应一些不交的区间，每个靶子有个红心区间，按顺序进行射击，根据重靶、丢靶、红心、非红心输出对应的消息。

第一行三个自然数 \(n,m,k\)，含义如题面所述。 接下来 \(n\) 行,每行四个自然数 \(l_i,x_i,y_i,r_i\)，描述了靶子的信息。 接下来一行 \(k\) 个自然数，表示每次射击的坐标。

对于每个询问，输出一行一个对应的结果。

\(1 \le n, k \le 10^5, 1 \le l_i \le x_i \le y_i \le r_i \le m \le 10^9\)。

Solution

因为区间无交集，所以我们可以直接二分，一个靶子一定会有四个坐标，对于一个坐标我们分类讨论即可。

考场想法：二分。

考场寄因：没寄。

时间复杂度 \(O(k \log n)\)，空间复杂度 \(O(n \log n)\)。

Code

\(\text{100pts:}\)

// 2023/10/9 PikachuQAQ

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int kMaxN = 4e5 + 7, kMaxM = kMaxN << 2;

int n, m, k, a[kMaxN], len;
bool vis[kMaxN];
map<int, int> mp;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1, l, x, y, r; i <= n; i++) {
        cin >> l >> x >> y >> r;
        a[++len] = l, a[++len] = r, a[++len] = x, a[++len] = y;
        mp[l] = mp[r] = 1, mp[x] = mp[y] = 2;
    }
    sort(a + 1, a + len + 1);
    for (int i = 1, x; i <= k; i++) {
        cin >> x;
        ll p = lower_bound(a + 1, a + len + 1, x) - a, g = p % 4, q = (p - 1) / 4 + 1;
        if (g == 1 && mp[x] == 0) {
            cout << "Failed\n";
        } else if (vis[q]) {
            cout << "Again\n";
        } else if (g == 1 && mp[x] == 1 || g == 2 && mp[x] != 2 || g == 0) {
            cout << "Normal\n";
            vis[q] = 1;
        } else {
            cout << "Perfect\n";
            vis[q] = 1;
        }
    }

    return 0;
}

T3

Description

给定一个序列，求子段和绝对值的最大值。

第一行两个自然数 \(n,m\)。 接下来一行 \(n\) 个整数，表示序列的初始值。 接下来 \(m\) 行，每行两个自然数，描述了一个查询。

对于每个询问，输出一行一个自然数，表示答案。

\(1 \le n \le 2 \times 10^5, 1\le m \le 3 \times 10^6,0 \le |a_i| \le 10^9\)

Solution

显然线段树是可以的，但是好像卡不过去，只能拿 \(70\) 分。普通线段树的做法是 \(O(m \log n + n)\) 的。

所以我们可以用一种特殊的线段树——猫树维护，其仅支持 \(O(1)\) 查询，不能修改，建树复杂度 \(O(n \log n)\)。

然后就达到了 \(O(n \log n + m)\) 的时间复杂度。

但是我赛后没写出来，但我们还有一种数据结构：ST 表。其实现后时间复杂度为 \(O(n \log n + m)\)。

考场想法：暴力。

考场寄因：没寄。

时间复杂度 \(O(n \log n + m)\)，空间复杂度 \(O(n \log n)\)。

Code

\(\text{100pts:}\)

// 2023/10/9 PikachuQAQ

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

const ll kMaxN = 2e5 + 7, LgMax = 28, INF = 4e18;

ll n, q, a[kMaxN], pre[kMaxN], minn[kMaxN][LgMax], maxn[kMaxN][LgMax], lg[kMaxN];

ll QueryMin(ll l, ll r) {
    if (l > r) {
        return INF;
    } else if (l == 0) {
        return min(QueryMin(l + 1, r), 0ll);
    } else {
        int k = lg[r - l + 1];
        return min(minn[l][k], minn[r - (1 << k) + 1][k]);
    }
}

ll QueryMax(ll l, ll r) {
    if (l > r) {
        return -INF;
    } else if (l == 0) {
        return max(QueryMax(l + 1, r), 0ll);
    } else {
        int k = lg[r - l + 1];
        return max(maxn[l][k], maxn[r - (1 << k) + 1][k]);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lg[i] = log2(i), pre[i] = pre[i - 1] + a[i], minn[i][0] = maxn[i][0] = pre[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]);
            maxn[i][j] = max(maxn[i][j - 1], maxn[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1, x, y; i <= q; i++) {
        cin >> x >> y;
        cout << QueryMax(x - 1, y) - QueryMin(x - 1, y) << '\n';
    }

    return 0;
}

T4

Description

给定 \(n\) 个二元组 \((a_i, b_i)\) ，求字典序最小的排列，使得相邻二元组之间的 \(a\) 或者 \(b\) 相同，且不能连续出现三个相同的二元组。

第一行一个自然数 \(n\)。 接下来 \(n\) 行，每行两个自然数 \(a, b\)。

第一行一个字符串 Yes 或 No ，表示是否存在方案。 如果存在方案，接下来一行 \(n\) 个自然数，第 \(i\) 个自然数表示第 \(i\) 个二元组。

\(1 \le a,b \le n,2 \le n \le 5 \times 10^5\)，保证不存在两个完全一样的二元组。

Solution

咕咕咕。

Code

咕咕咕。

Summary

需要掌握的：龙龙。