Codeforces Round 921 (Div. 2)
A - We Got Everything Covered!
解题思路:
以前\(k\)个字符都出现过至少一次为一轮，构造\(n\)轮即可。
代码:
#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, k;
cin >> n >> k;
string s;
for (int i = 0; i < k; i++)
{
char c = 'a' + i;
s += c;
}
string t = s;
for (int i = 2; i <= n; i++)
{
s += t;
}
cout << s << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - A Balanced Problemset?
解题思路:
假设我们结果的最大公因数为\(g\)，那么分出的\(n\)个数字分别为\((k_1g,k_2g,...,k_ng)\)。所以\(x = \sum\limits_{i = 1}^nk_ig\)。
所以\(g\)一定是\(x\)的因子。
筛出所有因子，遍历，能分出\(n\)份即可，取最大。
代码:
#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()
{
ll x, n;
cin >> x >> n;
vector<ll> v;
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
v.push_back(i);
if (x / i != i)
{
v.push_back(x / i);
}
}
}
v.push_back(1);
v.push_back(x);
ll ans = 0;
for (auto a : v)
{
ll k = x / a;
// cout << a << ' ' << k << endl;
if (k >= n)
{
ans = max(ans, a);
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Did We Get Everything Covered?
解题思路:
合法要求同第一题：以前\(k\)个字符都出现过至少一次为一轮，构造\(n\)轮即可.
判断是否有\(n\)轮，如果不满足，即只有\(s\)轮，\(s < n\)。
我们先取前\(k\)轮中每轮的最后一个字符。
然后选取一个第\(k + 1\)轮缺少的字符，一直加到字符长度为\(n\)，该字符一定不是给定字符的子串。
代码:
#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, k, m;
cin >> n >> k >> m;
string s;
cin >> s;
int cur = 0;
int cnt = 0;
vector<bool> vis(26);
string ans;
for (auto c : s)
{
int x = c - 'a';
if (x < k && !vis[x])
{
vis[x] = true;
cnt++;
if (cnt == k)
{
ans += c;
for (int i = 0; i < 26; i++)
{
vis[i] = false;
}
cnt = 0;
cur++;
}
}
}
if (cur < n)
{
puts("NO");
char c;
for (int i = 0; i < k; i++)
{
if (!vis[i])
{
c = i + 'a';
}
}
while (ans.size() < n)
{
ans += c;
}
cout << ans << endl;
}
else
{
puts("YES");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Good Trip
解题思路:
首先，我们每次出行要从\(n\)个人中选取两个人，即\(C(n,2) = \binom{n}{2} = \frac{n *(n -1)}{2}\)。
那么，每次选择到我们固定要的一对二人组的概率就是\(p = \frac{1}{\binom{n}{2}}\)，选不到我们要的二人组的概率为\(q = 1 - p\)。
我们有\(k\)次出行，那么\(k\)个二人组中共选到某一个特定二人组\(i\)次的概率为\(\binom{k}{i} \times p^{i}\times q^{k -i}\)。
如果这个特定二人组不是朋友，那么他们的期望为\(0 \times \binom{k}{i} \times p^{i}\times q^{k -i} = 0\)
如果这个特定二人组不是朋友，且初始友谊值为\(f_a\)， 那么他们的期望为\(\sum\limits_{j = 0}^{i - 1}(f_a+j) \times \binom{k}{i} \times p^{i}\times q^{k -i}\)。即每选到一次后，友谊值都会加\(1\).
我们要求的是所有情况的期望，也就是每个情况的期望的和。
由上可知，不是朋友的二人组期望贡献为\(0\)，所以我们只需要将朋友二人组的期望加起来即可。
有\(m\)组朋友二人组，将他们累加:
\[\binom{k}{i}\times p^i \times q^{k - i} \times \sum\limits_{a = 1}^m\sum\limits_{j = 0}^{i - 1}(f_a+j) \]设\(s = \sum\limits_{a =1}^m f_a\)化简：
\[\binom{k}{i}\times p^i \times q^{k - i} \times \sum\limits_{j = 0}^{i-1}(s +j\times m) \]明显，等差数列高斯求和。
遍历\(0 \sim k\)，对上式求各种情况和即为答案。
代码:
#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;
const int N = 2e5 + 10;
int n, m, k;
ll f[N];
ll inv[N];
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 C(ll a, ll b)
{
if (a == b || b == 0)
{
return 1;
}
return (f[a] * inv[a - b] % mod) * inv[b] % mod;
}
ll S(ll l, ll cnt)
{
return ((l + (l + (cnt - 1) * m)) * cnt % mod) * inv[2] % mod;
}
void init(int n)
{
f[0] = 1;
for (int i = 1; i <= n; i++)
{
f[i] = f[i - 1] * i % mod;
}
inv[n] = qmi(f[n], mod - 2);
for (int i = n - 1; i; i--)
{
inv[i] = (i + 1) * inv[i + 1] % mod;
}
}
void solve()
{
cin >> n >> m >> k;
ll sum = 0;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
sum = (sum + c) % mod;
}
ll ans = 0;
ll p = qmi(C(n, 2), mod - 2) % mod;
ll q = (((1 - p) % mod) + mod) % mod;
// cout << C(n, 0) << endl;
for (int i = 0; i <= k; i++)
{
// cout << i << ' ' << S(sum, i) << ' ' << C(k, i) * qmi(p, i) << ' ' << ' ' << endl;
ans = (ans + ((S(sum, i) * (C(k, i) * qmi(p, i) % mod) % mod) * qmi(q, k - i) % mod)) % mod;
}
cout << ans << endl;
}
int main()
{
int t = 1;
init(2e5 + 5);
cin >> t;
while (t--)
{
solve();
}
return 0;
}