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

A – CBC

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    string s;
    cin >> s;
    string ans;
    for (auto c : s)
    {
        if (c <= 'Z' && c >= 'A')
            ans.push_back(c);
    }

    cout << ans << endl;
}

B – Restaurant Queue

算法：

    模拟。

思路：

    无。

关键代码：

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

    queue<int> q;
    while (Q--)
    {
        int op, x;
        cin >> op;
        if (op == 1)
        {
            cin >> x;
            q.push(x);
        }
        else
        {
            cout << q.front() << endl;
            q.pop();
        }
    }
}

C – Dislike Foods

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<set<int>> a(n + 1);
    vector<int> cnt(m + 1);
    for (int i = 1; i <= m; ++i)
    {
        int k;
        cin >> k;
        cnt[i] = k;
        while (k--)
        {
            int x;
            cin >> x;
            a[x].insert(i);
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;

        for (auto val : a[x])
        {
            if (--cnt[val] == 0)
                ++ans;
        }
        a[x].clear();

        cout << ans << endl;
    }
}

D – Line Crossing

算法：

    几何。

思路：

    这个题目不要死脑筋，要绕个弯，相交的直线对数 = 总直线对数 – 平行的直线对数。

    总直线对数就是 \(C_m^2 = \frac{m \cdot (m – 1)}{2}\)。

    对于平行的直线对数，可以发现在圆上平行的直线其在圆弧上的中点是一样的，如图所示：

    先求出所有中点相同的点，那么对于每个中点，其个数为 t_i，那么对于这个中点，其平行直线对数为：\(C_m^2 = \frac{t_i \cdot (t_i – 1)}{2}\)

关键代码：

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

    map<ll, ll> cnt;
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;

        ll s = x + y;
        if (s > n)
            s -= n;
        ++cnt[s];
    }

    ll ans = m * (m - 1ll) / 2ll;
    for (auto [_, x] : cnt)
        ans -= x * (x - 1ll) / 2ll;

    cout << ans << endl;
}

E – Payment Required

    概率 \(dp\) 以后再补。