赛时A题意理解错误，导致A调试半小时没出样例，直接提前下班-->https://codeforces.com/contest/1848
A. Jellyfish and Undertale
题意：初始时长为b的定时炸弹，没秒从n个工具中选一个加时长\(x_i\)，每次加时不能超过a，并流失一秒。问：炸弹爆炸前的最长时间是多长？
思路：贪心枚举每个工具，每次加时min(a - 1, \(x_i\)),答案即为最后的b。
代码：
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 2e5 + 10;
void solve()
{
int a, b, c, x, mx = 0;
cin >> a >> b >> c;
for(int i = 0; i < c; i ++)
{
cin >> x;
b += min(x, a - 1);
}
cout << b << '\n';
}
signed main()
{
IOS; int _ = 1;
cin >> _;
while(_ --)
solve();
return _ ^ _;
}
B. Jellyfish and Game
题意：A和B两人博弈K次，每次以最优方案交换两者中的任意苹果的值。问：最终A的苹果最大化总价值是多少？
思路：由于两者是最优的交换，奇偶性相同的交换，答案相等，故可模拟实现前两次交换；第一次若mina < maxb，交换；第二次maxa > minb，交换。
代码：
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define i128 __int128
using namespace std;
const int N = 2e5 + 10;
void solve()
{
int n, m, k;
cin >> n >> m >> k, k --;
vector<int> a(n), b(m);
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0; i < m; i ++) cin >> b[i];
int x = 0, y = 0, ans = 0;
for(int i = 1; i < n; i ++) if(a[i] < a[x]) x = i;
for(int i = 1; i < m; i ++) if(b[i] > b[y]) y = i;
if(a[x] < b[y]) swap(a[x], b[y]);
if(k & 1)
{
x = y = 0;
for(int i = 1; i < n; i ++) if(a[i] > a[x]) x = i;
for(int i = 1; i < m; i ++) if(b[i] < b[y]) y = i;
swap(a[x], b[y]);
}
for(int i = 0; i < n; i ++)
ans += a[i];
cout << ans << '\n';
}
signed main()
{
IOS; int _ = 1;
cin >> _;
while(_ --)
solve();
return _ ^ _;
}
C. Jellyfish and Green Apple
题意：有n个重量为1kg的苹果，将其均分给m个人，每次操作可以将某个苹果均分成两份。问：最少需要次操作才能使m个人分得的苹果重量相等？不能均分，输出-1。
思路1：先均分整1kg质量的苹果，\(n/m\)后由于均分，\(m/gcd(n,m)\)应为2的整数次幂，否则无解。
代码1：
点击查看代码1
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 2e5 + 10;
void solve()
{
int n, m;
cin >> n >> m;
n %= m;
int a = n / __gcd(n, m);
int b = m / __gcd(n, m);
// cout << __builtin_popcount(b) << ' ';
if(__builtin_popcount(b) > 1) cout << "-1\n";
else cout << __builtin_popcount(a) * m - n << '\n';
}
signed main()
{
IOS; int _ = 1;
cin >> _;
while(_ --)
solve();
return _ ^ _;
}
思路2：由于均分，可以枚举\(n*2^i\)，累加n%m，当该值是m的整数倍时，和即为答案；当这个数非常大时，无解。
代码2：
点击查看代码2
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 2e5 + 10;
void solve()//模拟
{
int n, m;
cin >> n >> m;
n %= m;
int a = 1, ans = 0;
while(a < 1e18)
{
if(n % m == 0)
{
cout << ans << '\n';
return ;
}
n %= m;
ans += n;
n *= 2;
a *= 2;
}
cout << "-1\n";
}
signed main()
{
IOS; int _ = 1;
cin >> _;
while(_ --)
solve();
return _ ^ _;
}
D. Jellyfish and Mex
题意：有n个自然数，最初的总价值为0，每次操作会删除任一个\(x_i\)，后总价值加上MEX(x)。问：操作n次后的总价值最小是多少？
思路：由于有MEX的存在，该次操作依赖于上一次操作的结果，考虑线性dp，操作次数为n，可以记录下\(x_i\)<n出现的次数，然后找到没有出现过的最小的自然数mn，再求前i项的每项的最小总价值，转移方程：f[i]=min(f[i]，f[j]+x[i]*j)，答案为:f[0]-mn。
代码：
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
void solve()
{
int n, x, ma = 0, ans = 0;
cin >> n;
vector<int> a(n + 1, 0), res(n + 1, inf);
for(int i = 1; i <= n; i ++)
{
cin >> x;
a[min(x, n)] ++;
}
while(a[ma]) ma ++; res[ma] = 0;
for(int i = ma - 1; i >= 0; i --)
for(int j = i + 1; j <= ma; j ++)
res[i] = min(res[i], res[j] + a[i] * j);
cout << res[0] - ma << '\n';
}
signed main()
{
IOS; int _ = 1;
cin >> _;
while(_ --)
solve();
return _ ^ _;
}