C题

Problem - C - Codeforces

题意是有两排个n台计算机，要让他们连成一个网络，并且当某一台计算机坏掉，整个系统不会分成两个或更多的部分，当在两台计算机连线，会有|ai-bj|的代价，要求将两排计算机连成一个系统并且代价最低

首先分析可得，|a1-b1|+|an-bn|是一个解

|a1-b1|+|an-bi|+|bn-aj|也是一个解，同理|an-bn|+|a1-bi|+|b1-aj|也是一个解

|a1-bn|+|an-b1|也是一个解， |a1-bn| + |b1-ai|+|an-aj|也是一个解，|b1-an|+|bn-ai|+|a1-bj|也是一个解

以上为所有的情况，当时解题没考虑全，赛后看题解没想到可以分析的这么具体

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10, INF = 1e18;

int t;
int a[N];
int b[N];

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++)
    {
        cin >> b[i];
    }
    int res = min(abs(a[1] - b[1]) + abs(a[n] - b[n]), abs(a[1] - b[n]) + abs(a[n] - b[1]));

    int cnt_an_bi = INF, cnt_bn_ai = INF;
    int cnt_a1_bi = INF, cnt_b1_ai = INF;
    for (int i = 1; i <= n; i ++)
    {
        cnt_an_bi = min(cnt_an_bi, abs(a[n] - b[i]));
        cnt_bn_ai = min(cnt_bn_ai, abs(b[n] - a[i]));
        cnt_a1_bi = min(cnt_a1_bi, abs(a[1] - b[i]));
        cnt_b1_ai = min(cnt_b1_ai, abs(b[1] - a[i]));
    }
    res = min(res, abs(a[1] - b[1]) + cnt_an_bi + cnt_bn_ai);
    res = min(res, abs(a[n] - b[n]) + cnt_a1_bi + cnt_b1_ai);
    res = min(res, abs(a[1] - b[n]) + cnt_b1_ai + cnt_an_bi);
    res = min(res, abs(a[n] - b[1]) + cnt_a1_bi + cnt_bn_ai);
    res = min(res, cnt_a1_bi + cnt_an_bi + cnt_b1_ai + cnt_bn_ai);
    cout << res << endl;
}

main()
{
    cin >> t;
    while (t --)
    {
        solve();
    }
}

D题

Problem - D - Codeforces

刚开始自己看这个题想，这不就是个爆搜吗，写完之后在第九测试点MLE，再怎么优化都过不了，在网上找题解才发现自己搜的雀食太暴力了

题意

给出n个点（欧氏距离不多解释），要求给出距离每个点欧氏距离最近的点，这个点还不能是给出的n个点中的任何点

思路

MLE思路：存下每个点的坐标，给出的点用map记录是初始点，然后上下左右搜，搜到第一个不是初始点的输出。这个思路有个问题就是有可能所有点都入队，导致内存超限

AC思路：存下每个点坐标，给出的点用map记录是初始点，然后把每个点上下左右不是初始点的入队，上下左右搜一遍，搜到第一遍遍历到的初始点就将他入队等待下一轮搜索，同时将当前的点作为该初始点的答案

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 10;
const int down = -1e6, up = 1e6;

int n;
PII p[N], res[N];
queue<PII> q;
map<PII, int> mp, flag;
map<PII, PII> root;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void solve()
{
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        mp[{x, y}] = i;
        p[i] = {x, y};
    }

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < 4; j ++)
        {
            int x = p[i].first + dx[j], y = p[i].second + dy[j];
            if (!mp.count({x, y}))
            {
                q.push({x, y});
                root[{x, y}] = {x, y};
            }
        }

    while (!q.empty())
    {
        PII t = q.front();
        q.pop();

        for (int j = 0; j < 4; j ++)
        {
            int x = t.first + dx[j], y = t.second + dy[j];
            int fx = t.first, fy = t.second;

            if (mp.count({x, y}) && !flag.count({x, y}))
            {
                flag[{x, y}] = 1;
                root[{x, y}] = root[{fx, fy}];

                res[mp[{x, y}]] = root[{x, y}];
                q.push({x, y});
            }
        }
    }

    for (int i = 0; i < n; i ++)
        cout << res[i].first << ' ' << res[i].second << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    solve();
}

MLE代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 10;
const int down = -1e6, up = 1e6;

int n;
PII p[N];
queue<PII> q;
map<PII, int> mp;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void solve()
{
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        mp[{x, y}] = 1;
        p[i] = {x, y};
    }

    for (int i = 0; i < n; i ++)
    {
        q.push(p[i]);
        int x0 = p[i].first, y0 = p[i].second;

        bool flag = false;
        while (!q.empty())
        {
            PII t = q.front();
            q.pop();

            for (int j = 0; j < 4; j ++)
            {
                int x = t.first + dx[j], y = t.second + dy[j];

                if (x < down || x > up || y < down || y > up)
                    continue;
                if (x == x0 && y == y0)
                    continue;
                if (!mp.count({x, y}))
                {
                    cout << x << ' ' << y << endl;
                    flag = true;
                    queue<PII> tt;
                    q = tt;
                    break;
                }
                else
                {
                    q.push({x, y});
                }
            }
            if (flag)
                break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    solve();
}