多校 Day 1

发表于 2026-07-22 更新于 2026-08-05 本文字数： 1.8k 阅读时长 ≈ 7 分钟

A

选择 $u \in A, v\in B$ ，使得 $(x + u)\times(y + v)$ 最大。

由于可以不选，可以把 $0$ 加入到 $A$ 和 $B$ 中。

若固定 $v$ ，则 $f(u) = (x + u)(y + v) = (y + v)u + x(y + u)$ ，是关于 $u$ 的一次函数，因此要取到极值， $u$ 一定在两个端点上。固定 $u$ 的情况同理。

因此全局最优解一定在这之中：

\begin{aligned} &(x+\min A)(y+\min B),\\ &(x+\min A)(y+\max B),\\ &(x+\max A)(y+\min B),\\ &(x+\max A)(y+\max B). \end{aligned}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define int long long
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int maxn = 2e5 + 5;
int x, y, n, m;
void Solve() {
    cin >> x >> y >> n >> m;
    int maxx = 0, minx = 0;
    int maxy = 0, miny = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        maxx = max(maxx, a);
        minx = min(minx, a);
    }
    for (int i = 1; i <= m; i++) {
        int b;
        cin >> b;
        maxy = max(maxy, b);
        miny = min(miny, b);
    }
    maxx += x, minx += x, maxy += y, miny += y;
    cout << max(max(maxx * maxy, minx * miny), max(maxx * miny, minx * maxy)) << endl;

}
signed main() {
    // freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
    return  0;
}

F

把总期望拆成每盏灯打开时的连续段的期望个数之和。

给每盏灯独立分配一个 $[0,1]$ 上的均匀随机数 $U_i$ ，按 $U_i$ 从小到大的顺序开灯。由于这些随机数几乎一定两两不同，它们的相对大小构成一个均匀随机排列，与原问题完全等价。

亮灯连续段的数量等于「既是亮着的，又是所在段的起点」的位置数。位置 $j$ 是起点，需要满足：

第 $j$ 盏灯亮着。
$j=1$ ，或第 $j-1$ 盏灯不亮。

设灯 $i$ 正在打开， $U_i=x$ 。

1. 端点 $i=1$

第 $1$ 盏灯一定是起点。位置 $2$ 因为左边有灯 $1$ 亮着，不可能是起点。

其余 $n-2$ 个位置 $j\ge3$ 成为起点的概率均为 $x(1-x)$ （自身亮且左边不亮）。

\mathbb E[C_1\mid U_1=x]=1+(n-2)x(1-x).

积分得

\mathbb E[C_1]=1+\frac{n-2}{6}=\frac{n+4}{6}.

2. 端点 $i=n$

位置 $1$ 成为起点的概率为 $x$ 。位置 $n$ 成为起点的概率为 $1-x$ （左边不亮）。

其余 $n-2$ 个位置成为起点的概率为 $x(1-x)$ 。

\mathbb E[C_n\mid U_n=x]=x+(1-x)+(n-2)x(1-x)=1+(n-2)x(1-x),

同样得到

\mathbb E[C_n]=\frac{n+4}{6}.

3. 内部点 $2\le i\le n-1$

位置 $1$ ：概率 $x$ 。
位置 $i$ ：正在打开，它成为起点要求左边不亮，概率 $1-x$ 。
位置 $i+1$ ：左边是 $i$ 已亮，不可能成为起点，概率 $0$ 。
其余 $n-3$ 个位置：概率 $x(1-x)$ 。

\mathbb E[C_i\mid U_i=x]=x+(1-x)+(n-3)x(1-x)=1+(n-3)x(1-x).

积分得

\mathbb E[C_i]=1+\frac{n-3}{6}=\frac{n+3}{6}.

汇总

记 $S=\sum a_i$ 。

\begin{aligned} \mathbb E[\text{总分}] &= \frac{n+3}{6}\sum_{i=1}^n a_i+\frac{a_1}{6}+\frac{a_n}{6}\\[4pt] &= \boxed{\frac{(n+3)S+a_1+a_n}{6}}. \end{aligned}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
// #define int long long
const int mod = 998244353;
const int maxn = 2e5 + 5;
int qpow(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        n /= 2;
    }
    return res;
}
int n;
int a[maxn];
void Solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    if (n == 1) {
        cout << a[1] << endl;
        return;
    }
    ans = 1ll * (n + 4) * (a[1] + a[n]) % mod;
    for (int i = 2; i < n; i++) {
        ans = (ans + 1ll * (n + 3) * (a[i]) % mod) % mod;
    }
    cout << 1ll * ans * qpow(6, mod - 2) % mod << endl;
}
signed main() {
    // freopen("1006.in", "r", stdin);
    // freopen("1006.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
    return  0;
}

E

构造 $S = a...ab...b$ ，字符集设为 $2$ 。

令 $a$ 的数量为 $k_1$ ， $b$ 的数量为 $k_2$ 。

全 $a$ 串对答案的贡献为 $\sum^{k_1 - 1}_{i = 0}i = \frac{k_1(k_1 - 1)}{2}$ ，全 $b$ 串对答案的贡献为 $k_2$ 。

所以只需要找到最大的 $k_1$ ，使得 $\frac{k_1(k_1 - 1)}{2} \leq k$ ，然后再填 $k - \frac{k_1(k_1 - 1)}{2}$ 个 $b$ 就行了。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long; 
#define int long long
#define endl "\n"

const int inf = 2e9;
const int maxn = 1e6 + 5;
int k;
void solve() {
    cin >> k;
    int n = 1;
    while (n * (n + 1) / 2 <= k) ++n;
    --n;
    vector<char> ans;
    for (int i = 1; i <= n + 1; i++) ans.push_back('a');
    for (int i = 1; i <= k - n * (n + 1) / 2; i++) ans.push_back('b');
    cout << ans.size() << " " << 2 << endl;
    for (char x : ans) cout << x;
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) { 
        solve();
    }
    return 0;
}

J

比较字典序

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define int long long
const int mod = 998244353;
const int maxn = 1e6 + 5;
int n;
int x[maxn], pre[maxn];
void Solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + x[i];
    if (n & 1) {
        for (int i = n / 2; i >= 1; i--) {
            if (pre[i] > pre[n] - pre[n - i]) {
                cout << "YES" << endl;
                return;
            } else if (pre[i] < pre[n] - pre[n - i]) {
                cout << "NO" << endl;
                return;
            }
        }
        cout << "NO" << endl;
    } else {
        for (int i = n / 2; i >= 1; i--) {
            if (pre[i] > pre[n] - pre[n - i + 1]) {
                cout << "YES" << endl;
                return;
            } else if (pre[i] < pre[n] - pre[n - i + 1]) {
                cout << "NO" << endl;
                return;
            }
        }
        cout << "NO" << endl;
    }
    return;
}
signed main() {
    // freopen("1010.in", "r", stdin);
    // freopen("1010.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
    return  0;
}

D

考虑一个节点 $i$ 的两个儿子 $x$ 和 $y$ ，先放哪个收益更高只取决于 $\frac{A_x}{B_x}$ 和 $\frac{A_y}{B_y}。因此用优先队列维护这个值，每次再用并查集维护所属连通块的权值和即可。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define int long long
const int mod = 998244353;
const int maxn = 2e5 + 5;
struct DSU {
    vector<int> f, siz;
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    bool merge(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return 0;
        f[q] = p;
        siz[p] += siz[q];
        return 1;
    }
    DSU(int n) {
        f.resize(n + 1);
        siz.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            f[i] = i, siz[i] = 1;
        }
    }
};
int n;
int a[maxn], b[maxn], fa[maxn];

void Solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n;i ++) {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> fa[i];
    }
    DSU dsu(n);
    priority_queue<pair<double, int>> q;
    vector<int> vis(n + 1, 0);
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        q.push({1.0 * a[i] / b[i], i});
    }
    while (!q.empty()) {
        int now = (q.top()).second; q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        int nowf = dsu.find(fa[now]);
        now = dsu.find(now);
        ans += a[now] * b[nowf];
        dsu.merge(nowf, now);
        a[nowf] += a[now], b[nowf] += b[now];
        if (nowf != 1) q.push({1.0 * a[nowf] / b[nowf], nowf});
    }
    cout << ans << endl;
}
signed main() {
    // freopen("1004.in", "r", stdin);
    // freopen("1004.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
    return  0;
}

H

首先，最后答案中，相邻数字串的长度差一定不超过 1。

考虑答案中最长数字串的长度，会发现其不会超过 $\sqrt{n}$ 。

设 $f_{i, j}$ 表示前 $i$ 位中，以 $i$ 结尾的数字子序列长度为 $j$ 时的最长上升数字子序列长度。

f_{i,j} = \max_{k = 1}^{i - j}\max_{p = 1}^{j} \{f_{k,p}\} + 1

我们考虑按 $j$ 进行 dp，分两种情况讨论：

当 $p < j$ 时，我们直接维护一个 $g_{i,j}$ 表示前 $i$ 位中，最后一个数字子序列长度不超过 $j$ 时的最长上升数字子序列长度，每次就可以 $O(1)$ 转移；
当 $p = j$ ，注意到 $f_{k,p}$ 所对应的最后一个数字串的字典序必须严格小于当前串才能进行转移。这时可以按所有长度为 $j$ 的数字串的字典序升序枚举，用线段树维护前缀最大值。

时间复杂度 $O(n\sqrt{n}\log n)$

A

F

1. 端点 i=1i=1i=1

2. 端点 i=ni=ni=n

3. 内部点 2≤i≤n−12\le i\le n-12≤i≤n−1

汇总

E

J

D

H

1. 端点 $i=1$

2. 端点 $i=n$

3. 内部点 $2\le i\le n-1$