赛时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 _ ^ _;
}