2025牛客寒假训练营4蒻蒻题解（L,A,F,J）

这场由于赛时写错暴力+思路出现偏差（看到区间问题下意识离线处理，结果根本不需要），致使自己在L题卡了太久，总体发挥不太好

L.Tokitsukaze and XOR-Triangle

给定两个长度皆为的数组，需要多次求解指定的.

首先对于位运算的题，拆位是必然的。我们可以先对于每个，求解区间的贡献。然后考虑，可以通过的贡献减去的贡献、再额外减去区间内与区间内产生的贡献。时间复杂度。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI3 array<int, 3>
#define B bitset<32>

const int inf = 4e18;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int t = 1, n, q, u;
B a[N], b[N];
int Atot[N][33]; // 记录区间内该位为1的个数（对a数组）
int Btot[N][33]; // 记录区间内该位为1的个数（对b数组）
int pow2[N];
int res[N];

void Build()
{
    for (int i = 1; i <= n; i++)
    {
        res[i] = res[i - 1];
        for (int j = 0; j <= 30; j++)
            (res[i] += pow2[j] * (b[i][j] ? i - Atot[i][j] : Atot[i][j]) % mod) %= mod;
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pow2[0] = 1;
    for (int i = 1; i <= 30; i++)
        (pow2[i] = pow2[i - 1] * 2) %= mod;

    cin >> t;
    while (t--)
    {
        cin >> n >> q;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= 30; j++)
                Atot[i][j] = 0, Btot[i][j] = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> u;
            a[i] = u;
            for (int j = 0; j <= 30; j++)
                Atot[i][j] = Atot[i - 1][j] + a[i][j];
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> u;
            b[i] = u;
            for (int j = 0; j <= 30; j++)
                Btot[i][j] = Btot[i - 1][j] + b[i][j];
        }
        Build();
        while (q--)
        {
            int l, r;
            cin >> l >> r;
            int ans = (res[r] - res[l - 1] + mod) % mod;
            for (int j = 0; j <= 30; j++)
            {
                (ans += mod - (l - 1 - Atot[l - 1][j]) * (Btot[r][j] - Btot[l - 1][j]) % mod * pow2[j] % mod) %= mod;
                (ans += mod - Atot[l - 1][j] * (r - l + 1 - (Btot[r][j] - Btot[l - 1][j])) % mod * pow2[j] % mod) %= mod;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

A.Tokitsukaze and Absolute Expectation

给定一个数组，数组内每个元素都在指定范围内随机生成，求解的期望。

看到这题，那肯定是一组一组去算的（位置1,2、位置2,3、...）。这里的话，在思考时我们可以考虑枚举一下里面每个可能的值对于数组的期望（当然代码肯定不能这么写）。显然，对于，其实这里只有两种情况需要考虑，一种是在区间内，还有一种即为在区间外。手模一下即可分别找到这两种情况的规律（在区间内实质是两个二阶等差数列的贡献和，在区间外则为公差为的等差数列，因为每离区间远，所有可能产生的数都会，期望同样。）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>

const int inf = 4e18;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int t = 1, n;
int ans;
int L[N], R[N];

// 板子
int fpow(int a, int x)
{
    int _res = a % mod, _ans = 1;
    while (x)
    {
        if (x & 1)
            _ans = _ans * _res % mod;
        _res = _res * _res % mod;
        x >>= 1;
    }
    return _ans;
}

// mod必须是质数
int inv(int a)
{
    return fpow(a, mod - 2);
}
const int INV2 = inv(2);
const int INV6 = inv(6);

int solve(int pos)
{
    int ret = 0;
    int cur = inv(R[pos - 1] - L[pos - 1] + 1); // 枚举pos-1的位置
    int base = (R[pos] - L[pos]) * INV2 % mod;  // 计算每个位置对于pos的贡献

    if (L[pos - 1] < L[pos]) // 计算左侧的
    {
        int tmpL = L[pos - 1], tmpR = min(R[pos - 1], L[pos] - 1);
        int a1 = base + (L[pos] - tmpR);
        int tot = tmpR - tmpL + 1;
        (ret += tot * a1 % mod + tot * (tot - 1) % mod * INV2 % mod) %= mod;
    }

    if (R[pos - 1] > R[pos]) // 计算右侧的
    {
        int tmpL = max(L[pos - 1], R[pos] + 1), tmpR = R[pos - 1];
        int a1 = base + (tmpL - R[pos]);
        int tot = tmpR - tmpL + 1;
        (ret += tot * a1 % mod + tot * (tot - 1) % mod * INV2 % mod) %= mod;
    }

    if (L[pos - 1] > R[pos] || R[pos - 1] < L[pos])
        return ret * cur % mod;
    int tmpL = max(L[pos - 1], L[pos]), tmpR = min(R[pos - 1], R[pos]);
    int len = 0;
    int tmpret = 0;
    len = tmpR - L[pos];
    // cout << pos << '+' << len << '\n';
    //  二阶等差数列。一直加到第tmpR
    (tmpret += INV6 % mod * len % mod * (len + 1) % mod * (len + 2) % mod) %= mod;
    len = tmpL - 1 - L[pos];
    // cout << pos << '-' << len << '\n';
    (tmpret += (mod - INV6 % mod * len % mod * (len + 1) % mod * (len + 2) % mod)) %= mod;

    len = R[pos] - tmpL;
    //  二阶等差数列。一直加到第tmpL
    (tmpret += INV6 % mod * len % mod * (len + 1) % mod * (len + 2) % mod) %= mod;
    len = (R[pos] - tmpR) - 1;
    (tmpret += (mod - INV6 % mod * len % mod * (len + 1) % mod * (len + 2) % mod)) %= mod;

    (ret += tmpret * inv(R[pos] - L[pos] + 1) % mod) %= mod;
    return ret * cur % mod;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n;
        ans = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> L[i] >> R[i];
            if (i != 1)
                (ans += solve(i)) %= mod;
        }
        cout << ans << '\n';
    }
    return 0;
}

F.Tokitsukaze and Kth Problem (easy)

给定一个数组，求解所有二元组的的前大分别是哪些。

算是牛客寒假赛到现在为止最难的题了，不过也还是有迹可循。显然，对于每个可以直接，且数组此时可以随便排序。从小到大排序后，对于每个位置，可以寻找到最后一个满足的位置，用这个位置的对应指针遍历的所有情况；再找到最后一个满足的位置（其实就是），用这个位置的对应指针遍历的所有情况。全程使用优先队列维护即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
#define PI3 array<int, 3>

const int inf = 4e18;
const int N = 1e6 + 5;
int t = 1, n, p, k;
vector<int> arr;

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> p >> k;
        arr.clear();
        for (int i = 1; i <= n; i++)
        {
            int u;
            cin >> u;
            arr.push_back(u % p);
        }
        sort(arr.begin(), arr.end());

        priority_queue<PI3> pr;
        set<PII> s;
        for (int i = 0; i < n; i++)
        {
            int fp = lower_bound(arr.begin(), arr.end(), p - arr[i]) - arr.begin() - 1;
            if (fp == i)
                fp--;
            if (fp != -1)
                pr.push({arr[fp] + arr[i], fp, i}); // 分别对应实际值，当前指针位置和初始位置
        }
        for (int i = 0; i < n - 1; i++)
            if (arr[n - 1] + arr[i] >= p)
                pr.push({(arr[n - 1] + arr[i]) % p, n - 1, i});
        if (arr[n - 2] + arr[n - 1] >= p)
            pr.push({(arr[n - 2] + arr[n - 1]) % p, n - 2, n - 1});

        while (!pr.empty())
        {
            PI3 g = pr.top();
            pr.pop();

            if (s.insert({min(g[1], g[2]), max(g[1], g[2])}).second)
            {
                cout << g[0] << ' ';
                if (--k == 0)
                    break;
            }

            int nxt = (g[1] - 1 == g[2] ? g[1] - 2 : g[1] - 1);
            if (nxt < 0)
                continue;
            if (arr[g[1]] + arr[g[2]] >= p && arr[nxt] + arr[g[2]] < p) // 剪枝，减少重复遍历
                continue;
            pr.push({(arr[nxt] + arr[g[2]]) % p, nxt, g[2]});
        }
        while (k--)
            cout << -1 << ' ';
        cout << '\n';
    }
    return 0;
}

J.Tokitsukaze and Recall

又臭又长的模拟题（不是

大致题意是：现有点边的图（都是敌人），你有一个军队（初始位于点，不与任何其他点联通）和个固定后可无限使用的传送器，军队只能占领传送器位置所在的点或已经占领位置附近的点，求最多的占领点数与对应的最小字典序占领顺序。

加强版的。首先贪心选大的联通块必然，然后还要注意如果超过了联通块的总数，则剩余的还可以用来强制改变占领顺序（减小字典序）。核心思路就是这样了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>

const int inf = 4e18;
const int N = 2e5 + 5;
int t = 1, n, m, k;
vector<int> g[N];
int fa[N], siz[N]; // 并查集
bool vis[N];
set<int> all[N];

int Find(int m1)
{
    if (fa[m1] == m1)
        return m1;
    return fa[m1] = Find(fa[m1]);
}

void Merge(int m1, int m2)
{
    int tmp1 = Find(m1);
    int tmp2 = Find(m2);
    if (tmp1 > tmp2)
        swap(tmp1, tmp2);
    if (tmp1 < tmp2)
        fa[tmp2] = tmp1, siz[tmp1] += siz[tmp2];
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> k;
        int ans = 0;
        for (int i = 1; i <= n; i++)
            fa[i] = i, siz[i] = 1, vis[i] = 0, g[i].clear(), all[i].clear();
        while (m--)
        {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            Merge(u, v);
        }
        for (int i = 1; i <= n; i++)
            if (i == Find(i))
                all[siz[i]].insert(i);

        set<int> arr;
        for (int i = n; i >= 1 && k > 0; i--)
            for (int j : all[i])
            {
                ans += i, arr.insert(j);
                if (!(--k))
                    break;
            }

        int now = 0;
        cout << ans << '\n';
        while (arr.size())
        {
            int cur = *arr.begin();
            if (k && (cur > now + 1))
            {
                arr.insert(now + 1);
                cur = now + 1;
                k--;
            }
            arr.erase(cur);
            vis[cur] = 1;
            now = cur;
            cout << cur << ' ';
            for (int adj : g[cur])
                if (!vis[adj])
                    arr.insert(adj);
        }
        cout << '\n';
    }
    return 0;
}

后话：

题是在的基础上套了个主席树，有阵子没用主席树了，所以之后复习了再回来补

逆天题搞个五维，这题估计不会去补了（逃