NOIP2023未来共同体 模拟十一

最打摆的一集，剧场版！

A. 爱吃鱼的小Y（eattt）

题目简介

给定 个数 ，现在进行 次操作：

• 随机选择 中未被删除的点 ；
• 找到 之后第一个未被删除的点 。
• 删除 ，并执行 。

求出最后剩下的 个数的和的期望。对 取模。

数据范围：

考虑分别计算每条鱼的贡献，发现 时每条鱼的贡献是相同的，因为贡献只跟前两条鱼被吃的顺序有关，使用组合数学直接计算即可。

AC Code

#include <algorithm>
#include <cstdio>
#include <vector>
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x;
}
int qpow(int a, int b, int mod)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int n, k;
int a[maxn];
signed main()
{
    freopen("eattt.in", "r", stdin);
    freopen("eattt.out", "w", stdout);
    n = read(), k = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    if (k == 0)
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
            (ans += a[i]) %= mod;
        printf("%d", ans);
        return 0;
    }
    int cou = 1, one = 1, dif = 1, sum = 0, ans = 0;
    for (int i = n - 1; i >= n - k; i--)
        cou = 1ll * cou * i % mod;
    (ans += 1ll * cou * a[1] % mod) %= mod;
    for (int i = 1; i <= k; i++)
        one = 1ll * one * (n - 1 - i) % mod;
    if (n >= 2)
        (ans += 1ll * (one - (cou - one) + mod) % mod * a[2] % mod) %= mod;
    for (int i = 1; i <= k; i++)
        dif = 1ll * dif * (n - 2 - i) % mod;
    if (n >= 3)
    {
        for (int i = 3; i <= n; i++)
            (sum += a[i]) %= mod;
        (ans += 1ll * sum * dif % mod) %= mod;
    }
    printf("%lld", 1ll * ans * qpow(cou, mod - 2, mod) % mod);
    return 0;
}
/*
10 7
1000000000 998244353 999998765 1 2 3 4 5 6 7
*/
// namespace burningContract

---

B. 万圣节（var）

题目简介

给定一个长度为 的序列 ，将 从 移动到 ，每次在对应位置累加，得到一个长度为 的数组 。

要求构造出一个长度为 的序列 ，要求 ，其中 是一个长度为 的序列，最大化：

$$\sum_{i=1}^{n}x_i\cdot w_i$$

多测。

数据范围：

有一个朴素的 ，记录 表示当前考虑 且 的最大值，那么复杂度为 。

将 视作关于 的函数，那么每次转移相当于关于 对称，调整定义域，整体加一次函数，取前缀 。

则 是一个凸包，所以直接队列 维护。

AC Code

#include <bits/stdc++.h>
#define getchar() ((p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 23, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char buf[1 << 23], *p1 = buf, *p2 = buf;
int Qread()
{
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return x;
}
void Qwrite(__int128 a)
{
    if (a < 10)
        putchar('0' + a);
    else
        Qwrite(a / 10), putchar('0' + a % 10);
}
int n, k, nd;
int a[2000010];
long long cnt[2000010];
long long b[1000010];
__int128 ans, rem1, rem2;
__int128 calc(int num)
{
    if (num < 0)
        return 0;
    __int128 ret = (__int128)num * cnt[nd];
    for (int i = nd - 1, val = num; i; i--)
        val = min(a[i] - val, a[i - 1]), ret += (__int128)val * cnt[i];
    for (int i = nd + 1, val = num; i <= n; i++)
        val = min(a[i - 1] - val, a[i]), ret += (__int128)val * cnt[i];
    return ret;
}
void solve()
{
    ans = 0;
    n = Qread(), k = Qread();
    for (int i = 1; i < n; i++)
        make_pair(a[i] = Qread(), i);
    a[0] = a[n] = 1e9 + 10;

    for (int i = 1; i <= k; i++)
        b[i] = b[i - 1] + Qread();
    for (int i = 1; i <= k; i++)
        cnt[i] = b[i], cnt[n - i + 1] = b[k] - b[k - i];
    for (int i = n - k; i > k; i--)
        cnt[i] = b[k];

    nd = n - k + 1;
    int l = 0, r = min(a[nd], a[nd - 1]), mid;
    while (l <= r)
    {
        mid = (l + r >> 1);
        rem1 = calc(mid - 1), rem2 = calc(mid);
        ans = max(ans, rem1), ans = max(ans, rem2);
        if (rem1 < rem2)
            l = mid + 1;
        else
            r = mid - 1;
    }
    Qwrite(ans);
    putchar('\n');
}
int main()
{
    freopen("var.in", "r", stdin);
    freopen("var.out", "w", stdout);
    Qread();
    int T = Qread();
    while (T--)
        solve();
    return 0;
}

---

C. 抽屉（box）

题目简介

给定 条线段 摆在长 的数轴上，满足要么 ，要么 ，且不存在完全相同的线段。维护 次操作：

• 插入一条新的线段 ；满足原来数轴上不存在线段在 中。
• 将所有线段随机摆动，满足相对顺序不变（包括嵌套内的相对顺序），求至少有多少条线段包含点 。

数据范围：，线段总和不超过

我们考虑对每一个铁盒求出其一定覆盖到的位置。先考虑 的情况，即考虑某一个不在铁盒内的铁盒。

首先不难发现， 号铁盒无法避开的位置一定是连续的一段。考虑到其连续性，将其尽可能靠左和尽可能靠右的覆盖区间交起来就是答案（具体来说就是所有同层铁盒全部靠左和所有同层铁盒全部靠右）。

考虑嵌套的情况，发现结论类似，即覆盖位置是一段区间，可以通过极端情况求交取得。

我们可以考虑维护出每个小铁盒左端点（相对其父亲）的合法区间，在查询的时候，通过把区间的两端按照在链上依次加和即可。

我们发现，对于深度越大的小铁盒，其绝对合法区间一定更大，而它的长度更小。因而，对于树上的任意一条链，一定存在一个分界点，使得比它浅的结点存在一定覆盖到的位置，而其他节点不存在。

我们可以在重链上二分，用 的复杂度找到分界点。不难发现，我们只需要维护每个铁盒的 的绝对位置。这样就可以完成每次的 check。

性质发现后，考虑实现。我们最好先离线构建出所有可能的树。

考虑更改。发现相当于在其左边的 的相对值 ，右边的 的相对值减少 。为了维护绝对值，所以要考虑把左右边节点及其子树减去。不难发现这是两个在 序上连续的区间。

用线段树进行维护。

问题在于如何处理出位置 所在的位置。考虑按照区间左端点对所有区间排序后，我们要找到的是所有 中，最后一个满足 的区间。可以考虑二分时使用线段树查询。复杂度仍然是 。

问题基本解决。实现的时候注意特判一下跳到目前不存在的树节点的情况（直接跳过）。总时间复杂度是 ，空间复杂度线性。

AC Code

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int, int> pi;

const int N = 4e5 + 5;
int n, q, L;
array<int, 3> box[N];
vector<pi> qry;
void Input()
{
    cin >> n >> q >> L;
    rep(i, 1, n)
    {
        cin >> box[i][0] >> box[i][1];
        box[i][2] = i;
    }
    rep(i, 1, q)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            n++;
            cin >> box[n][0] >> box[n][1];
            box[n][2] = n;
        }
        else
        {
            int x;
            cin >> x;
            qry.pb(mp(x, n));
        }
    }
}
struct BIT
{
    int s[N];
    void add(int d, int nw)
    {
        while (d < N)
        {
            s[d] += nw;
            d += d & -d;
        }
    }
    int query(int d)
    {
        int res = 0;
        while (d)
        {
            res += s[d];
            d -= d & -d;
        }
        return res;
    }
} T0, T1;
vi G[N];
int dfn[N], id[N], dfc, fa[N], dep[N], sz[N];
int bz[N][19];
vector<pi> bel;
void dfs(int u, int le, int ri)
{
    bz[u][0] = fa[u];
    rep(i, 1, 18)
    {
        bz[u][i] = bz[bz[u][i - 1]][i - 1];
    }
    dfc++, dfn[u] = dfc, id[dfc] = u;
    T0.add(dfn[u], le);
    T0.add(dfn[u] + 1, -le);
    T1.add(dfn[u], ri);
    T1.add(dfn[u] + 1, -ri);

    int L = box[u][0];
    for (int v : G[u])
    {
        ri += box[v][0] - L;
        L = box[v][1] + 2;
    }
    ri += box[u][1] - L + 2;
    L = box[u][0];
    int pre = box[u][0];
    for (int v : G[u])
    {
        if (v == fa[u])
        {
            continue;
        }
        if (pre < box[v][0])
        {
            bel.pb(mp(pre, u));
        }
        pre = box[v][1] + 1;

        ri -= box[v][0] - L;
        le += box[v][0] - L;
        L = box[v][1] + 2;

        dep[v] = dep[u] + 1;
        dfs(v, le, ri);
    }
    if (pre <= box[u][1])
    {
        bel.pb(mp(pre, u));
    }
    sz[u] = dfc - dfn[u] + 1;
}
int Getbel(int x)
{
    return prev(upper_bound(bel.begin(), bel.end(), mp(x + 1, -1)))->se;
}
void solve()
{
    sort(box + 1, box + n + 1, [](array<int, 3> A, array<int, 3> B)
         { return A[0] != B[0] ? A[0] < B[0] : A[1] > B[1]; });
    box[0] = {1, L, 0};
    rep(i, 1, n)
    {
        fa[i] = i - 1;
        while (box[fa[i]][1] < box[i][0])
        {
            fa[i] = fa[fa[i]];
        }
        G[fa[i]].pb(i);
    }
    dfs(0, 0, 0);
    auto Add = [&](int id, int nw)
    {
        int l0 = dfn[fa[id]] + 1, r0 = dfn[fa[id]] + sz[fa[id]] - 1;
        int l1 = dfn[id], r1 = dfn[id] + sz[id] - 1;
        T1.add(l0, nw);
        T1.add(l1, -nw);
        T0.add(r1 + 1, nw);
        T0.add(r0 + 1, -nw);
    };
    vi fp(n + 1);
    rep(i, 1, n)
    {
        Add(i, box[i][1] - box[i][0] + 2);
        fp[box[i][2]] = i;
    }
    vector<char> vis(n + 1, 0);
    vis[0] = 1;
    int pt = 0;
    for (pi x : qry)
    {
        while (pt < x.se)
        {
            pt++;
            int id = fp[pt];
            vis[id] = 1;
            Add(id, -(box[id][1] - box[id][0] + 2));
        }
        auto chk = [&](int u) -> int
        {
            if (!vis[u])
            {
                return 1;
            }
            int le = T1.query(dfn[u]), ri = T0.query(dfn[u]);
            return x.fi + ri > box[u][1] || x.fi - le < box[u][0];
        };
        int u = Getbel(x.fi);
        per(i, __lg(dep[u]), 0)
        {
            if (chk(bz[u][i]))
            {
                u = bz[u][i];
            }
        }
        cout << dep[u] - chk(u) << '\n';
    }
}
signed main()
{
    freopen("box.in", "r", stdin);
    freopen("box.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Input();
    solve();
    return 0;
}

---

D. XYH 和 AEY 的战略游戏（game）

题目简介

给定一个有 个结点 条边的无向图，无重边自环，连通。每个边通行时长 天，有一个颜色为 。

现在一些结点有居民（不存在全无的情况），要求用最短的时间将所有居民全部移动到结点 ，初始所有边全部断掉，从第 天开始，每一天可以选择一种颜色，花费 的代价将所有该颜色的边接通，之后居民开始移动，这一天结束后所有边回到全部断开的状态。

设当前居民状态为 ，将所有居民移动到结点 的最短时间为 ，最短时间下的最小花费为 ，求出：

$$\sum_s t_s,\sum_s ct_s$$

即对所有居民状态求出其最小移动时间与最小时间下花费的最小代价。多测。

数据范围：

本题最棘手的点在于很难知道启用一种颜色的边后哪些点会发生移动。首先有一个关键的观察，那就是一个集合的答案一定不会劣于它的超集的答案。正确性是显然的。考虑将问题倒过来，所有国民都在 号结点，现在要用最快的时间以及最小的代价覆盖住所有的点集内的点。我们可以认为最开始有无穷多个国民在 号结点。那么，启用一种颜色的边后，所有有国民且能发生移动的点都会将自己结点内的一部分国民移动到这条边所指向的点。这样的话，问题就迎刃而解了。

具体实现，记录 表示至少覆盖住了 的答案，枚举转移所需颜色 ，转移方程：

$$f_s[\mathrm{time}]+1,f_s[\mathrm{cost}]+w_c\rightarrow f_{\mathrm{trans}(c,s)}$$

其中 表示 中每个 颜色连接的新点扩展之后的状态，这个可以预处理。之后转移 ，从大到小枚举 然后对其大小恰好比 少 的子集转移即可。

时间复杂度 。