CF901D2[A-D]
A. Jellyfish and Undertale[分类讨论]
弗洛伊在斯诺丁安置了一枚炸弹!
炸弹的计时器初始设置为$b$。计时器将每秒减少$1$。
当计时器达到$0$时,炸弹将会爆炸!为了让斯诺丁的居民有足够的时间撤离,你需要尽可能推迟炸弹爆炸的时间。您有$n$个工具。每个工具只能使用最多一次。如果使用第$i$个工具,计时器将增加$x_i$。
但是,如果计时器更改为大于$a$的整数,则由于错误,计时器将设置为$a$。更具体地说,以下事件将按以下顺序每秒发生一次:
- 你会选择一些(可能没有)
你以前没有用过的工具。如果您选择第$i$个工具,并且炸弹的计时器当前设置为$c$,则计时器将更改为$\min(c + x_i, a)$。
- 计时器减少$1$。3. 如果计时器达到$0$,炸弹就会爆炸。
水母现在想知道,如果工具得到最佳使用,炸弹爆炸的最长时间(以秒为单位)。
那么我们肯定要让工具没有使用完的时候,计时器的秒数大于0
也就是如果使用工具的话,在秒数为1的时候使用是最佳的
因为此时可以将工具的溢出值降到最低
但是还是会有溢出值的,那么就分类讨论一下就好了
如果$1+当前的值>最大值$
那么就加上$最大值-1$
如果没溢出就加上$当前的值$
code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
int a, b;
std::cin >> a >> b >> n;
std::vector<int> x(n);
for (auto &it : x) {
std::cin >> it;
}
sort(begin(x), end(x));
int ans = b;
for (auto it : x) {
ans += (it >= a ? a - 1 : it);
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
int __;
std::cin >> __;
while (__--) solve();
return 0;
}
B. Jellyfish and Game[分类讨论,排序]
水母$A$有$n$个值为$a_1, a_2, \dots, a_n$的青苹果,
水母$B$有$m$个值为$b_1,b_2,\ldots,b_m$的青苹果。
他们将玩$k$回合的游戏。
对于此顺序中的$i=1,2,\ldots,k$,它们将执行以下操作:
-如果$i$是奇数,
水母可以选择将她的一个苹果与水母的一个苹果交换,或者什么都不做。-如果$i$是偶数,水母可以选择将他的一个苹果与水母的一个苹果交换,或者什么都不做。
两个玩家都想最大化各自苹果的价值总和。
既然你是世界上最聪明的人之一,
$Jellyfish$希望您在所有$k$轮游戏结束后告诉她苹果的最终价值。假设水母和水母都以最优方式发挥作用,以最大化其苹果的价值总和。
我们可以化简一下题意
有两个从小到大排列的数组
为什么可以是从小到大排列是因为我们可以对其进行排序操作
水母$A$ $B$ 分别有一个数组
第奇数轮操作可以让$A$去用$B$的数组中最大的数来替换自己数组中最小的数
第偶数轮操作可以让$B$去用$A$的数组中最大的数来替换自己数组中最小的数
最后输出$A$的数组之和的最优解
那么显然涉及到的操作只有$4$个数
$A_首,A_尾,B_首,B_尾$
刚开始
$A$进行操作
$A$ 肯定用$B_尾$去换$A_首$,因为是从小到大排列的
那么现在变为
$[B_尾,A_尾]$
$[B_首,A_首]$
$B$进行操作
轮到$B$操作的时候就需要多判断一点
我们对现在的两个数组在进行一次排序
那么就变成
$[次MAX,MAX]$
$[MIN,次MIN]$
然后$B$就会用$MIN$去交换$MAX$
变成
$[MIN,次MAX]$
$[次MIN,MAX]$
再轮到A呢
那么就会变为
$[次MAX,MAX]$
$[MIN,次MIN]$
再轮到B呢
变成
$[MIN,次MAX]$
$[次MIN,MAX]$
然后我们可以发现最后只会剩下两种情况,于是我们根据轮数的奇偶性进行判断就行
code
#include <bits/stdc++.h>
#define int long long
int n, m, k;
void solve() {
std::cin >> n >> m >> k;
std::vector<int> a(n);
std::vector<int> b(m);
for (auto &i : a) {
std::cin >> i;
}
sort(begin(a), end(a));
for (auto &i : b) {
std::cin >> i;
}
sort(begin(b), end(b));
if (k & 1) {
if (b[m - 1] > a[0]) {
std::swap(b[m - 1], a[0]);
}
int ans = 0;
for (auto it : a) {
ans += it;
}
std::cout << ans << "\n";
} else {
if (b[m - 1] > a[0]) {
std::swap(b[m - 1], a[0]);
}
sort(begin(a), end(a));
sort(begin(b), end(b));
if (a[n - 1] > b[0]) {
std::swap(a[n - 1], b[0]);
}
int ans = 0;
for (auto it : a) {
ans += it;
}
std::cout << ans << "\n";
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
int __;
std::cin >> __;
while (__--) solve();
return 0;
}
C. Jellyfish and Green Apple[二进制]
水母有$n$个青苹果块。每块青苹果重$1~\text{kg}$。水母想把这些青苹果平均分配给三个人。
水母有一把魔刀。
每次海蜇可以选择一块青苹果,并将其分成两小块。每一块的重量是原来的一半。水母想知道所需的最少操作次数,这样她就可以将青苹果块分成苹果的总重量。
每个人收到的物品都是一样的。
我们可以先将可以被整除的苹果数分好
n %= m
根据题目中的性质我们只能将蛋糕切成2的倍数块
然后先约个公约数看看是不是二的倍数
然后将一个蛋糕切成(n)块需要(n-1)刀
所以n块蛋糕我们可以节省下n刀
然后就是二进制拆分
哪一位上有一就是需要对应大小的蛋糕
就需要切m刀分给m个人
得到结果后把公约数乘回来即可
code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::cin >> n >> m;
n %= m;
if (!n) {
std::cout << "0\n";
} else {
int tt = std::__gcd(n, m);
n /= tt;
m /= tt;
int first_idx = std::__lg(m);
if ((1 << first_idx) == m) {
int ans = 0;
for (int i = 0; i <= 31; i++) {
if (((n >> i) & 1) == 1) {
ans++;
}
}
std::cout << ((ans)*m - n) * tt << "\n";
} else {
std::cout << "-1\n";
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
int __;
std::cin >> __;
while (__--) solve();
return 0;
}
D. Jellyfish and Mex[DP]
您将得到一个由$n$个非负整数$a_1, a_2, \dots, a_n$组成的数组。假设$m$是初始化为$0$的变量,Jellyfish将执行以下操作$n$次:
-选择索引$i$($1 \leq i \leq |a|$)
并从$a$中删除$a_i$。
-将$\operatorname{MEX}(a)^{\dagger}$添加到$m$。现在Jellyfish想要知道如果他最优地执行所有操作,$m$的最小可能最终值。
$\operatorname{MEX}$是不属于数组的最小非负整数。例如:
-$[2,2,1]$的MEX是$0$,因为$0$不属于数组。
-$[3,1,0,1]$的MEX是$2$,因为$0$和$1$属于数组,而$2$不属于数组。
-$[0,3,1,2]$的MEX是$4$,因为$0$、$1$、$2$和$3$属于数组,但$4$不属于数组。
我是谁? ——设计状态,表示局面
我从哪里来?
我要到哪里去? ——设计转移
很显然进行操作时的花费仅与当前状态的$\operatorname{MEX}$相关
那么DP就在于 设计状态 和状态的转移
我们如果设置$\operatorname{MEX}$为状态便可以很方便的进行花费之间的转移
然后就可以转换成选与不选的01背包问题
code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::cin >> n;
std::vector<int> dp(n + 1, INT_MAX);
std::vector<int> a(n);
for (auto &i : a) {
std::cin >> i;
}
sort(begin(a), end(a));
int MEX = -1;
std::set<int> S;
std::map<int, int> mp;
for (auto it : a) {
S.insert(it);
mp[it]++;
}
for (int i = 0; i <= 1e5; i++) {
if (!S.count(i)) {
MEX = i;
break;
}
}
dp[MEX] = 0;
for (int i = MEX; i >= 0; i--) {
for (int j = i + 1; j <= MEX; j++) {
dp[i] = std::min(dp[i], dp[j] + j * mp[i] + i - j);
}
}
std::cout << dp[0] << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
int __;
std::cin >> __;
while (__--) solve();
return 0;
}