CF2133A. Redstone?

不难发现

$$\prod \frac{b_i}{b_{i+1}} = \frac{b_1}{b_n}$$

开一个 set，找有没有相同的即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        set<int> s;
        bool ans = false;
        
        for (int i=1; i<=n; i++) {
            int a;
            cin >> a;
            if (s.count(a)) {
                ans = true;
            }
            s.insert(a);
        }
        
        cout << (ans? "YES\n" : "NO\n");
    }
    
    return 0;
}

CF2133B. Villagers

样例启示我们：将 $g_i$ 两两配对，接下来将每一对合并。之后这一对较小的一个会减到 $0$，于是可以用 $\max(0,0)=0$ 的绿宝石连接每一对。对于奇数个，会多出来一个孤立的，把它和任意一个 $0$ 合并。

为什么是最优的？

Lemma 1. 最大的 $g_i$ 一定会计入代价。

Lemma 2. 若一种状态的数字完全小于另一种，则小的方案一定不劣。

Lemma 3. 在一个连通块内，用数字小的代替数字大的一定不劣。

综合以上三点，由 Lemma 1，从最大的开始模拟；由于 Lemma 3，之后连通块一定会变成相当于一个 $0$；而由 Lemma 2，则知道一定要把次大的变成 $0$ 最优。此时出现了一个更小的子问题，归纳即可。

证毕。

又：不开 long long 见祖宗。

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+100;
int g[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i=1; i<=n; i++) {
            cin >> g[i];
        }
        
        sort(g+1, g+n+1);
        long long ans = 0;
        for (int i=n; i>=1; i-=2) {
            ans += g[i];
        }
        cout << ans << '\n';
    }
    
    return 0;
}

CF2133C. The Nether

很久没做过猜谜的交互题了。

一个兜底方案是每次询问 $(\{u,v\}, u)$，就能知道他们之间有没有边。但是纯粹的暴力只能过 $n=2,3$ 的情况。

先考虑如何找到最长路的长度。最容易想到的方法是对每个 $u$ 询问 $d_u =(V, u)$，然后取最大值。

如此，我们不仅找到了最长路，还找到它的起点。那么怎么确定它的方案呢？

最长路 $p_i$ 一定满足 $d_{p_i} = d_{p_{i+1}} + 1$。

如何在众多可能的 $P_i = \{v \in V \mid d_v = d_{p_{i-1}} - 1\}$ 中找到合适的？

只需使用兜底方案，把每个候选问一遍就行。

找长度和起点用了 $n$ 次询问，找路径用了 $(n - \#\operatorname{arg max} d_u)$ 次询问（起点不用找），可以过。

#include <bits/stdc++.h>
using namespace std;

const int maxn=512;
vector<int> dd[maxn];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i=1; i<=n; i++) {
            dd[i].clear();
        }
        
        int maxd=0, start=0;
        for (int u=1; u<=n; u++) {
            printf("? %d %d ", u, n);
            for (int j=1; j<=n; j++) {
                printf("%d ", j);
            }
            printf("\n");
            fflush(stdout);
            
            int d;
            scanf("%d", &d);
            dd[d].push_back(u);
            
            if (d > maxd) {
                maxd = d;
                start = u;
            }
        }
        
        vector<int> path = {start};
        for (int d=maxd-1; d>=1; d--) {
            for (int v: dd[d]) {
                printf("? %d 2 %d %d\n", path.back(), path.back(), v);
                fflush(stdout);
                int res;
                scanf("%d", &res);
                
                if (res == 2) {
                    path.push_back(v);
                    break;
                }
            }
        }
        
        printf("! %d ", maxd);
        for (int v: path) {
            printf("%d ", v);
        }
        printf("\n");
        fflush(stdout); 
    }
    
    return 0;
}

CF2133D. Chicken Jockey

需要最大化摔伤的收益。

手玩样例发现摔伤有两种策略：

1. 手打掉一个怪，让上面的怪掉下来。
2. 从最底下的怪开始打。

可以证明：所有策略经过交换步骤（不会变劣）之后都可以变成先 1 后 2 的策略。（这个很难发现，我是看了提示的）

考虑 dp，设杀死 $1 \sim i$，且 $i$ 以策略 $s \in \{1,2\}$ 杀死的最小攻击次数为 $f(i,s)$，则

$$\begin{aligned} f(0,2)&=0, f(0,1)=+\infty,\\ f(i,1) &= \min\{f(i-1,1)+h_i-1, f(i-1,2)+\max\{h_i-i+1,0\}\} \\ f(i,2) &= f(i-1,1) + h_i \qquad \text{(连续的 2 总是更劣)} \end{aligned}$$

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=2e5+100, inf=0x3f3f3f3f3f3f3f3f;
int h[maxn], f[maxn][4];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i=1; i<=n; i++){
            cin >> h[i];
        }
        
        f[0][1] = inf;
        f[0][2] = 0;
    
        for (int i=1; i<=n; i++) {
            f[i][1] = min(
                f[i-1][1] + h[i] - 1,
                f[i-1][2] + max(h[i]-i+1, 0ll)
            );
            f[i][2] = f[i-1][1] + h[i];
        }
        
        cout << f[n][1] << '\n';
    }
    
    return 0;
}

CF2133E. I Yearned For The Mines

根据提示，看看链怎么做，显然用操作 1 扫一遍就行。

于是考虑先用操作 2 把树拆成链，然后把每条链扫一遍（注意孤点也要扫）

由于所有点都要扫一遍，这意味着使用操作 2 的次数不能超过 $\dfrac{n}{4}$，考虑怎么最小化这个次数。

使用树形 dp：

• $f(u)$：删除 $u$ 之后，$u$ 所在子树成链森林的最小删除次数；
• $g(u)$：不删除 $u$，$u$ 所在子树成链森林且 $u$ 的度为 $1$ 的最小删除次数；
• $h(u)$：不删除 $u$，$u$ 所在子树成链森林且 $u$ 的度为 $2$ 的最小删除次数.

对于 $u \in \text{leaves}$

$$\begin{aligned} f(u) &= 1 \\ g(u) &= 0 \\ h(u) &= +\infty \end{aligned}$$

而对 $u$ 的所有儿子 $v_i$，按照 $g(u)-f(u)$ 升序排序之后，

$$\begin{aligned} f(u) &= 1 + \sum_{v \in \operatorname{son} u} \min\{f(v), g(v), h(v)\} \\ g(u) &= \min\{f(v_1), g(v_1)\} + f(v_2) + f(v_3) + \cdots \\ h(u) &= g(v_1) + g(v_2) + f(v_3) + \cdots \end{aligned}$$

dp 完再 dfs 一遍即可得到链。