比赛链接
Solved: 4/6
A. Redstone?
题意
给一个序列，问能否重排使得 \(\prod_{i=1}^{n-1} \frac {a_i}{a_{i+1}} = 1\)。
题解
当且仅当存在两个数相等。
bool solve(){int n; cin >> n;vector <int> a(n); cin >> a;sort(all(a));for (int i=0; i<n-1; ++i) if (a[i] == a[i+1]) return 1;return 0;
}
B. Villagers
题意
有 \(n\) 个点，每次可以给其中任意两个点连边，代价为它们点权的 max，同时它们的点权会同时减少 min。求将所有点连通所需最小代价。
题解
从大到小排序，让第 \(2k-1\) 大的和第 \(2k\) 大的连边，如果一共有奇数个就随便取一个 0 和最小的连边。剩下的都连 0 和 0 即可。
void solve(){int n; cin >> n;vector <int> a(n); cin >> a;sort(all(a));ll ans = 0;for (int i=n-1; i>=0; i -= 2) ans += a[i];cout << ans << '\n';
}
C. The Nether
题意
交互题。有一张 \(n\) 个点的 DAG，每次可询问一个起点和一个点集，交互器会给出从这个起点出发，仅经过这个点集时最长路经过的点数。求原图中的一条最长路（起点任意）。询问次数不超过 \(2n\)。
题解
首先让每个点作为起点询问全图的最长路 \(f_1, \dots, f_n\)。假设最大值是 \(m\)。任取一个 \(f_x = m\) 的点 \(x\) 作为起点。
对所有 \(f_y = m-1\) 的 \(y\) 询问 \((x,y)\) 是否存在（这只需令起点为 \(x\)，点集为 \(\{x,y\}\) 即可），
任取一个边 \((x,y)\) 存在的 \(y\)（考虑 DAG 最长路的 dp 过程，这样的 \(y\) 一定存在）作为第二个点。
然后令 \(x\leftarrow y\) 重复上述过程即可找到这条路径上所有的点。
因为每个点只会作为 \(y\) 至多一次，所以这部分询问次数不会超过 \(n\)。加上一开始询问 \(f\) 的次数，总询问次数不超过 \(2n\)。
int ask(int x, const vector <int>& s)
{cout << "? " << x << ' ' << s.size() << ' ';for (int u: s) cout << u << ' ';cout << endl;cout.flush();int res;cin >> res;return res;
}void solve(){int n; cin >> n;vector <int> s;vector <vector<int>> buc(n+1);for (int i=1; i<=n; ++i) s.push_back(i);int m = 0;for (int i=1; i<=n; ++i){int l = ask(i, s);buc[l].push_back(i);m = max(m, l);}vector <int> ans(m+1);ans[m] = buc[m][0];for (int i=m-1; i; --i){for (int v: buc[i]){if (ask(ans[i+1], {ans[i+1], v}) == 2){ans[i] = v;break;}}}cout << "! " << m << ' ';for (int i=m; i; --i) cout << ans[i] << ' ';cout << endl;cout.flush();
}
D. Chicken Jockey
题意
有 \(n\) 个障碍，从低到高生命值为 \(a_1,\dots,a_n\)。每次可以选择一个障碍 \(i\) 攻击，使其生命值减少 \(1\)。
如果某个障碍的生命值 \(\leq 0\)，它会消失且上方的所有障碍就会掉落并形成新的一堆障碍，顺序不变，同时它上方的第一个障碍会减少其高度点生命值。
求最少的攻击次数使所有障碍消失。
题解
从上到下消除显然是更优的，因为这样可以让掉落的贡献最大化。
dp，设 \(f_i\) 为清空 \(i\) 以上的障碍所需最少的攻击次数，枚举上一次清空的位置 \(j\) 转移，可得 dp 方程
维护 \(f_{j+1} + s_j - j\) 的最大值，转移复杂度 \(O(1)\)，总复杂度 \(O(n)\)。
void solve(){int n; cin >> n;vector <int> a(n+2);vector <ll> s(n+2), f(n+2);for (int i=1; i<=n; ++i) cin >> a[i], s[i] = s[i-1] + a[i];ll mn = INF;for (int i=n; i; --i){f[i] = min(f[i+1] + a[i], i == n ? INF : mn + a[i] + max(0, a[i+1] - i) - s[i+1] + i+1);mn = min(mn, f[i+1] + s[i] - i);}cout << f[1] << '\n';
}