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

A – Stage Clear

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    string s;
    cin >> s;

    if (s[2] >= '8')
        s[0] = s[0] + 1, s[2] = '1';
    else
        s[2] = s[2] + 1;

    cout << s << endl;
}

B – Looped Rope

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (auto &x : s)
        cin >> x;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (s[i][j] == '#')
            {
                ll cnt = 0;
                for (int k = 0; k < 4; ++k)
                {
                    int a = i + dx[k], b = j + dy[k];

                    if (a >= 0 && a < n && b >= 0 && b < m && s[a][b] == '#')
                        ++cnt;
                }

                if (cnt != 2 && cnt != 4)
                {
                    cout << "No" << endl;
                    return;
                }
            }
        }
    }

    cout << "Yes" << endl;
}

C – AtCoder AAC Contest

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    ll a, b, c;
    cin >> a >> b >> c;

    ll t = min({a, b, c});
    ll ans = t;
    a -= t, b -= t, c -= t;
    ans += min({a, c, (a + c) / 3});

    cout << ans << endl;
}

D – Least Unbalanced

算法：

    构造，找规律，分治。

思路：

    玩几组样例后不难发现答案只有两种情况 \(0\) 和 \(1\)。

• 当 \(k\) 是 \(2 ^ n\) 的倍数时，全部构造一样的值，答案就为 \(0\)，每个元素为 \(k / 2 ^ n\)。
• 如果不是 \(2 ^ n\) 的倍数，通过分治均匀的构造每个值即可，答案为 \(1\)。

关键代码：

void solve()
{
    ll n, k;
    cin >> n >> k;

    n = 1 << n;
    if (k % n == 0)
    {
        cout << 0 << endl;

        for (int i = 0; i < n; ++i)
            cout << k / n << ' ';
        cout << endl;

        return;
    }

    cout << 1 << endl;

    vector<ll> a(n + 1, 0);
    auto dfs = [&](auto &&self, int l, int r, ll cnt) -> void
    {
        ll val = cnt / (r - l + 1);
        for (int i = l; i <= r; ++i)
            a[i] += val;

        cnt -= (r - l + 1) * val;

        if (l < r)
        {
            int mid = r - l - 1 >> 1;
            self(self, l, l + mid, ((cnt & 1) ? cnt / 2 + 1 : cnt / 2));
            self(self, l + mid + 1, r, cnt / 2);
        }
    };

    dfs(dfs, 1, n, k);

    for (auto x : a | views::drop(1))
        cout << x << ' ';
    cout << endl;
}

E – Colinear

算法：

    随机化，概率。

思路：

    假设存在一条直线 \(ax + by + c = 0\) 穿过超过一半的点，则该直线上至少有 \(\frac{n + 1}{2}\) 个点。因此，若从 \(n\) 个点中随机选取两点，它们同时位于该直线上的概率为：

\(\frac{\frac{n+1}{2}}{n} \cdot \frac{\frac{n+1}{2} – 1}{n-1}= \frac{n+1}{4n} > \frac{1}{4}\)

    可以理解为如果一条直线为答案，那么两点同时在该直线上的概率为 \(\frac{1}{4}\) ，不在的概率为 \(\frac{3}{4}\)，假设我们猜 \(100\) 次，全部错误的概率为 \((\frac{3}{4}) ^ {100}\)，这个概率非常小，几乎可以看做如果存在答案\(100\)次猜出来的概率为 \(100%\)。

    由两点式可知直线方程为：

\(\frac{x – x_{1}}{x_{2} – x_{1}} = \frac{y – y_{1}}{y_{2} – y_{1}} \Rightarrow (x – x_{1})(y_{2} – y_{1}) = (y – y_{1})(x_{2} – x_{1})\)

    转换成一般式得：

\((y_{1} – y_{2})x + (x_{2} – x_{1})y + x_{1}y_{2} – x_{2}y_{1} = 0\)

    此时：

• \(a = (y_{1} – y_{2})\)
• \(b = (x_{2} – x_{1})\)
• \(c = x_{1}y_{2} – x_{2}y_{1}\)

    剩下直接随机找两点，求出直线方程，判断是否有超过一半点在直线上即可。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<ll> x(n), y(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];

    srand(time(0));
    for (int k = 1; k <= 200; ++k)
    {
        ll pos1 = rand() % n, pos2 = rand() % n;

        if (pos1 == pos2)
            continue;

        ll a = y[pos2] - y[pos1];
        ll b = x[pos1] - x[pos2];
        ll c = x[pos2] * y[pos1] - x[pos1] * y[pos2];

        ll cnt = 0;
        for (int i = 0; i < n; ++i)
            if (a * x[i] + b * y[i] + c == 0)
                ++cnt;

        if (cnt > n / 2)
        {
            cout << "Yes" << endl;
            cout << a << ' ' << b << ' ' << c << endl;
            return;
        }
    }

    cout << "No" << endl;
}

F – Eat and Ride

    树形dp先不补了。