外观
CF2133: Minecraft
CF2133A. Redstone?
不难发现
∏bi+1bi=bnb1
开一个 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
样例启示我们:将 gi 两两配对,接下来将每一对合并。之后这一对较小的一个会减到 0,于是可以用 max(0,0)=0 的绿宝石连接每一对。对于奇数个,会多出来一个孤立的,把它和任意一个 0 合并。
为什么是最优的?
Lemma 1. 最大的 gi 一定会计入代价。
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 询问 du=(V,u),然后取最大值。
如此,我们不仅找到了最长路,还找到它的起点。那么怎么确定它的方案呢?
最长路 pi 一定满足 dpi=dpi+1+1。
如何在众多可能的 Pi={v∈V∣dv=dpi−1−1} 中找到合适的?
只需使用兜底方案,把每个候选问一遍就行。
找长度和起点用了 n 次询问,找路径用了 (n−#argmaxdu) 次询问(起点不用找),可以过。
#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 的策略。(这个很难发现,我是看了提示的)
考虑 dp,设杀死 1∼i,且 i 以策略 s∈{1,2} 杀死的最小攻击次数为 f(i,s),则
f(0,2)f(i,1)f(i,2)=0,f(0,1)=+∞,=min{f(i−1,1)+hi−1,f(i−1,2)+max{hi−i+1,0}}=f(i−1,1)+hi(连续的 2 总是更劣)
#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 的次数不能超过 4n,考虑怎么最小化这个次数。
使用树形 dp:
- f(u):删除 u 之后,u 所在子树成链森林的最小删除次数;
- g(u):不删除 u,u 所在子树成链森林且 u 的度为 1 的最小删除次数;
- h(u):不删除 u,u 所在子树成链森林且 u 的度为 2 的最小删除次数.
对于 u∈leaves
f(u)g(u)h(u)=1=0=+∞
而对 u 的所有儿子 vi,按照 g(u)−f(u) 升序排序之后,
f(u)g(u)h(u)=1+v∈sonu∑min{f(v),g(v),h(v)}=min{f(v1),g(v1)}+f(v2)+f(v3)+⋯=g(v1)+g(v2)+f(v3)+⋯
dp 完再 dfs 一遍即可得到链。