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

A. Redstone?

算法：

    推公式。

思路：

    题目给出的每个齿轮的转数为：

\(\omega_k=\prod_{i=1}^{k-1}\frac{b_i}{b_{i+1}}=\frac{b_1}{b_k},\qquad
\omega_n=1\iff b_1=b_n.\)

关键代码：

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

    if (set(a.begin(), a.end()).size() == n)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

B. Villagers

算法：

    贪心。

思路：

    贪心策略：

• 对答案有影响的友谊只需建立 \(\left\lceil \frac{n}{2} \right\rceil\) 组即可，其余组使用怨气值已经变成 0 的人相连。
• 由于每两个之间对答案的贡献都为最大值，所有每次选择最大的和次大的即可。

关键代码：

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

    ranges::sort(a);

    ll ans = 0;
    for (int i = n - 1; i >= 0; i -= 2)
        ans += a[i];

    cout << ans << endl;
}

C. The Nether

    交互题先不补了。

D. Chicken Jockey

算法：

    \(dp\)，贪心。

思路：

    定义 \(dp[i]\) : 杀死第 \(i\) 只怪所需的最小操作次数。不用关心上方的怪，他们掉不掉都不会对 \(i\) 造成影响。

    边界：\(dp[0] = 0,dp[1] = a[1]\)

    对于每个怪只考虑以下情况：

• 先处理前 \(i – 1\) 个怪物，然后第 \(i\) 个怪物受到一点掉落伤害，需要再攻击 \(h[i] – 1\) 次，总代价为  \(dp[i – 1] + h[i] – 1\)。
• 直接杀死第 \(i – 1\) 个怪物，此时第 \(i\) 个怪物受到的掉落伤害为 \(i – 1\) 点，需要再攻击 \(max(0, h[i] – i + 1)\) 次。总代价为 \(dp[i – 2] + max(0, h[i] – i + 1)\) 。

    可以证明没有比这更优的方案。

关键代码：

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

    vector<ll> dp(n + 1);
    dp[0] = 0, dp[1] = a[1];
    for (int i = 2; i <= n; ++i)
        dp[i] = min(dp[i - 1] + a[i] - 1, dp[i - 2] + a[i - 1] + max(0ll, a[i] - i + 1));

    cout << dp[n] << endl;
}

E. I Yearned For The Mines

    还没补。