Educational Codeforces Round 124 (Rated for Div. 2) CD题解

C-Fault-tolerant Network

题目大意：
有两列主机，每一列的主机相邻之间有网络连线，但是两列之间的主机没有网络连线，现在将两列之间的主机进行连接，使得任意一台主机断开后整个网络还是能连通。输出最小的费用，连接两台主机的费用为$|a_i-b_i|$

思路：
显然每一列的头尾主机都要与另一列有连接。
如果只是贪心地求出头尾主机连接对面主机的最小费用，可能会存在连接重合或者不是最优解的情况。
比如有的时候连接两条不是最小费用的线比连接三条最小费用的线花费更少。
因为只有四台主机需要连接，所以直接枚举这四台主机的连接情况即可，一个主机对应三种连接情况：连对面第一台，连对面最后一台，连对面中间花费最小的一台。
枚举第一列的头尾主机连接后就可以确定另一列的头尾主机怎么连了。

AC代码：

#include 
const long long inf = 1e18;
const int N = 2e5 + 5;
using namespace std;

int a[N], b[N];

long long ca1[4], ca2[4], cb1[4], cb2[4];

void solve()
{
    int n;
    long long ans = inf;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    ca1[1] = abs(a[1] - b[1]);
    ca1[3] = abs(a[1] - b[n]);
    ca2[1] = abs(a[n] - b[1]);
    ca2[3] = abs(a[n] - b[n]);
    cb1[1] = abs(b[1] - a[1]);
    cb1[3] = abs(b[1] - a[n]);
    cb2[1] = abs(b[n] - a[1]);
    cb2[3] = abs(b[n] - a[n]);
    ca1[2] = ca2[2] = cb1[2] = cb2[2] = inf;
    for (int i = 1; i <= n; i++)
    {
        if (abs(a[1] - b[i]) < ca1[2]) ca1[2] = abs(a[1] - b[i]);
        if (abs(a[n] - b[i]) < ca2[2]) ca2[2] = abs(a[n] - b[i]);
        if (abs(b[1] - a[i]) < cb1[2]) cb1[2] = abs(b[1] - a[i]);
        if (abs(b[n] - a[i]) < cb2[2]) cb2[2] = abs(b[n] - a[i]);
    }
    for (int a1 = 1; a1 <= 3; a1++) //1表示连对面第一台，2表示连中间花费最小的的，3表示连对面最后一台
    {
        for (int a2 = 1; a2 <= 3; a2++)
        {
            long long tmp = ca1[a1] + ca2[a2];
            if (a1 != 1 && a2 != 1) tmp += min({cb1[1], cb1[2], cb1[3]});
            if (a1 != 3 && a2 != 3) tmp += min({cb2[1], cb2[2], cb2[3]});
            ans = min(ans, tmp);
        }
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

D-Nearest Excluded Points

题目大意：
给定一个点集，求出每个点在点集以外曼哈顿距离最小的点。

思路：
如果一个点的上下左右有至少一个点是不在点集中的，那么这个点就是最小的曼哈顿距离点。
对于那些四周的点都在点集中的，将四周的点确定后就可以确定中间点的最小曼哈顿距离点。
就是一个BFS的过程，先将外围一圈的点入队，接着将里面一圈的点再入队。也可以先将不在点集中，但是与点集中的点相邻的点入队。因为坐标范围比较大，需要用pair 和 map进行存储
同时记录一下每个点的最小曼哈顿点。

AC代码：

#include 
const int N = 2e5 + 5;
using namespace std;
typedef pair<int, int> PII;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int x[N], y[N];
int n, xx, yy;
map<PII, bool> vis, inset;
map<PII, PII> root; //记录每个点的最小曼哈顿点
queue<PII> q;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i] >> y[i];
        inset[{x[i], y[i]}] = 1;
    }

    for (int i = 1; i <= n; ++i) //先将不在点集中，但是与点集中的点相邻的点入队
    {
        for (int j = 0; j < 4; j++)
        {
            xx = x[i] + dx[j];
            yy = y[i] + dy[j];
            if (!inset.count({xx, yy}) && !vis[{xx, yy}])
            {
                q.push({xx, yy});
                root[{xx, yy}] = {xx, yy};
                vis[{xx, yy}] = 1;
            }
        }
    }
    int cnt = 0;
    while (q.size())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            xx = x + dx[i];
            yy = y + dy[i];
            if (inset.count({xx, yy}) && !vis[{xx, yy}])
            {
                vis[{xx, yy}] = 1;
                root[{xx, yy}] = root[{x, y}];
                q.push({xx, yy});
                cnt++;
            }
        }
        if (cnt == n) break;
    }
    for (int i = 1; i <= n; i++)
        cout << root[{x[i], y[i]}].first << " " << root[{x[i], y[i]}].second << "\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60