链接：https://codeforces.com/contest/2153

A. Circle of Apple Trees

算法：

    贪心。

思路：

    不同元素的个数。

关键代码：

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

    cout << set(all(a)).size() << endl;
}

B. Bitwise Reversion

算法：

    位运算。

思路：

    无。

关键代码：

void miyan()
{
    ll x, y, z;
    cin >> x >> y >> z;

    ll a = x | z, b = x | y, c = y | z;

    if ((a & b) != x || (b & c) != y || (a & c) != z)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

C. Symmetrical Polygons

算法：

    计算几何，贪心，构造，排序。

思路：

    由三角形两边之和大于第三边可推广至多边形：最大的边小于前 i – 1 条边的和。

    要求对称，每次选两条相等的边。

    对于出现奇数次数的边，单独存储。

    最后可以选一条或者两条边。

    对于一条边选可选择最大的即可。

    对于两条边选尽可能大的边和次大边。

关键代码：

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

    map<ll, ll> m;
    for (auto x : a)
        ++m[x];

    ll sum = 0;
    ll tot = 0;
    vector<int> have;
    for (auto [val, cnt] : m)
    {
        ll t = cnt;
        if (cnt & 1)
        {
            have.push_back(val);
            --t;
        }

        sum += val * t;
        tot += t;
    }

    ranges::sort(have);

    bool ok1 = 0, ok2 = 0;
    ll ans = sum;
    ll len = have.size();
    for (int i = 0; i < len; ++i)
    {
        int a = have[i], b;
        if (a < sum)
        {
            ans = max(ans, sum + a);
            ok1 = 1;
        }

        if (i < len - 1)
        {
            b = have[i + 1];
            if (a + sum > b)
            {
                ans = max(ans, a + b + sum);
                ok2 = 1;
            }
        }
    }

    if ((ok2 && tot) || (!ok2 && ok1 && tot > 1) || (!ok1 && !ok2 && tot > 2))
        cout << ans << endl;
    else
        cout << 0 << endl;
}

D. Not Alone

算法：

    \(dp\)，贪心。

思路：

    结论：将数组分成长度为 \(2\) 或者 \(3\) 的段是最优的。

    长度为 \(2\) 的段代价为 \(abs(a_i – a_{i + 1})\)，长度为 \(3\) 的段代价为 \(max(a_{i – 1}, a_i, a_{i + 1}) – min(a_{i – 1}, a_i, a_{i + 1})\)。

    为什么长度为 \(2\) 的段或者长度为 \(3\) 的段是最优的。

    证明长度为 \(2\) 的段是最优的：

    对于一个长度为 \(m > 3\) 的相同块，记为 \(a_1, a_2, …………, a_m\)，要将全部元素都变为 \(x\)，所需的代价为 \(Σabs(a_i – x)\)，拿出最后两个使之成为单独块，记为 \(C\)，那么此时代价为 \(\sum_{i=1}^{m – 2} abs(a_i – x) + abs(a_m – a_{m – 1})\)，此时需要考虑 \(C\) 先的代价变化，既考虑 \(abs(a_{m – 1} – x) + abs(a_m – x)\) 和 \(abs(a_m – a_{m – 1})\) 的大小，不难发现只有 \(a_{m – 1}\) 或者 \(a_m\) 其中一个小于等于 \(x\) 或者 大于等于 \(x\)，而另一个要相反，既 \(a_{m – 1}\) 和 \(a_m\) 在 \(x\) 的两边。

    其他情况都是大于的。那么可知分成大小为两的块代价只会不变或者减少。

    长度为 \(3\) 的情况同理。

    通过以上证明，问题就转换为了将数组中的连续元素可以分成长度为 \(2\) 或者 \(3\) 的块，每个块需要变成一样的值，求最小代价。

    考虑 \(dp\) 解。

    如果数组不是环形的，\(dp[i] = min(dp[i], dp[i + 2] + abs(a_i – a_{i + 1}), dp[i + 3] + max(a_{i – 1}, a_i, a_{i + 1}) – min(a_{i – 1}, a_i, a_{i + 1}))\);

    考虑数组是环形，只需考虑 \(a_n, a_1\) 或者 \(a_{n – 1}, a_n, a_1\) 或者 \(a_n, a_1, a_2\) 在同一个块，对数组做一个循环移位即可。

关键代码：

const ll inf = 1e18;

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (auto &x : a | views::drop(1))
        cin >> x;

    ll ans = inf;
    for (int _ = 0; _ < 4; ++_)
    {
        vector<ll> dp(n + 1, inf);
        dp[0] = 0;
        for (int i = 2; i <= n; ++i)
        {
            dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - a[i - 1]));
            if (i > 2)
                dp[i] = min(dp[i], dp[i - 3] + max({a[i], a[i - 1], a[i - 2]}) - min({a[i], a[i - 1], a[i - 2]}));
        }

        for (int i = 1; i < n; ++i)
            swap(a[i], a[i + 1]);

        ans = min(ans, dp[n]);
    }

    cout << ans << endl;
}

E. Zero Trailing Factorial

    还没补。