牛客周赛 Round 29
小红大战小紫
代码:
#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 a, b;
cin >> a >> b;
if (a > b)
{
puts("kou");
}
else if (a < b)
{
puts("yukari");
}
else
{
puts("draw");
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的白日梦
代码:
#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 a, b;
cin >> a >> b;
ll ans = 0;
for (int i = 0; i < n; i++)
{
if (a[i] == 'Y')
{
ans += 2;
}
if (b[i] == 'Y')
{
if (a[i] == 'N')
{
ans += 2;
}
else
{
ans += 1;
}
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的小小红
代码:
#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()
{
string s;
cin >> s;
int n = s.size();
string a = "xiao";
string b = "hong";
int idx = s.find(a);
s.erase(idx, a.size());
idx = s.find(b);
s.insert(idx, a);
cout << s << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的中位数
解题思路:
排个序 + 分类讨论。
代码:
#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;
vector<double> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
vector<double> b = a;
sort(b.begin() + 1, b.end());
for (int i = 1; i <= n; i++)
{
auto idx = lower_bound(b.begin() + 1, b.end(), a[i]) - b.begin();
if (n & 1)
{
if (idx == (n + 1) / 2)
{
int l = (n + 1) / 2 - 1;
int r = (n + 1) / 2 + 1;
double ans = ((double)b[l] + b[r]) / 2;
printf("%.1lf\n", ans);
}
else if (idx < (n + 1) / 2)
{
int l = (n + 1) / 2;
int r = (n + 1) / 2 + 1;
double ans = ((double)b[l] + b[r]) / 2;
printf("%.1lf\n", ans);
}
else if (idx > (n + 1) / 2)
{
int l = (n + 1) / 2 - 1;
int r = (n + 1) / 2;
double ans = ((double)b[l] + b[r]) / 2;
printf("%.1lf\n", ans);
}
}
else
{
if (idx <= n / 2)
{
printf("%.1lf\n", b[n / 2 + 1]);
}
else
{
printf("%.1lf\n", b[n / 2]);
}
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红构造数组
解题思路:
首先，\(1\)无法构造。
我们对每个数进行质因子分解。记录所有质因子之和为\(sum\)，最大的质因子次数为\(mx\)。
对于\(sum\)为奇数的情况，若\(mx \geq \frac{sum}{2} + 1\)，则无解，反之则有解。
对于\(sum\)为偶数的情况，若\(mx \geq \frac{sum}{2}\)，则无解，反之则有解。
关于数组的构造:
创建一个空数组。
每次取当前次数最大的质因子加入队尾，然后取一个次数第二大的放到队尾。记得每加入一次，次数减一。
指导所有次数为0.
代码:
#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 = 5e6 + 10;
void solve()
{
ll n;
cin >> n;
if (n == 1)
{
puts("-1");
return;
}
vector<int> mp(N);
vector<int> primes;
auto sieve = [&](int n)
{
for (int i = 2; i <= n; i++)
{
if (!mp[i])
{
primes.push_back(i);
mp[i] = i;
}
for (auto p : primes)
{
if (i * p > n)
{
break;
}
mp[i * p] = i;
if (i % p == 0)
{
break;
}
}
}
};
sieve(N - 5);
ll x = n;
ll mx = 0;
ll s = 0;
priority_queue<pii> q;
for (auto i : primes)
{
if (x % i == 0)
{
ll cnt = 0;
while (x % i == 0)
{
cnt++;
x /= i;
s++;
}
mx = max(mx, cnt);
q.push({cnt, i});
}
}
bool isp = true;
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
isp = false;
break;
}
}
if (x > 1 && isp)
{
s++;
q.push({1, x});
}
if (s & 1)
{
if (mx <= s / 2 + 1)
{
cout << s << endl;
while (q.size())
{
auto a = q.top();
q.pop();
a.fi--;
cout << a.se << ' ';
if (q.size())
{
auto b = q.top();
q.pop();
b.fi--;
cout << b.se << ' ';
if (b.fi > 0)
{
q.push(b);
}
}
if (a.fi > 0)
{
q.push(a);
}
}
}
else
{
puts("-1");
return;
}
}
else
{
if (mx <= s / 2)
{
cout << s << endl;
while (q.size())
{
auto a = q.top();
q.pop();
a.fi--;
cout << a.se << ' ';
if (q.size())
{
auto b = q.top();
q.pop();
b.fi--;
cout << b.se << ' ';
if (b.fi > 0)
{
q.push(b);
}
}
if (a.fi > 0)
{
q.push(a);
}
}
}
else
{
puts("-1");
return;
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红又战小紫
解题思路:
首先，如果此时没有包含两个石子的石子堆，那么当前为必胜状态。
\(g[i][j]:此时含有1个石子的石子堆有i个，含有2个石子的石子堆有j个\).
随机选择胜率转移：
\(g[i][j] = \frac{i}{i + j} \times (1 - g[i-1][j]) + \frac{j}{i + j} \times (1 - g[i + 1][j - 1])\)。
其中，\(\frac{i}{i + j}\)是选中含有\(1\)个石子的石子堆的概率，\(\frac{j}{i + j}\)是选中含有\(2\)个石子的石子堆的概率。
\(1 - g\)，是因为如果我们走完当前这一步，那么下一步就是对手走，所以\(g\)在这里是对手的胜率。
与之对应，我们的胜率就是\(1 - g\)。
不难发现，上述转移方程对于维度\(i\)有加有减，不容易写递推式。\(ps:这里可以写记忆化搜索递归。\)
所以，我们修改状态定义:
\(f[i][j]:当前有i堆石子不为空，其中，含有2个石子的堆数为j。\)
由此可得状态转移方程为:
\(f[i][j] = \frac{i - j}{i} \times f[i-1][j] + \frac{j}{i} \times f[i][j - 1]\)。
代码:
#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 mod = 1e9 + 7;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return res;
}
ll inv(ll x)
{
return qmi(x, mod - 2);
}
void solve()
{
int n;
cin >> n;
vector<int> cnt(4);
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
cnt[x]++;
}
vector<vector<ll>> f(n + 1, vector<ll>(n + 1));
double ans = 1;
// 对于状态转移方程，最好定义到方便递推的顺序
// 当然，又要减又要加的那种形式也可以写成记忆化搜索
// 不为0的石子堆有i个
for (int i = 1; i <= n; i++)
{
f[i][0] = 1;
// 为2的石子堆有j个
for (int j = 1; j <= i; j++)
{
f[i][j] = ((((((i - j) * inv(i) % mod) * (1 - f[i - 1][j]) % mod) + mod)) % mod + ((((j * inv(i) % mod) * (1 - f[i][j - 1]) % mod) + mod)) % mod) % mod;
f[i][j] %= mod;
}
}
cout << f[cnt[1] + cnt[2]][cnt[2]] << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}