2025 牛客寒假 6 部分题解 (E, D, H, I)

6个月前更新

290

本文首先发布于个人博客，博客园不定期更新，推荐去我的博客阅读。

I 小鸡的排列构造的 checker

看题第一反应是主席树。

定义 \(lst[x]\) 表示值 \(x\) 出现的下标（因为是排列只会出现一次），则每次询问中要求的区间排名即为 \(lst\) 上 \(p[c]\) 左侧在 \([l,r]\) 之间的数的个数，加上 \(l\) 就是答案。使用扫描线——离线树状数组解决即可。（如果你没有学过二位数点，类比树状数组求逆序对即可）。

赛时代码：

int n, m;
cin >> n >> m;

vector<int> p(n + 1);
for (int &num : p | views::drop(1)) {
    cin >> num;
}

struct Query {
    int l, r, c, id;
};

vector<vector<Query>> queryByCVal(n + 1);
for (int i = 0; i < m; i++) {
    Query query;
    auto &[l, r, c, id] = query;
    cin >> l >> r >> c;
    id = i;
    queryByCVal[p[c]].push_back(query);
}

vector<int> lst(n + 1);
for (int i = 1; i <= n; i++) {
    lst[p[i]] = i;
}

Fenwick<int> tree(n);
vector<int> ans(m);

for (int val = 1; val <= n; val++) {
    for (auto q : queryByCVal[val]) {
        ans[q.id] = tree.GetSum(q.r) - tree.GetSum(q.l - 1) + q.l;
    }

    tree.Add(lst[val], +1);
}

for (int num : ans) {
    cout << num << '\n';
}

H 小鸡的排列构造

我讨厌构造题…

猜测无论输入如何都存在满足条件的排列（即任意奇数或者偶数长度区间都是全错排），试着构造：

当 \(r – l + 1\) 为奇数时：\(n=3\) 的情况平凡，2 3 1 或者 3 1 2。以前者为例，考虑以此构造 \(n=4\) 的情况，设第 4 位为 x，由于后三位 3 1 x 必须满足全错排，因此只能是 2 3 1 1.5 的大小关系，即 3 4 1 2。同理构造 \(n=5\) 的情况：3 4 1 2 0.5 即 4 5 2 3 1，以此类推，不难看出规律 n-1,n,n-3,n-2,...。（如果从 3 1 2 出发能得到另一组构造）。

不太清楚“对于一个任意长度为 3 的区间都是全错排的排列，任意长度为 5, 7, 9… 的区间也是全错排”怎么形式化的理解或证明，但是观察我们构造出的序列显然是满足的。

\(r – l + 1\) 为偶数时同理，可以得到构造 n, n-1, n-2, n-3, ...。

赛时代码：

int n, m;
cin >> n >> m;

int parity = 0;
for (int i = 1; i <= m; i++) {
    int l, r, c;
    cin >> l >> r >> c;
    parity = (r - l + 1) & 1;
}

if (parity == 1) {
    for (int i = n - 1; i >= 1; i -= 2) {
        cout << i << ' ' << i + 1 << ' ';
    }
    if (n % 2 == 1) {
        cout << 1;
    }
    cout << '\n';
}
else {
    for (int i = n; i >= 1; i--) {
        cout << i << ' ';
    }
    cout << '\n';
}

D Viva La Vida(Fried-Chicken’s Version)

虽然题目是无向边，但是我们先将其看作有向边。画个简单的图，结论其实就一目了然：

（剩下的边用更大的数补全即可）

边权就类似势能一样，从高走向低，因此不能成环（重边除外）。由于出度为 1，所以每个联通分量一定有且仅有一个重边，所以数重边个数即可。

由于边权是排列，没有相等的数，也就是说对于一条重边，它的边权就是和这两个点相连的 \(2n-3\) 条边里最小的一条，概率 \(\cfrac{1}{2n-3}\)。由期望的线性性，总期望就是每一条的期望之和，即 \(\cfrac{C_n^2}{2n-3}\)。

代码略。

E 任造化落骰

参考官方题解的做法，先用单调栈预处理出 \(nxtMax[i]\)，即 \(i\) 之后下一个改变 \(\max\) 的位置，然后枚举左端点 \(l\)，用双指针处理 \(\max \times \min\) 为 \(val\) 的二元对的个数，做个后缀和，每次询问二分找要的值就行。

代码：

int n, m, q;
cin >> n >> m >> q;

vector<int> a(n);
for (int &num : a) {
    cin >> num;
}

auto calc = [&](const function<bool(int, int)> &cmp) {
    stack<int> St;
    vector<int> nxt(n);

    for (int i = n - 1; i >= 0; i--) {
        while (St.empty() == false && cmp(a[St.top()], a[i]) == false) {
            St.pop();
        }

        if (St.empty()) {
            nxt[i] = n;
        }
        else {
            nxt[i] = St.top();
        }

        St.push(i);
    }
    return nxt;
};

auto nxtMin = calc(less());
auto nxtMax = calc(greater());

map<ll, ll> bkt;
for (int l = 0; l < n; l++) {
    for (int i = l, j = l; i < n && j < n;) {
        if (nxtMin[i] < nxtMax[j]) {
            bkt[1ll * a[i] * a[j]] += nxtMin[i] - max(i, j);
            i = nxtMin[i];
        }
        else {
            bkt[1ll * a[i] * a[j]] += nxtMax[j] - max(i, j);
            j = nxtMax[j];
        }
    }
}

vector<ll> vals;
vector<ll> sufSum;
for (auto [val, cnt] : bkt) {
    vals.push_back(val);
    sufSum.push_back(cnt);
}

for (int i = sufSum.size() - 2; i >= 0; i--) {
    sufSum[i] += sufSum[i + 1];
}

while (q--) {
    ll k;
    cin >> k;

    int ind = ranges::lower_bound(vals, k) - vals.begin();
    cout << sufSum[ind] << '\n';
}

来源链接：https://www.cnblogs.com/satori-march/p/18715461

评分

欢迎为Ta评分