2024牛客暑期多校训练营7
比赛链接
英文题面
官方题解
标程/数据
难度梯度 JI KD HC BGA FE
B Lottery
题意
有 \(n\) 张彩票，第 \(i\) 张彩票将等概率的获得 \([0,i]\) 元。
问 \(n\) 张彩票全部刮完之后，你得到的金额总和大于 \(\dfrac{n*m}{k}\) 的概率。
\(1\le n,m,k\le10^5\)。
\(0<\dfrac{m}{k}\le2\)。
解题思路
我们考虑每张彩票的生成函数：
第 \(1\) 张的生成函数是 \(\frac{1}{2}*(1+x)\)，，
第 \(2\) 张的生成函数是 \(\frac{1}{3}*(1+x+x^2)\)，
第 \(i\) 张的生成函数是 \(\frac{1}{i+1}*(1+x+…+x^i)=\frac{1}{i+1}*\frac{1-x^{i+1}}{1-x}\)。
那么我们把 \(n\) 张的生成函数乘起来，得到：
\[ \begin{align} f(x)&=\prod_{i=1}^n\frac{1}{i+1}*\frac{1-x^i}{1-x}\\ &=\frac{1}{(n+1)!}*\frac{\prod_{i=1}^n(1-x^{i+1})}{(1-x)^n}\\ &=\frac{1}{(n+1)!}*\frac{\prod_{i=2}^{n+1}(1-x^i)}{(1-x)^n}\\ &=\frac{1}{(n+1)!}*\frac{\prod_{i=1}^{n+1}(1-x^i)}{(1-x)^{n+1}}\\ \end{align} \]
我们可以知道 \(\dfrac{1}{1-x}=\sum_{i=0}^\infty x^i\)，
所以 \(\dfrac{1}{(1-x)^{n+1}}=(\sum_{i=0}^\infty x^i)^{n+1}\)，
所以 \(f(x)=\frac{1}{(n+1)!}*\prod_{i=1}^{n+1}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}\)，
因为 \(\frac{1}{(n+1)!}\) 是常数项，所以我们可以最后计算。
我们令 \(g(x)=\prod_{i=1}^{n+1}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}\\\)。
可以看到左边与五边形数相似，然后我们需要查询的 \(\frac{nm}{k}\le2n\) 的。
如果要使用五边形数，那么我们必须使得左边的上界至少为 \(2n\)。
则有 \(g(x)=\dfrac{\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}}{\prod_{i=n+2}^{2n}(1-x^i)}\\\)。
我们先看 \(\frac{1}{1-x^i}\)。
使用等比数列求和公式展开，得 \(1-x^i=(1-x)*(1+x+…+x^i)\)，
所以 \(\frac{1}{1-x^i}=\dfrac{1}{(1-x)*(1+x+…+x^i)}\),
因为有 \(\frac{1}{1-x}=\sum_{i=0}^\infty x^i\)，
所以 \(\dfrac{1}{1-x^i}=\dfrac{\sum_{i=0}^\infty x^i}{(1+x+…+x^i)}\),
我们观察可以知道：
\[ \sum_{i=0}^\infty x^i=(1+x+…+x^i)+x^i*(1+x+…+x^i)+x^{2i}*(1+x+…+x^i)+……+x^\infty*(1+x+…+x^i) \]
所以 \(\dfrac{1}{1-x^i}=1+x^i+x^{2i}+…+x^{\infty}\)，
因为我们的 \(i\ge n+2\)，然后我们只需要前 \(2n\) 项，
所以我们可以令 \(\dfrac{1}{1-x^i}=1+x^i\)。
那么 \(\dfrac{1}{\prod_{i=n+2}^{2n}(1-x^i)}=(1+x^{n+2})*(1+x^{n+3})*…*(1+x^{2n})\)。
我们可以看出来 \(x\) 只能与常数项匹配指数才会 \(\le2n\)。
所以 \(\dfrac{1}{\prod_{i=n+2}^{2n}(1-x^i)}=1+x^{n+2}+x^{n+3}+…+x^{2n}=1+\sum_{i=n+2}^{2n}x^i\)
所以：
\[ \begin{align} g(x)&=\dfrac{\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}}{\prod_{i=n+2}^{2n}(1-x^i)}\\ &=\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}*(1+\sum_{i=n+2}^{2n}x^i)\\ &=\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}+\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}*(\sum_{i=n+2}^{2n}x^i)\\ &=\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}+\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}*(x^{n+2}*\sum_{i=0}^{n-2}x^i)\\ &=\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}+\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+2}*(x^{n+2})\\ \end{align} \]
\((\sum_{i=0}^\infty x^i)^n=\dfrac{1}{(1-x)^n}=(1-x)^{-n}\)
我们用广义二项式定理展开，得：\((1-x)^{-n}=\sum_{i=0}^{\infty}C_{-n}^i*(-x)^i=\sum_{i=0}^{\infty}C_{-n}^i*(-1)^i*x^i\)
由于这里组合数出现负数没有实际意义，我们将 \(C_n^m=\dfrac{n^{\underline m}}{m!}\)。
则：\((1-x)^{-n}=\sum_{i=0}^{\infty}\dfrac{(-n)^{\underline i}}{i!}*(-1)^i*x^i\)
我们将 \((-n)^{\underline i}\) 展开，得到 \((-n)*(-n-1)*…*(-n-i+1)\)，
我们提取一个负号出来，得到 \((-1)^{i}*(n*(n+1)*…*(n+i-1))=(-1)^i*(n+i-1)^{\underline i}\)，
所以：
\[ \begin{align} (1-x)^{-n}&=\sum_{i=0}^{\infty}\dfrac{(-1)^i*(n+i-1)^{\underline i}}{i!}*(-1)^i*x^i\\ &=\sum_{i=0}^{\infty}\dfrac{(n+i-1)^{\underline i}}{i!}*(-1)^{2i}*x^i\\ &=\sum_{i=0}^{\infty}C_{n+i-1}^i*x^i\\ \end{align} \]
那么 \(x\) 的指数 \(\le k\) 项的系数和有 \(\sum_{i=0}^kC_{n+i-1}^i=C_{n+k}^k\)。
我们定义函数 \(get(p,q)\) 为求 \(\prod_{i=1}^{2n}(1-x^i)\) 的每一项乘上 \((\sum_{i=0}^\infty x^i)^{p}\) 之后指数 \(\le q\) 的系数和。
因为 \(g(x)=\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+1}+\prod_{i=1}^{2n}(1-x^i)*(\sum_{i=0}^\infty x^i)^{n+2}*(x^{n+2})\\\)
我们 \(ans=\sum_{i=0}^{\frac{n*m}{k}}g(x)[i]=get(n+1,\frac{n*m}{k})+get(n+2,\frac{n*m}{k}-(n+2))\)
最后再乘上一个 \(\frac{1}{(n+1)!}\)，就可以算出 \(\le\dfrac{n*m}{k}\)的概率。
我们取反就可以算出 \(>\dfrac{n*m}{k}\) 的概率。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const i64 P = 1000000007;
i64 qpow(i64 a, i64 b = P - 2, i64 res = 1) {
while (b) {
if (b & 1) {
res = res * a % P;
}
a = a * a % P;
b >>= 1;
}
return res;
}
i64 fact[400005], inv[400005], invfact[400005];
i64 C(int n, int m) {
if (n < m || m < 0) return 0;
return fact[n] * invfact[m] % P * invfact[n - m] % P;
}
vector<array<i64, 2>> f;
void solve() {
i64 n, m, k;
cin >> n >> m >> k;
auto get = [&](i64 x, i64 y) {
i64 res = C(x + y, y);
for (auto &[f, g] :f) {
res = (res + C(x + y - f, y - f) * g) % P;
}
return res;
};
i64 ans = (get(n + 1, n * m / k) + get(n + 2, n * m / k - (n + 2))) % P;
ans = ((1 - ans * invfact[n + 1]) % P + P) % P;
cout << ans << "\n";
}
int main() {
fact[0] = 1;
for (int i = 1 ; i <= 400000 ; i++) {
fact[i] = fact[i - 1] * i % P;
}
invfact[400000] = qpow(fact[400000]);
for (int i = 400000 ; i >= 1 ; i--) {
invfact[i - 1] = invfact[i] * i % P;
inv[i] = fact[i] * invfact[i - 1] % P;
}
for (int i = 1 ; ; i++) {
int k = (3 * i * i - i) / 2;
if (k > 300000) break;
f.push_back({k, (i & 1 ? P - 1 : 1)});
k = (3 * i * i + i) / 2;
if (k > 300000) break;
f.push_back({k, (i & 1 ? P - 1 : 1)});
}
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
C Array Sorting
题意
给你一个长度为 \(n\) 的数组。
数组的每一个元素都是随机的。
你可以操作至多 \(200\) 次。
每次操作你可以选择一个 \(M(M\le\lfloor\frac{n}{2}\rfloor)\)，然后给出 \(M\) 对下标 \((id_1,id_2),(id_3,id_4),…,(id_{2M-1},id_{2M})\)。
\(id\) 之间不可以重复。
请你输出方案。
\(1\le n\le10^4\)
解题思路
使用 3-smooth number shellsort 即可。
需要注意 \(id\) 不能重复，对于每次插入排序，基本都需要两次操作。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
int main() {
int n;
cin >> n;
vector<int> g;
for (int i = 1 ; i < n ; i *= 2) {
for (int j = i ; j < n ; j *= 3) {
g.push_back(j);
}
}
sort(rbegin(g), rend(g));
vector<vector<int>> ans;
for (auto &g : g) {
vector<int> temp[2];
set<int> st;
for (int i = 0 ; i + g < n ; i++) {
int k = 0;
if (st.count(i) || st.count(i + g)) {
k = 1;
} else {
st.insert(i);
st.insert(i + g);
}
temp[k].push_back(i);
temp[k].push_back(i + g);
}
ans.push_back(temp[0]);
if (!temp[1].empty()) {
ans.push_back(temp[1]);
}
}
cout << ans.size() << "\n";
for (auto &ans : ans) {
cout << ans.size() / 2 << " ";
for (auto &ans : ans) {
cout << ans << " ";
}
cout << "\n";
}
return 0;
}
|
D Interval Selection
题意
一个长度为 \(n\) 的数组 \(a\)。
给你一个 \(k\)。
问数组 \(a\) 的所有子数组中，满足每个数恰好出现 \(k\) 次的子数组的数量。
解题思路
我们可以知道，对于 \(x\) 有两种贡献，一种是不存在，一种是恰好出现 \(k\) 次。
我们定义 \(pos\) 数组为 \(x\) 出现的下标。
那么第一种的合法区间是 \(L\in[pos_i+1,pos_{i+1}-1],R\in[pos_i+1,pos_{i+1}-1]\)。
第二种的合法区间是 \(L\in[pos_{i-1}+1,pos_i],R\in[pos_{i+k-1},pos_{i+k}-1]\)。
每种数都产生贡献 \(1\)，假设有 \(m\) 种数，那么所有值为 \(m\) 的个数，就是当前满足要求的数量。
我们对这些区间进行二维数点，使用线段树来维护一个最大值和最大值的数量。
我们枚举从 \(1\) 到 \(n\) 枚举左端点 \(L\)，那么查询区间 \([L,n]\) 中 \(m\) 的个数即可。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const int N = 200005;
struct Node {
int mx, cnt;
} tr[N << 2];
int lazy[N << 2];
Node merge(Node x, Node y) {
Node res{};
res.mx = max(x.mx, y.mx);
res.cnt = 0;
if (res.mx == x.mx) {
res.cnt += x.cnt;
}
if (res.mx == y.mx) {
res.cnt += y.cnt;
}
return res;
}
void pushup(int p) {
tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
}
void build(int p, int L, int R) {
lazy[p] = 0;
if (L == R) {
tr[p] = {0, 1};
return;
}
int mid = L + R >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
pushup(p);
}
void pushtag(int p, int tag) {
tr[p].mx += tag;
lazy[p] += tag;
}
void pushdown(int p) {
if (lazy[p] == 0) return;
pushtag(p << 1, lazy[p]);
pushtag(p << 1 | 1, lazy[p]);
lazy[p] = 0;
}
void modify(int p, int L, int R, int QL, int QR, int k) {
if (QL <= L && R <= QR) {
pushtag(p, k);
return;
}
pushdown(p);
int mid = L + R >> 1;
if (QL <= mid) modify(p << 1, L, mid, QL, QR, k);
if (QR > mid) modify(p << 1 | 1, mid + 1, R, QL, QR, k);
pushup(p);
}
Node query(int p, int L, int R, int QL, int QR) {
if (QL <= L && R <= QR) {
return tr[p];
}
pushdown(p);
int mid = L + R >> 1;
if (QR <= mid) return query(p << 1, L, mid, QL, QR);
if (QL > mid) return query(p << 1 | 1, mid + 1, R, QL, QR);
return merge(query(p << 1, L, mid, QL, QR), query(p << 1 | 1, mid + 1, R, QL, QR));
}
int a[200005];
vector<int> pos[200005];
vector<array<int, 3>> upd[200005];
void add(int L1, int R1, int L2, int R2) {
if (L2 > R2) return;
if (L1 > R1 + 1) return;
upd[L1].push_back({L2, R2, 1});
upd[R1 + 1].push_back({L2, R2, -1});
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> idx(1, -1);
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
idx.push_back(a[i]);
}
sort(begin(idx), end(idx));
idx.resize(unique(begin(idx), end(idx)) - begin(idx));
int m = idx.size() - 1;
for (int i = 1 ; i <= n ; i++) {
pos[i].resize(0);
upd[i].resize(0);
a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
}
for (int i = 1 ; i <= m ; i++) {
pos[i].push_back(0);
}
for (int i = 1 ; i <= n ; i++) {
pos[a[i]].push_back(i);
}
for (int i = 1 ; i <= m ; i++) {
pos[i].push_back(n + 1);
}
for (int i = 1 ; i <= m ; i++) {
for (int j = 0 ; j + 1 < (int) pos[i].size() ; j++) {
int L = pos[i][j] + 1;
int R = pos[i][j + 1] - 1;
add(L, R, L, R);
}
for (int j = 1 ; j + k < (int) pos[i].size() ; j++) {
int L1 = pos[i][j - 1] + 1;
int R1 = pos[i][j];
int L2 = pos[i][j + k - 1];
int R2 = pos[i][j + k] - 1;
add(L1, R1, L2, R2);
}
}
build(1, 1, n);
i64 ans = 0;
for (int i = 1 ; i <= n ; i++) {
for (auto &[L, R, val] : upd[i]) {
modify(1, 1, n, L, R, val);
}
auto [mx, cnt] = query(1, 1, n, i, n);
if (mx == m) {
ans += cnt;
}
}
cout << ans << "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
H Database
题意
实现一个可嵌套的数据库。
语句有 \(insert,select,delete,select_in,delete_in,transaction\)。
解题思路
模拟题
J Ball
题意
在一个二维平面直角坐标系中，有一根长度为 \(L\)，左端点位于 \((0,0)\) 且垂直于 \(y\) 轴的木棍。
有一小球位于点 \(P(x,y)\)，可以在木棍上选取一点 \(Q(x',0)\) 为旋转轴，可以以 \(Q\) 为轴任意旋转。
求符合条件的 \(x'\)，没有则输出 \(NO\)。
解题思路
枚举旋转轴为 \((0,0)\) 和 \((L,0)\) 即可。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
i64 l, x, y;
cin >> l >> x >> y;
i64 d = x * x + y * y;
if (l * l >= d) {
cout << "Yes\n";
cout << 0 << "\n";
} else {
d = (x - l) * (x - l) + y * y;
if (l * l >= d) {
cout << "Yes\n";
cout << l << "\n";
} else {
cout << "No\n";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
K Strings, Subsequences, Reversed Subsequences, Prefixes
题意
给你一个字符串 \(S\) 和 \(T\)。
现在问你 \(S\) 有多少个本质不同的子序列。
满足该子序列的前缀为 \(T\) ，且该子序列翻转后的前缀也为 \(T\)。
解题思路
首先，我们找到满足前缀为 \(T\) 的子序列的最小的右端点 \(L\)，和满足翻转后前缀为 \(T\) 的子序列的最大的左端点 \(R\)。
当 \(L+1\le R-1\) 时，我们可以发现，这两个子序列的中间还有若干个字符，我们任意的选择都能满足条件。
所以这一步就是对区间 \([L+1,R-1]\) 求本质不同的非空子序列的个数。
然后中间可以为空，所以还需要 \(+1\)。
这样我们就找到了所有的前缀和翻转后前缀不交叉的情况。
那么接下来考虑前缀和翻转后前缀交叉的情况，
容易知道符合的子序列一定是一个回文串。
对于每个 \(T\) 的后缀，如果是一个回文串，就判断 \(S\) 中是否存在指定子序列，若出现过，则答案 \(=1\)。
我们可以使用马拉车来快速找到回文串。
我们可以使用子序列自动机来快速查找是否存在子序列。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const i64 P = 1000000007;
array<int, 26> seq[1000005];
int main() {
int n, m;
cin >> n >> m;
string S, T;
cin >> S >> T;
S = " " + S;
T = " " + T;
fill(begin(seq[n + 1]), end(seq[n + 1]), -1);
for (int i = n ; i >= 1 ; i--) {
seq[i] = seq[i + 1];
seq[i][S[i] - 'a'] = i;
}
int L = 1;
{
int r = 1;
while (L <= n) {
if (S[L] == T[r]) {
r++;
}
if (r > m) {
break;
}
L++;
}
}
int R = n;
{
int r = 1;
while (R >= 1) {
if (S[R] == T[r]) {
r++;
}
if (r > m) {
break;
}
R--;
}
}
i64 ans = 0;
if (L <= n) {
string t = T.substr(1);
int len = m * 2 + 1;
vector<char> a(len);
vector<int> b(len);
{
int r = 0, c = 0, idx = 0;
for (int i = 0 ; i < len ; i++) {
a[i] = i & 1 ? t[idx++] : '#';
}
for (int i = 0 ; i < len ; i++) {
b[i] = r > i ? min(r - i, b[c * 2 - i]) : 1;
while (i - b[i] > -1 && i + b[i] < len && a[i - b[i]] == a[i + b[i]]) {
b[i]++;
}
if (i + b[i] > r) {
r = i + b[i];
c = i;
}
}
for (auto &x : b) {
x--;
}
}
auto check = [&](int start, int R) -> bool {
for (int i = R ; i >= 1 ; i--) {
if (a[i] == '#') continue;
start = seq[start + 1][a[i] - 'a'];
if (start == -1) return false;
}
return true;
};
bool flag = false;
for (int i = 2 * m - 1 ; i >= 1 ; i--) {
if (i + b[i] == 2 * m) {
if (!flag) {
if (check(L, i - b[i] - 1)) {
flag = true;
}
}
if (flag) {
ans = (ans + 1) % P;
}
}
}
if (L < R) {
ans = (ans + 1) % P;
}
L++; R--;
if (L <= R) {
vector<i64> dp(n + 1, 0);
array<int, 26> lst{};
for (int i = L ; i <= R ; i++) {
int k = S[i] - 'a';
if (lst[k] > 0) {
dp[i] = ((dp[i - 1] * 2 - dp[lst[k] - 1]) % P + P) % P;
} else {
dp[i] = (dp[i - 1] * 2 + 1) % P;
}
lst[k] = i;
}
ans = (ans + dp[R]) % P;
}
}
cout << ans << "\n";
return 0;
}
|