OI

AtCoder Grand Contest 032 – 解题报告

A – Limited Insertion

这个 \(n \leq 100\),考虑最后一次插入,然后复原出来即可。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110;

int n, ai[MAX_N];
vector<int> seq;

int main()
{
    bool valid = true;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), seq.push_back(ai[i]);
    stack<int> st;
    while (!seq.empty())
    {
        int pos = 0;
        for (int i = 0, siz = seq.size(); i < siz; i++)
            if (seq[i] == i + 1)
                pos = i + 1;
        if (pos == 0)
            puts("-1"), exit(0);
        seq.erase(seq.begin() + pos - 1);
        st.push(pos);
    }
    while (!st.empty())
        printf("%d\n", st.top()), st.pop();
    return 0;
}

B – Balanced Neighbors

随手画一画,发现完全图可以做到对于每一个 \(i\) 有 \(S_i = \frac{n(n + 1)}{2} – i\),那么其实如果是偶数图,我们完全可以舍弃掉一个 \(n\),也就是不连接 \(n – i\)。如果是奇数图,我们把配对和固定为 \(n – 1\),所有的点都连接 \(n\) 即可。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110;

int n;

int main()
{
    scanf("%d", &n);
    int b = n & 1;
    n -= b;
    vector<pair<int, int>> ansBox;
    for (int i = 1; i <= (n << 1); i++)
    {
        for (int j = i + 1; j <= n; j++)
            if (j != i && j != (n - i + 1))
                ansBox.push_back(make_pair(i, j));
    }
    if (b)
    {
        n += b;
        for (int i = 1; i < n; i++)
            ansBox.push_back(make_pair(i, n));
    }
    printf("%lld\n", 1LL * ansBox.size());
    for (auto x : ansBox)
        printf("%d %d\n", x.first, x.second);
    return 0;
}

C – Three Circuits

令人无语的结论题。

首先度数都要是偶数。然后考虑中枢节点,那么如果最大度数大于 \(4\),那么显然可以对边进行染色得到三个欧拉子图。如果度数为 \(4\),那么如果存在以下情况则存在划分方式,否则 GG:

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, head[MAX_N], current, deg[MAX_N], A, B;
bool vis[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fa)
{
    vis[u] = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (i != fa && edges[i].to != B)
            if (!vis[edges[i].to])
                dfs(edges[i].to, i ^ 1);
            else
                puts("Yes"), exit(0);
    vis[u] = false;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u), deg[u]++, deg[v]++;
    int mdeg = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] & 1)
            puts("No"), exit(0);
        else
            mdeg = max(mdeg, deg[i]);
    if (mdeg == 4)
    {
        for (int i = 1; i <= n; i++)
            if (deg[i] == 4)
                if (A == 0)
                    A = i;
                else if (B == 0)
                    B = i;
                else
                    puts("Yes"), exit(0);
        if (B)
            dfs(A, 0);
        puts("No"), exit(0);
    }
    else if (mdeg > 4)
        puts("Yes"), exit(0);
    else
        puts("No"), exit(0);
    return 0;
}

D – Rotation Sort

其实就是用 \(A\) 的代价把该元素放到右边任意区域、\(B\) 代价把该元素放到左边任意区域。做个 DP 吧。

// D.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 5e3 + 200;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, A, B, pi[MAX_N], pos[MAX_N];
ll dp[MAX_N][MAX_N];

int main()
{
    scanf("%d%d%d", &n, &A, &B);
    for (int i = 1; i <= n; i++)
        scanf("%d", &pi[i]), pos[pi[i]] = i;
    memset(dp, 0x3f, sizeof(dp)), dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
            if (dp[i - 1][j] != INF)
                if (pos[i] > pos[j])
                {
                    dp[i][i] = min(dp[i][i], dp[i - 1][j]);
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + B);
                }
                else
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + A);
    }
    printf("%lld\n", *min_element(dp[n], dp[n] + 1 + n));
    return 0;
}

E – Modulo Pairing

先排序,然后通过扰动法获得结论:存在一个分割点,使得前半部分匹配都小于 \(M\)、后半部分匹配都大于 \(M\)。这个点可以 check,且我们尽量需要一个更靠左的节点(贪心)。

// E.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

int n, m, ai[MAX_N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        scanf("%d", &ai[i]);
    sort(ai + 1, ai + 1 + 2 * n);
    int l = 0, r = n, res;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        bool valid = true;
        for (int i = 2 * mid + 1; i <= (n << 1); i++)
            if (ai[i] + ai[2 * n + 2 * mid + 1 - i] < m)
            {
                valid = false;
                break;
            }
        if (valid)
            r = mid - 1, res = mid;
        else
            l = mid + 1;
    }
    int pos = res << 1;
    int ans = 0;
    for (int i = 1; i <= pos; i++)
        ans = max(ans, ai[i] + ai[pos - i + 1]);
    for (int i = pos + 1; i <= (n << 1); i++)
        ans = max(ans, (ai[i] + ai[(n << 1) + pos - i + 1]) % m);
    printf("%lld\n", ans);
    return 0;
}

kal0rona

http://kaloronahuang.com

江西师大附中全机房最弱