26牛客暑假多校2

点击查看题面

M题 Maybe Connected

题目大意

有$n$个点，$m$条边，求连通但不相连点的对数，无自环或重边

数据范围：$1⩽n⩽{10}^5,0⩽m⩽min({10}^9,{\displaystyle \frac{n(n-1)}{2}})$

思路

• $n\le 2$时，无论怎样都是0
• 当所有点连接成一条线的时候，取得最大值 当有$k$个点一条线，则有${\displaystyle \frac{(k-1)(k-2)}{2}}$对点
• 当$m\le n-1$时 可以将$m+1$个点连成一条线，取得最大值${\displaystyle \frac{m(m-1)}{2}}$
• 在$m=n-1$时取得最大值，当$m\ge n$时，每多一条边，最大值将减1，需要减去的部分为$m-(n-1)$多余出来边数

复杂度分析

时间复杂度：$O(1)$
空间复杂度：$O(1)$

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void fc() {
	ll n,m;std::cin>>n>>m;
    
    if(n<=2){
        std::cout<<0<<"\n";return;
    }
    
    if(m<=n-1){
        std::cout<<m*(m-1)/2<<"\n";
    }else{
        std::cout<<(n-1)*(n-2)/2-(m-(n-1))<<"\n";
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	std::cin>>t;
	while (t--) fc();
	return 0;
}

N题 Lazy Shuffling

题目大意

给定一个长度为n的数组，要求执行恰好一次，每次选取$k$个数，将$k$个数都变成这$k$个数都中位数，求这个数组最终和的最大值

数据范围：$1⩽k⩽n,\sum n⩽2\times {10}^5,1⩽a_i⩽{10}^9$

思路

• 由于排序不会影响答案，先排序
• 在升序条件下，要求操作后增量最大化，应当小于和大于中位数的部分都要最小，即假设$M$为中位数，前$x$个较小元素$(<=M)$无额外限制，直接取全局最小的$x$个，后$y$个较大元素$(>=M)$,最优解为紧跟中位数之后连续的$y$个

1. $k$为奇数

• $m=\lfloor \frac{k-1}{2}\rfloor$，中位数 $M=b_m$
• 增量展开：

$$\mathrm{\Delta }=2m\cdot b_m-\sum _{i=0}^{m-1}{b}_i-\sum _{i=m+1}^{2m}{b}_i$$

贪心构造：

• 1. 较小元素集合 ($b_0\dots b_{m-1}$)：仅需满足 $b_i\le b_m$，无额外下界限制。要使和最小，直接选取全局最小的前 $m$ 个数，即排序后的前缀 $a_0,a_1,\dots ,a_{m-1}$。
• 2. 较大元素集合 ($b_{m+1}\dots b_{2m}$)：必须满足 $b_i\ge b_m$。要使和最小，最优解为在排序数组中紧跟在 $b_m$ 后的连续 $m$ 个元素。

结构结论：

• 1. 设 $b_m=a_j$（其中 $j\ge m$），则选取的 $k$ 个元素分割为：固定前缀：$a_0,a_1,\dots ,a_{m-1}$（共 $m$ 个元素）。
• 2. 连续区间：$a_j,a_{j+1},\dots ,a_{j+m}$（共 $m+1$ 个元素，首元素为 $a_j$）。

2. $k$为偶数

• $d=\lfloor \frac{k-1}{2}\rfloor =m-1$，中位数 $M=\frac{b_{m-1}+b_m}{2}$

• 增量展开：

$$\mathrm{\Delta }=(m-1)(b_{m-1}+b_m)-\sum _{i=0}^{m-2}{b}_i-\sum _{i=m+1}^{2m-1}{b}_i$$

贪心构造：

• 1. 较小元素集合 ($b_0\dots b_{m-2}$)：直接选取全局最小的前 $m-1$ 个数，即前缀 $a_0,a_1,\dots ,a_{m-2}$。
• 2. 较大元素集合 ($b_{m+1}\dots b_{2m-1}$)：紧跟在中位数对 $(b_{m-1},b_m)$ 后的连续 $m-1$ 个元素。

结构结论： 设 $b_{m-1}=a_j$（其中 $j\ge m-1$），则 $b_m=a_{j+1}$。选取的 $k$ 个元素分割为：

• 1. 固定前缀：$a_0,a_1,\dots ,a_{m-2}$（共 $d=m-1$ 个元素）。连续区间：$a_j,a_{j+1},\dots ,a_{j+m}$（共 $m+1$ 个元素，包含中位数对及其右侧元素）。
• 2. 连续区间：$a_j,a_{j+1},\dots ,a_{j+m}$（共 $m+1$ 个元素，包含中位数对及其右侧元素）

3.统一奇偶模型

为了方便计算，只需要统一变量无需大量奇偶讨论，通过滑动窗口求解

固定前缀长度：$d=\lfloor \frac{k-1}{2}\rfloor$

连续窗口长度：$L=k-d$

滑动范围：窗口首元素 $a_j$ 的下标 $j\in [d,n-L]$

参考代码

参考代码

#include<bits/stdc++.h>
using namespace std;

using ll = long long;


void fc() {
    int n,k;std::cin>>n>>k;
    std::vector<int>a(n);
    
    bool t=(k&1);
    ll sk=k;
    
    ll sum=0;
    for(int i=0;i<n;i++)std::cin>>a[i],sum+=a[i];
    std::sort(a.begin(),a.end());
    
    int d=(k-1)/2;
    ll s=0,ans=LLONG_MIN;
    for(int i=0;i<d;i++)s+=a[i];
    k=k-d;
    
    for(int i=d;i<n;i++){
        s+=a[i];
        if(i<d+k-1)continue;
        
        ll mid=(t?a[i-k+1]*sk:sk/2*(a[i-k+1]+a[i-k+2]));
        ans=max(ans,sum-s+mid);
        
        s-=a[i-k+1];
    }
    std::cout<<ans<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        fc();
    }
    return 0;
}

复杂度分析

时间复杂度：排序 $\mathcal{O}(n\log n)$，滑动窗口维护 $\mathcal{O}(n)$，总时间复杂度 $\mathcal{O}(n\log n)$，完美通过 $\sum n\le 2\times {10}^5$。

空间复杂度：$\mathcal{O}(n)$ 存储数组，常数空间完成窗口滑动。

B题 Bitwise Maximization

---

题目大意

给定一个长度为$n$的数组，将其分成任意两个集合，输出两个集合的异或和之和的最大值

数据范围：$\sum n\le 5\times {10}^5,0\le A_i<2^{30}$

---

思路

设全局异或和为 $S=\underset{i=1}{\overset{n}{⨁}}{A}_i$。对于任意划分，两集合异或和 $x,y$ 满足 $x\oplus y=S$。根据按位加法等式：

$$x+y=(x\oplus y)+2\cdot (x\mathrm{\&}y)=S+2\cdot (x\mathrm{\&}y)$$

由于 $S$ 为定值，目标转化为最大化 $x\mathrm{\&}y$：

1. 若 $S$ 的第 $k$ 位为 1：$x$ 与 $y$ 在该位必为一 0 一 1，故 $x\mathrm{\&}y$ 的第 $k$ 位恒为 0。
2. 若 $S$ 的第 $k$ 位为 0：$x$ 与 $y$ 在该位值相同。若能使 $x$ 在该位为 1，则 $y$ 在该位也必然为 1，此时 $x\mathrm{\&}y$ 的第 $k$ 位为 1。

然后对所有 $A_i^{\prime }$ 插入线性基，求出最大异或和 $X^{\prime }$（此 $X^{\prime }$ 即为 $x\mathrm{\&}y$ 能达到的最大值）

复杂度分析

时间复杂度： $O(n\log (max{A}_i))$

空间复杂度： $O(n)$。

参考代码

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

using ll = long long;

ll p[30];

void insert(ll x) {
    for (int i = 29; i >= 0; --i) {
        if (!(x >> i & 1)) continue;
        if (!p[i]) {
            p[i] = x;
            return;
        }
        x ^= p[i];
    }
}

void fc() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll s = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        s ^= a[i];
    }

    memset(p, 0, sizeof(p));

    for (int i = 0; i < n; ++i) {
        insert(a[i] & (~s));
    }

    ll max_x = 0;
    for (int i = 29; i >= 0; --i) {
        max_x = max(max_x, max_x ^ p[i]);
    }

    cout << max_x * 2 + s << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        fc();
    }
    return 0;
}

G题 GCD Graph

题目大意

给定一个顶点由正整数 $1,2,3,\dots$ 命名的无限有向图。对于每对满足 $1\le i<j$ 的整数 $(i,j)$，存在一条从 $i$ 到 $j$、权值为 $w_{i,j}=gcd(i,j)$ 的有向边。定义 $\text{cost}(u,v)$ 为顶点 $u$ 到 $v$ 的最小总代价。

对于给定的参数 $l,r,n$，计算并输出：

$$\sum _{i=l}^r\text{cost}(i,n)$$

数据范围：$1\le T\le 100$，$1\le l\le r<n\le {10}^7$

---

思路

设不超过 $n$ 的最大质数为 $P$。受限于素数间隙理论（Prime Gap），在 ${10}^7$ 范围内连续素数之间的最大间隔仅为 154，因此 $n-P$ 的数值极小。我们可以以 $P$ 为界将区间 $[l,r]$ 划分为两部分分别处理：

1. 对于 $x<P$ 的部分：

• 若 $gcd(x,n)=1$，存在直连边 $x\to n$，代价为 1。
• 若 $gcd(x,n)>1$，考虑取质数 $P$ 作为中转点。因为 $P$ 为质数且 $x<P$，必有 $gcd(x,P)=1$；若 $P<n$，由于 $P$ 为质数亦有 $gcd(P,n)=1$。路径 $x\to P\to n$ 的代价为 $1+1=2$。
• 因此在 $[l,min(P-1,r)]$ 范围内，与 $n$ 互质的数代价为 1，不互质的数代价为 2。设该区间长度为 $\text{len}$，其中与 $n$ 互质的个数为 $C$，则贡献为：

$${\text{ans}}_1=2\cdot \text{len}-C$$

• 利用线性筛提取 $n$ 的质因子，结合容斥原理在前缀上计算互质个数 $C=\text{count\_coprime}(R_1)-\text{count\_coprime}(l-1)$。

2. 对于 $x\ge P$ 的部分：

• 由于 $n-P$ 的范围极小，可以采用逆序动态规划求解。设 $dp[u-P]$ 表示从顶点 $u$ 到 $n$ 的最短路长度。
• 动态规划转移方程为：

$$dp[u-P]=\underset{u<i\le n}{min}(dp[i-P]+gcd(i,u))$$

• 边界条件为 $dp[n-P]=0$。

最后将两部分的贡献相加即为所求答案。

---

复杂度分析

时间复杂度：线性筛预处理为 $O(MAXN)$；每组测试用例中质因子分解耗时 $O(\log n)$，容斥原理状态数 $2^{\omega (n)}$（其中 $\omega (n)\le 8$），DP 部分耗时 $O((n-P{)}^2\log n)$。由于 $n-P\le 154$，单组测试用例的复杂度约为 $O(2^{\omega (n)}+(n-P{)}^2\log n)$，能高效通过全部数据。

空间复杂度：线性筛预处理耗费 $O(MAXN)$ 空间（约 40MB），DP 辅助数组耗费 $O(n-P)$ 空间，整体空间复杂度为 $O(MAXN)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 10000000;
vector<int> primes;
int min_prime[MAXN + 1];

// 线性筛预处理最小质因子
void sieve() {
    for (int i = 2; i <= MAXN; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > min_prime[i] || (ll)i * p > MAXN) break;
            min_prime[i * p] = p;
        }
    }
}

// 获取 n 的所有不同质因子
vector<int> get_prime_factors(int n) {
    vector<int> factors;
    while (n > 1) {
        int p = min_prime[n];
        factors.push_back(p);
        while (n % p == 0) {
            n /= p;
        }
    }
    return factors;
}

// 容斥原理：求 [1, m] 中与 n 互质的数的个数
ll count_coprime(ll m, const vector<int>& factors) {
    if (m <= 0) return 0;
    int k = factors.size();
    ll count = 0;
    int total_subsets = 1 << k;
    
    for (int mask = 0; mask < total_subsets; ++mask) {
        ll prod = 1;
        int bits = 0;
        for (int i = 0; i < k; ++i) {
            if ((mask >> i) & 1) {
                prod *= factors[i];
                bits++;
            }
        }
        if (bits % 2 == 1) {
            count -= m / prod;
        } else {
            count += m / prod;
        }
    }
    return count;
}

void fc() {
    ll l, r, n;
    cin >> l >> r >> n;
    
    // 1. 找到不超过 n 的最大质数 P
    int P = n;
    while (P > 1 && min_prime[P] != P) {
        P--;
    }
    
    ll ans = 0;
    
    // 2. 处理 x < P 的部分：使用容斥原理求解互质个数
    ll R1 = min((ll)P - 1, r);
    if (l <= R1) {
        vector<int> factors = get_prime_factors(n);
        ll len = R1 - l + 1;
        ll coprime_cnt = count_coprime(R1, factors) - count_coprime(l - 1, factors);
        ans += 2 * len - coprime_cnt;
    }
    
    // 3. 处理 x >= P 的部分：使用小范围 DP
    ll L2 = max(l, (ll)P);
    if (L2 <= r) {
        // dp[i - P] 表示从 i 到 n 的最短路长度
        vector<int> dp(n - P + 1, 0);
        dp[n - P] = 0;
        
        for (int u = n - 1; u >= P; u--) {
            int min_dist = 1e9;
            for (int i = u + 1; i <= n; i++) {
                min_dist = min(min_dist, dp[i - P] + std::gcd(i, u));
            }
            dp[u - P] = min_dist;
        }
        
        for (int x = L2; x <= r; x++) {
            ans += dp[x - P];
        }
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    sieve();
    
    int t = 1;
    cin >> t;
    while (t--) fc();
    return 0;
}

---