SSL-OI夏日合宿 2020.08.20 A组

摘要： SSL-OI 夏日合宿 2020.08.20 A 组比赛中，选手们在 T1 题上遭遇滑铁卢，T2 题考查了线段树优化建边和传递闭包等知识点，T3 题则是一道字符串题。

为啥今天又爆0?
开场看完题直接睡了两个钟
T1挺水的但最后没时间写是什么鬼?
T2前两天听WYC说点对区间建边要用线段树, 没想到这么快就考到了.
得先把A题搞定, 不然必被教练骂

今天缺的知识点

线段树优化建边
传递闭包
求最大独立集

T1 温暖题

来自 Codeforces 1066F

出题人送的温暖, 我看见了, 可完全没有收到.

题意

笛卡尔坐标系上有$n$个点, 定义一个点$(x,y)$在第$max(x,y)$层.
从$(0,0)$出发, 按层数不降的顺序遍历所有点, 求最小曼哈顿距离和.

$n \leq 2 \times 10^5$, $0\leq x,y\leq10^9$

故事

故事就是睡了两个钟. 今天一天都好困, 可能是前天稍微小肝了一会NS, 其实也就到十二点而已. 然后昨天也没有及时休整, 一直到今天都很困, 昨天和今天都是七点才起床洗澡.

其实只要看完题目就能切掉这题.

观察到第$x$层的形状是从$(x,x)$向负方向引出两条射线所形成的直角. 对于每一层我们肯定不会走回头路, 所以一定是从其中一个端点走到另一个端点.
设$f_{i,j}$表示第i层到左上/右下结束所需的最小曼哈顿距离($j\in\{0,1\}$), DP即可. 注意到$i$可能比较大, 排个序即可.

#define MXN (200020)

#include <math.h>
#include <stdio.h>

#include <algorithm>

int n;

struct Node {
    long long x, y;
    bool operator<(const Node N) const { return (std::max(x, y) == std::max(N.x, N.y)) ? ((x == N.x) ? (y > N.y) : (x < N.x)) : (std::max(x, y) < std::max(N.x, N.y)); }
} node[MXN], last[2];

long long way(Node a, Node b) { return abs(a.x - b.x) + abs(a.y - b.y); }

long long f[MXN][2], p = 0;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif

    scanf("%d", &n);

    for (int i = 0, x, y; i < n; ++i)
        scanf("%lld%lld", &node[i].x, &node[i].y);

    std::sort(node, node + n);

    for (int i = 0, j = 0; i <= n; ++i) {
        if (std::max(node[i].x, node[i].y) != std::max(node[i - 1].x, node[i - 1].y)) {
            ++p;
            f[p][0] = way(node[i - 1], node[j]) + std::min(f[p - 1][0] + way(last[0], node[i - 1]), f[p - 1][1] + way(last[1], node[i - 1]));
            f[p][1] = way(node[i - 1], node[j]) + std::min(f[p - 1][0] + way(last[0], node[j]), f[p - 1][1] + way(last[1], node[j]));
            last[0] = node[j], last[1] = node[i - 1];
            j = i;
        }
    }

    printf("%lld", std::min(f[p][0], f[p][1]));

    return 0;
}

T2 礼物

来自USACO 2017 December A Pie for a Pie

又一次, 我知道该用什么算法但我不会.

题意

A和B是一对该死的情侣, 他们在该死的情人节要互赠该死的礼物.

A和B各有$n$个礼物, 每个礼物有两个价值$(a,b)$分别表示在送出者眼中的价值和在接收者眼中的价值. 每当(A或B)收到一个在自己眼中价值为$v$的礼物时, 会选择在自己眼中价值属于$[v,v+d]$的礼物回赠. 显而易见, 收到的礼物不能送出, 收到的礼物不能送出.(这是我单身的原因?)
当其中一个人收到自己眼中价值为$0$的礼物时, 送礼就正常结束.(送礼正常结束,吵架正常开始?)

A先送礼, 问: 最少送几次礼物后, 送礼正常结束.(急着吵架~). 若不能正常结束, 输出$-1$.

该死的题面该死的又臭又长

故事

故事就考场想到可以搜索骗分, 如果线段树优化建边差不多就能过, 但是不知道为啥磨磨唧唧打了一个多钟没打出来. 可能本来就不太熟悉这种做法吧?

题解

题解提供了两种做法, 线段树建边跑最短路&并查集维护跑bfs(我算是想到两种正解吗?)

线段树优化建边

这个我待会去学

并查集维护跑bfs

T3 字符串

来自Codeforces 590E