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

A – Triangular Number 

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    cout << n * (n + 1) / 2 << endl;
}

B – No-Divisible Range 

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            ll sum = 0;
            for (int k = i; k <= j; ++k)
                sum += a[k];

            bool ok = 1;
            for (int k = i; k <= j; ++k)
            {
                if (sum % a[k] == 0)
                {
                    ok = 0;
                    break;
                }
            }

            if (ok)
                ++ans;
        }
    }

    cout << ans << endl;
}

C – Domino 

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int cnt = a[1];
    int ans = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (cnt >= i)
        {
            cnt = max(cnt, i + a[i] - 1);
            ++ans;
        }
        else
            break;
    }

    cout << ans << endl;
}

D – Reachability Query 2

算法：

    图论，\(dfs\)。

思路：

    询问当前点可不可以到达黑色节点等价于反向建图中黑色节点中可以到达该点。

    反向建图，对于当前要设置成黑色的节点，将它所有可以到达的节点都设置成黑色。

关键代码：

void miyan()
{
    int n, m, q;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[v].push_back(u);
    }

    vector<int> st(n + 1, 0);
    auto dfs = [&](auto &&self, int u) -> void
    {
        st[u] = 1;
        for (auto v : g[u])
        {
            if (st[v])
                continue;

            self(self, v);
        }
    };

    cin >> q;

    while (q--)
    {
        int op, u;
        cin >> op >> u;
        if (op == 1)
        {
            if (st[u])
                continue;

            dfs(dfs, u);
        }
        else
        {
            if (st[u])
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }
}

E – Cover query 

算法：

    区间合并。

思路：

    \(set\) 维护区间，每次设置黑色区间时都将相交的区间合并。

关键代码：

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

    set<pii> S;
    ll ans = 0;
    while (q--)
    {
        ll l, r;
        cin >> l >> r;

        auto p = S.lower_bound({l, -1});
        if (p != S.begin())
        {
            p = prev(p);

            if (p->second < l - 1)
                p = next(p);
        }

        int L = l, R = r;
        while (p != S.end())
        {
            if (p->first > R + 1)
                break;

            L = min(L, p->first);
            R = max(R, p->second);

            ans -= (p->second - p->first + 1);

            p = S.erase(p);
        }

        S.insert({L, R});
        ans += R - L + 1;

        cout << n - ans << endl;
    }
}

F – Cat exercise

    还没补。