Codeforces Round 901 (Div. 2)
A - Jellyfish and Undertale
解题思路:
卡在最后秒放。
若\(x_i > (a - 1)\):那么该\(x_i\)的贡献为\(a - 1\)。
否则，该\(x_i\)的贡献为\(x_i\)。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
void solve()
{
int a,b,n;
scanf("%d %d %d",&a,&b,&n);
vector<int> x(n + 1);
ll ans = b;
for(int i = 1;i<=n;i++)
{
scanf("%d",&x[i]);
if(x[i] < a - 1)
{
ans += (ll)x[i];
}
else
{
ans += (ll)a - 1;
}
}
printf("%lld\n",ans);
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
B - Jellyfish and Game
解题思路：
如果\(k\)为奇数，那么\(Jellyfish\)具有绝对选择权。此时，选取最大正收益交换方案加上即可。若无正收益方案，不变即可。
如果\(k\)为偶数，那么\(Jellyfish\)没有主动权，但同样选取最大正收益交换方案加上，无正收益就不动。交换后，更新二者最大数和最小数，此时找到\(Gellyfish\)的最大正收益方案，这个也就是\(Jellyfish\)亏损最大的方案，答案减去亏损即可。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
void solve()
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
vector<int> a(n + 1),b(m + 1);
int mina = 1e9 + 10;
int maxa = 0;
int minb = 1e9 + 19;
int maxb = 0;
ll sa = 0;
ll sb = 0;
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
mina = min(mina,a[i]);
maxa = max(maxa,a[i]);
sa += (ll)a[i];
}
for(int i = 1;i<=m;i++)
{
scanf("%d",&b[i]);
minb = min(minb,b[i]);
maxb = max(maxb,b[i]);
sb += (ll)b[i];
}
ll l = maxb - mina;
ll r = maxa - minb;
if(k & 1)
{
if(l >= 0)
{
sa += l;
}
}
else
{
if(r <= 0)
{
}
else
{
if(l >= 0)
{
sa += l;
sb -= l;
int t = (max(maxb,maxa) - min(mina,minb));
sa -= t;
}
else
{
sa -= r;
}
}
}
printf("%lld\n",sa);
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
C - Jellyfish and Green Apple
解题思路:
首先，如果\(n \% m==0\),那么苹果一定能直接均分，不需要切。
对半分，得到的苹果重量只有\(1,\frac {1}{2},\frac{1}{4},...,\frac{1}{2^{29}}\)这类\(2\)的负整数次幂。
也就是说，我们将\(n\)个苹果均分为\(m\)份，$ \frac{n}{m}\(,去除整数部分，\)res = \frac{n % m}{m}\(。只有当对\)res\(进行约分后，即\)d = gcd(n%m,m),a = \frac{(n% m)}{d},b = \frac{m}{d}$。
其中，\(b\)应当为\(2^x\),即\(2\)的整数次幂。
现在我们要将\(a\)个苹果均分给\(b\)个人。计算要切几刀。注意我们之前进行了约分，答案最后要乘回\(d\)。
得到两个\(0.5\)要一刀，得到四个\(0.25\)要三刀，得到八个\(0.125\)要七刀。。。以此类推。
然后对于\(\frac{a}{b}\)的组成，我们可以用乘基取整法来得出。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
vector<ll> cnt(100);
ll lowbit(ll x)
{
return x & -x;
}
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = (res * a);
}
a *= a;
b >>= 1;
}
return res;
}
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
ll n, m;
scanf("%lld %lld", &n, &m);
ll d = gcd(n, m);
n /= d;
m /= d;
if (n % m == 0)
{
puts("0");
return;
}
if (lowbit(m) != m)
{
puts("-1");
return;
}
ll u = n % m;
ll ans = 0;
for (int i = 1; i < 40; i++)
{
u *= 2;
if (u >= m)
{
ans += cnt[i] * (m / (cnt[i] + 1));
u -= m;
}
}
printf("%lld\n", ans * d);
}
int main()
{
int t = 1;
scanf("%d", &t);
for (int i = 1; i <= 40; i++)
{
cnt[i] = cnt[i - 1] + qmi(2, i - 1);
}
while (t--)
{
solve();
}
return 0;
}
D - Jellyfish and Mex
解题思路:
设开始\(MEX(a) = u\),那么我们只会从小于\(u\)的数开始删。
如果我们删除了\(a_i 此时 u > a_i\),那么接下来\(u = a_i\)。
所以，我们删除的顺序一定是一个非单调递增序列。
\(dp[i]:使得MES(a) = a[i]的最小花费\)。答案就是排完序后的\(dp[i]\)。
状态转移方程:
\[dp[i] = min(u * (cnt[a[i]] - 1)+a[i],dp[j] + a[j] * (cnt[a[i]]- 1)+a[i]) \]由于本题数据范围较小，对于\(j\)直接枚举转移即可。
其中\(u * (cnt[a[i]] - 1)+a[i]\)表示第一个删除的数就是\(a[i]\)的花费。
其中\(dp[j] + a[j] * (cnt[a[i]]- 1)+a[i]\)表示从\(MEX(a) = a[j]\)转移到\(MEX(a) = a[i]\)的花费。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
int n;
scanf("%d", &n);
vector<int> a(n + 1);
map<int, int> cnt;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
cnt[a[i]]++;
}
sort(a.begin() + 1, a.end());
a.erase(unique(a.begin() + 1, a.end()), a.end());
n = a.size() - 1;
ll u = 0;
for (int i = 1; i <= n; i++, u++)
{
if (u != a[i])
{
break;
}
}
// dp[i]：使得MEX(a) = a[i]的最小花费
vector<ll> dp(n + 1, 0);
for (int i = n; i; i--)
{
if (a[i] > u)
{
continue;
}
dp[i] = (cnt[a[i]] - 1) * u + a[i];
for (int j = i + 1; j <= n && a[j] <= u; j++)
{
dp[i] = min(dp[i], dp[j] + a[j] * (cnt[a[i]] - 1) + a[i]);
}
}
printf("%lld\n", dp[1]);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}