牛客练习赛121
出题人题解 | 牛客练习赛 121 题解
小念吹气球
解题思路:
字符长度加字符种类数。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
map<char, bool> q;
for (auto c : s)
{
q[c] = true;
}
cout << n + q.size() << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
You Brought Me A Gentle Breeze on the Field
解题思路:
如果只有一个糖果，必败状态，则小念输。
如果糖果在\(2 \sim m + 1\)，那么小念赢，因为一定能一步到必败状态。
否则，能连取的赢。因为不能连取的人，一定无法先进入必败状态。只要能连取的人将连取机会留到\(m + 2 \sim 1 + 2m\)，此时，自己一定能转入必败状态，而对面不行。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int n, m, p;
cin >> n >> m >> p;
if (n == 1)
{
puts("YangQiShaoNian");
return;
}
if (n > 1 + m)
{
if (p == 1)
{
puts("YangQiShaoNian");
}
else
{
puts("XiaoNian");
}
}
else
{
puts("XiaoNian");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
氧气少年的水滴 2
解题思路:
模拟。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int n, p;
cin >> n >> p;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int i = p - 1;
int j = p + 1;
a[p]++;
int l = 0;
int r = 0;
if (a[p] == 10)
{
l++;
r++;
}
int cnt = 0;
while (i > 0 && j <= n)
{
cnt++;
if (cnt > n + 1)
{
break;
}
if (a[i] + l >= 10)
{
l -= 10 - a[i];
i--;
l++;
r++;
}
else
{
a[i] += l;
l = 0;
}
if (a[j] + r >= 10)
{
r -= 10 - a[j];
j++;
r++;
l++;
}
else
{
a[j] += r;
r = 0;
}
}
cnt = 0;
while (i > 0)
{
if (a[i] + l >= 10)
{
l -= 10 - a[i];
i--;
l++;
r++;
}
else
{
l = 0;
break;
}
}
cnt = 0;
while (j <= n)
{
if (a[j] + r >= 10)
{
r -= 10 - a[j];
j++;
r++;
l++;
}
else
{
r = 0;
break;
}
}
cout << l << ' ' << r << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
氧气少年的 LCM
解题思路:
\(g = gcd(x,y)\\x = k_1*g\\y = k_2*g \\lcm(x,y) = \frac{x * y}{g} = k_1*k_2*g = k_2*x\).
如上，我们只要构建出\(k_2*x\)即可。
通过加法构造出\(2^1*x,2^2 *x,...2^{32}*x\).
我们将\(k_2\)进行二进制拆分,然后按位将需要的\(2^k*x\)累加起来即可。
注意点:
- 由于我们需要数字两两相加，记得每个数字构造两个。
- 题目明确说了，集合内每个元素不超过\(10^{18}\)。（本人这点没注意，卡了近一个小时).
代码;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b)
{
return a * b / gcd(a, b);
}
struct option
{
ll t, a, b;
};
void solve()
{
ll x, y;
cin >> x >> y;
ll tar = lcm(x, y);
if (tar == x || tar == y)
{
puts("0");
}
else
{
ll g = gcd(x, y);
vector<option> v;
v.push_back({1, x, y});
v.push_back({1, x, y});
ll k1 = x / g;
ll k2 = y / g;
ll cur = g;
vector<ll> p(40), b(40);
p[0] = x;
b[0] = g;
for (int i = 1; i <= 32; i++)
{
if (cur + cur > 1e18)
{
break;
}
v.push_back({2, cur, cur});
v.push_back({2, cur, cur});
cur += cur;
b[i] = cur;
}
bool vis = false;
for (int i = 32; i >= 0; i--)
{
if (k1 >> i & 1)
{
if (vis == false)
{
vis = true;
cur = b[i];
}
else
{
v.push_back({2, b[i], cur});
cur += b[i];
}
}
}
cur = x;
for (int i = 1; i <= 32; i++)
{
if (cur + cur > 1e18)
{
break;
}
v.push_back({2, cur, cur});
v.push_back({2, cur, cur});
cur += cur;
p[i] = cur;
}
cur = 0;
vis = false;
for (int i = 32; i >= 0; i--)
{
if (k2 >> i & 1)
{
if (vis == false)
{
vis = true;
cur = p[i];
}
else
{
v.push_back({2, p[i], cur});
cur += p[i];
}
}
}
cout << v.size() << endl;
for (auto t : v)
{
cout << t.t << ' ' << t.a << ' ' << t.b << endl;
}
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
氧气少年逛超市 3
解题思路:
观察范围，时间复杂度\(O(n^2)\)可过。
对于前\(min(a + b,n)\)个物品，我们一定使用券。
并且一定是价格贵的物品先用，减额力度大的券。
\(f[i][j]:考虑前i个物品，我们用了j个折扣卷。\)
\[f[i][j] = \begin{cases} f[i-1][j-1] + a[i]\times \frac{x[j]}{100.0}\\ f[i-1][j] + a[i] - y[i - j] \end{cases} \]注意转移限制区间条件。
\[ans = min(f[min(a+b,n)][0,1,2,...,a]) + \sum\limits_{i = a + b + 1}^np_i \]解释，为什么答案统计前面是\(f[min(a + b,n)][0,1,2,...,a]\)而不是\(f[min(a + b,n)][a]\)。
因为\(0 \leq a + b \leq 2n\),不一定所有的券都会用上。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
const int N = 5010;
double f[N][N];
void solve()
{
int n;
cin >> n;
vector<double> a(n + 1), x(1), y(1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= 2; i++)
{
int m;
cin >> m;
for (int j = 1; j <= m; j++)
{
double t;
cin >> t;
if (i == 1)
{
x.push_back(t);
}
else
{
y.push_back(t);
}
}
}
sort(a.begin() + 1, a.end());
reverse(a.begin() + 1, a.end());
sort(x.begin() + 1, x.end());
sort(y.begin() + 1, y.end());
reverse(y.begin() + 1, y.end());
double ans = 1e18;
double cur = 0;
for (int i = 1; i <= n; i++)
{
cur += a[i];
for (int j = 0; j <= n; j++)
{
f[i][j] = cur;
}
}
for (int i = 0; i <= n; i++)
{
f[0][i] = 0;
}
int m = min(n, (int)x.size() + (int)y.size() - 2);
for (int i = 1; i <= m; i++)
{
for (int j = 0; j <= x.size() - 1; j++)
{
if (j > 0)
{
f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] * x[j] / 100.0));
}
if (i - j > 0 && i - j < y.size())
{
f[i][j] = min(f[i][j], f[i - 1][j] + max(0.0, a[i] - y[i - j]));
}
}
}
// cout << f[1][0] << endl;
for (int i = 0; i <= x.size() - 1; i++)
{
ans = min(ans, f[m][i]);
}
for (int i = m + 1; i <= n; i++)
{
ans += a[i];
}
printf("%.14lf\n", ans);
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}