链接：https://atcoder.jp/contests/abc424

A – Isosceles

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int a, b, c;
    cin >> a >> b >> c;

    if (a == b || b == c || c == a)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B – Perfect

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector st(n + 1, vector<int>(m + 1, 0));
    while (k--)
    {
        int a, b;
        cin >> a >> b;
        st[a][b] = 1;

        if (accumulate(all(st[a]), 0) == m)
            cout << a << ' ';
    }

    cout << endl;
}

C – New Skill Acquired

算法：

    模拟，\(STL\)。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    ll ans = 0;
    vector<int> st(n + 1, 0);
    map<int, vector<int>> m;
    vector<int> ok;
    ok.reserve(n);
    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        cin >> x >> y;
        m[x].push_back(i);
        m[y].push_back(i);

        if (!x && !y)
        {
            st[i] = 1;
            ok.push_back(i);
            ++ans;
        }
    }

    for (int i = 0; i < ok.size(); ++i)
    {
        for (auto x : m[ok[i]])
        {
            if (!st[x])
            {
                ++ans;
                st[x] = 1;
                ok.push_back(x);
            }
        }
    }

    cout << ans << endl;
}

D – 2×2 Erasing 2

算法：

    暴搜。

思路：

    暴搜在每个 '#' 上转换成 '.' 的情况，暴搜出所有可能，更新最小答案即可。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i)
        cin >> g[i];

    ll ans = INT_MAX;
    auto dfs = [&](auto &&self, ll res, int x, int y) -> void
    {
        if (res >= ans)
            return;

        if (y == m)
            ++x, y = 0;

        if (x == n)
        {
            ans = res;
            return;
        }

        if (g[x][y] == '.')
            return self(self, res, x, y + 1);

        if (!x || !y || g[x - 1][y - 1] == '.' || g[x - 1][y] == '.' || g[x][y - 1] == '.')
            self(self, res, x, y + 1);

        g[x][y] = '.';
        self(self, res + 1, x, y + 1);
        g[x][y] = '#';
    };

    dfs(dfs, 0, 0, 0);

    cout << ans << endl;
}

E – Cut in Half

算法：

    堆。

思路：

    在大根堆中存储每个元素的值和出现次数，每次对相等的全部元素分割，最后再遍历堆，取第 \(x\) 大的数即可。

关键代码：

void miyan()
{
    ll n, k, x;
    cin >> n >> k >> x;
    map<double, int> m;
    for (int i = 0; i < n; ++i)
    {
        double x;
        scanf("%lf", &x);
        ++m[x];
    }

    priority_queue<pair<double, ll>> q;
    for (auto [x, y] : m)
        q.push({x, y});

    while (k)
    {
        auto [val, cnt] = q.top();
        q.pop();

        if (k >= cnt)
        {
            q.push({val / 2.0, cnt * 2ll});
            k -= cnt;
        }
        else
        {
            q.push({val, cnt - k});
            q.push({val / 2.0, k * 2ll});
            k = 0;
        }
    }

    while (q.size())
    {
        auto [val, cnt] = q.top();
        q.pop();

        if (cnt >= x)
        {
            printf("%.15lf\n", val);
            return;
        }

        x -= cnt;
    }
}

F – Adding Chords

算法：

    线段树。

思路：

    可以发现在圆上两条线段 \([a, b](a < b)\)，\([c, d](c < d)\) 相交需要满足 \(a < c < b < d\) 或者 \(c < a < d < b\)。

    那么对于当前线段只需寻找起点在 \([a – 1, b – 1]\) 之间并且终点在 \(b\) 后面的点，如果存在就说明相交。

    另一个条件同理，只需寻找终点在 \([a – 1, b – 1]\) 之间并且起点在 \(a\) 前面的点，如果存在就说明相交。

    \(n\) 的级别为 \(1e6\)。使用线段树维护，要判断当前线段与之前线段会不会相交，只需判断以上两个条件都不满足即可。

    既在起点区间 \([a – 1, b – 1]\) 之间找最大的终点，其值小于等于 \(b\)，并且在终点区间 \([a – 1, b – 1]\) 之间找最小的起点，其值大于等于 \(a\)。

关键代码：

template <typename T>
struct SegmentTreeMin
{
    struct Node
    {
        int l, r;
        T minn;
    };

    // 线段树大小
    int N;
    vector<Node> tr;
    vector<T> v;

    SegmentTreeMin(int _N, const vector<T> &_v)
    {
        N = _N;
        v.resize(N + 10);
        for (int i = 1; i <= N; ++i)
            v[i] = _v[i];
        tr.resize(4 * N);
        build(1, 1, N);
    }

// 左右子区间
#define LC (u << 1)
#define RC ((u << 1) | 1)

    inline void pushup(int u)
    {
        tr[u].minn = min(tr[LC].minn, tr[RC].minn);
    }

    inline void build(int u, int l, int r)
    {
        if (l == r)
        {
            tr[u] = {l, r, v[l]};
            return;
        }

        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(LC, l, mid);
        build(RC, mid + 1, r);
        pushup(u);
    }

    inline T query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r)
            return tr[u].minn;

        int mid = tr[u].l + tr[u].r >> 1;
        T ans = std::numeric_limits<T>::max(); // 当前类型能表示的最大值
        if (l <= mid)
            ans = min(ans, query(LC, l, r));
        if (r > mid)
            ans = min(ans, query(RC, l, r));
        return ans;
    }

    inline void update(int u, int x, T val)
    {
        if (tr[u].l == x && tr[u].r == x)
        {
            tr[u].minn = val;
            return;
        }

        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            update(LC, x, val);
        else
            update(RC, x, val);
        pushup(u);
    }

    inline T query(int l, int r) { return query(1, l, r); }

    inline void update(int x, T val) { update(1, x, val); }
};

template <typename T>
struct SegmentTreeMax
{
    struct Node
    {
        int l, r;
        T maxx;
    };

    // 线段树大小
    int N;
    vector<Node> tr;
    vector<T> v;

    SegmentTreeMax(int _N, const vector<T> &_v)
    {
        N = _N;
        v.resize(N + 10);
        for (int i = 1; i <= N; ++i)
            v[i] = _v[i];
        tr.resize(4 * N);
        build(1, 1, N);
    }

// 左右子区间
#define LC (u << 1)
#define RC ((u << 1) | 1)

    inline void pushup(int u)
    {
        tr[u].maxx = max(tr[LC].maxx, tr[RC].maxx);
    }

    inline void build(int u, int l, int r)
    {
        if (l == r)
        {
            tr[u] = {l, r, v[l]};
            return;
        }

        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(LC, l, mid);
        build(RC, mid + 1, r);
        pushup(u);
    }

    inline T query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r)
            return tr[u].maxx;

        int mid = tr[u].l + tr[u].r >> 1;
        T ans = std::numeric_limits<T>::min(); // 当前类型能表示的最大值
        if (l <= mid)
            ans = max(ans, query(LC, l, r));
        if (r > mid)
            ans = max(ans, query(RC, l, r));
        return ans;
    }

    inline void update(int u, int x, T val)
    {
        if (tr[u].l == x && tr[u].r == x)
        {
            tr[u].maxx = val;
            return;
        }

        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            update(LC, x, val);
        else
            update(RC, x, val);
        pushup(u);
    }

    inline T query(int l, int r) { return query(1, l, r); }

    inline void update(int x, T val) { update(1, x, val); }
};

void miyan()
{
    int n, q;
    cin >> n >> q;

    SegmentTreeMin<int> segmin(n, vector<int>(n + 1, INT_MAX));
    SegmentTreeMax<int> segmax(n, vector<int>(n + 1, INT_MIN));

    while (q--)
    {
        int a, b;
        cin >> a >> b;

        int val1 = segmin.query(a + 1, b - 1);
        int val2 = segmax.query(a + 1, b - 1);

        if (val1 >= a && val2 <= b)
        {
            cout << "Yes" << endl;
            segmin.update(b, a);
            segmax.update(a, b);
        }
        else
            cout << "No" << endl;
    }
}

G – Set list

    还没补。