AtCoder Regular Contest 092 解题报告

C – 2D Plane 2N Points

可以考虑先排个序，然后贪心的、暴力的处理即可。

@@ -0,0 +1,36 @@
// ARC092A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 210;

int n;
bool enabled[MAX_N];

struct point
{
    int x, y, typ;
    bool operator<(const point &rhs) const { return x < rhs.x; }
} pts[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= (n << 1); i++)
        scanf("%d%d", &pts[i].x, &pts[i].y), pts[i].typ = i > n;
    sort(pts + 1, pts + 1 + (n << 1));
    int ans = 0;
    for (int i = 1; i <= (n << 1); i++)
        if (pts[i].typ == 1)
        {
            int id = -1;
            for (int j = 1; j < i; j++)
                if (!enabled[j] && pts[j].typ == 0 && pts[j].y < pts[i].y && (id == -1 || pts[j].y > pts[id].y))
                    id = j;
            if (id != -1)
                enabled[id] = true, ans++;
        }
    printf("%d\n", ans);
    return 0;
}

D – Two Sequences

这个题还蛮有意思的，让我想起某个 Div.1 B。

我们可以从低位到高位考虑。设 \(T = p^b, mod = 2T\)，那么我们先把所有的 \(a_i, b_i\) 对 \(mod\) 取个模，然后可以发现的是，对于固定的 \(b_i\)，如果 \(T \leq a_i + b_i < 2T, 3T \leq a_i + b_i < 4T\)，那么这个位的贡献就是 \(1\)。我们可以在取模之后来二分出这个区间，得到答案。

@@ -0,0 +1,38 @@
// ARC092B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

int n, ai[MAX_N], bi[MAX_N], ta[MAX_N], tb[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &bi[i]);
    int ans = 0;
    for (int b = 0; b < 29; b++)
    {
        int T = 1 << b, mod = T << 1;
        for (int i = 1; i <= n; i++)
            ta[i] = ai[i] % mod, tb[i] = bi[i] % mod;
        sort(tb + 1, tb + 1 + n);
        int pans = 0;
        for (int i = 1; i <= n; i++)
        {
            int l = lower_bound(tb + 1, tb + 1 + n, T - ta[i]) - tb;
            int r = lower_bound(tb + 1, tb + 1 + n, mod - ta[i]) - tb;
            pans ^= (r - l) & 1;
            l = lower_bound(tb + 1, tb + 1 + n, T * 3 - ta[i]) - tb;
            r = lower_bound(tb + 1, tb + 1 + n, (mod << 1) - ta[i]) - tb;
            pans ^= (r - l) & 1;
        }
        ans += (pans << b);
    }
    printf("%d\n", ans);
    return 0;
}

E – Both Sides Merger

首先有一个性质：最后对答案贡献的数的下标奇偶性相同。这是个充要条件，所以我们可以直接分类讨论，得到最后的答案。

@@ -0,0 +1,47 @@
// ARC092C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1010;

typedef long long ll;

int n, ai[MAX_N];
ll sum[2];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), sum[i & 1] += max(0, ai[i]);
    if (max(sum[0], sum[1]) == 0)
    {
        int pos = max_element(ai + 1, ai + 1 + n) - ai;
        printf("%d\n%d\n", ai[pos], n - 1);
        for (int i = n; i > pos; i--)
            printf("%d\n", i);
        for (int i = pos - 1; i >= 1; i--)
            puts("1");
        return 0;
    }
    int parity = sum[1] >= sum[0];
    vector<int> pos, ans;
    for (int i = 1; i <= n; i++)
        if (ai[i] > 0 && i % 2 == parity)
            pos.push_back(i);
    for (int i = n; i > pos.back(); i--)
        ans.push_back(i);
    for (int i = 1; i < pos.front(); i++)
        ans.push_back(1);
    for (int i = 0, siz = pos.size(); i < siz - 1; i++)
    {
        for (int j = 0; j < ((pos[i + 1] - pos[i] - 1) >> 1); j++)
            ans.push_back(3);
        ans.push_back(2);
    }
    printf("%lld\n%lld\n", sum[parity], 1LL * ans.size());
    for (int v : ans)
        printf("%d\n", v);
    return 0;
}

F – Two Faced Edges

一种暴力做法是直接 \(\Theta(nm + m^2)\) 去做 Tarjan，但是会 gg。我们仔细思考一条边的方向对于 SCC 的影响。如果这个边反转之后并不能形成一个新的 SCC 或者是破坏原来的 SCC，那么这个就不会变。

我们发现一条边形成 SCC 和破坏 SCC 是独立影响的，所以我们分开考虑。破坏一个 SCC 当且仅当边 \((u, v)\) 反转之后 \(u\) 无法到达 \(v\)，这样我们确实破坏了一个 SCC。这个东西我们其实可以通过做不同顺序的 Tarjan 来得到不同的 dfn 和 low，进而判断是否有第二条路可走。

那么对于形成一个 SCC，当且仅当 \(b_i\) 无法到达 \(a_i\)。这个同理。这两个问题的结果进行异或之后就是答案了。

@@ -0,0 +1,63 @@
// ARC092D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1010, MAX_E = 2e5 + 200;

int n, m, mp[MAX_N][MAX_N], etot, ui[MAX_E], vi[MAX_E], p[MAX_N], q[MAX_N];
bool accessible[MAX_N][MAX_N], vis[MAX_N], enabled[MAX_N][MAX_N];
vector<int> G[MAX_N];

void mark(int u, int root)
{
    vis[u] = true, accessible[root][u] = true;
    for (int v : G[u])
        if (!vis[v])
            mark(v, root);
}

void markPos(int u)
{
    vis[u] = true;
    for (int v : G[u])
        if (!vis[v])
            p[v] = mp[u][v], markPos(v);
}

void markNeg(int u)
{
    vis[u] = true;
    int siz = G[u].size() - 1;
    for (int i = siz; i >= 0; i--)
    {
        int v = G[u][i];
        if (!vis[v])
            q[v] = mp[u][v], markNeg(v);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        ui[++etot] = u, vi[etot] = v;
        mp[u][v] = etot, G[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        mark(i, i), memset(vis, false, sizeof(vis));
    for (int i = 1; i <= n; i++)
    {
        markPos(i), memset(vis, false, sizeof(vis));
        markNeg(i), memset(vis, false, sizeof(vis));
        for (int v : G[i])
            if (p[v] != mp[i][v] || q[v] != mp[i][v])
                enabled[i][v] = true;
        memset(p, 0, sizeof(p)), memset(q, 0, sizeof(q));
    }
    for (int i = 1; i <= m; i++)
        puts((accessible[vi[i]][ui[i]] ^ enabled[ui[i]][vi[i]]) ? "diff" : "same");
    return 0;
}