2026暑期牛客多校2 2026-7-22

sol 7

以下题目按照难度顺序给出

M

签到

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define fi first
#define se second
#define dbg(x) cout<<#x<<" = "<<x<<endl;
#define dbg2(x,y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl;
#define forn for(int i=1;i<=n;i++)
#pragma GCC optimize(2)
using namespace std;

void solve(){
int n,m;
cin>>n>>m;
int kk=n*(n-1)/2;
if(m>=kk){
cout<<"0\n";
return;
}
//最大就是n-1
if(m<=n-1){
int ans=(1+m-1)*(m-1)/2;
cout<<ans<<"\n";
return;
}
else{
int ans=(1+n-2)*(n-2)/2;
ans-=(m-(n-1));
cout<<ans<<"\n";
return;
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--){
solve();
}

return 0;
}

N

签到

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

#define int long long

void solve(){
int n,k;
cin>>n>>k;
vector<int>a(n+1),pre(n+5);
int sum=0;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a.begin()+1,a.end());
for(int i=1;i<=n;i++){
sum+=a[i];
pre[i]=pre[i-1]+a[i];
}
if(k&1){
int hf=k/2;
int Max=-1e18;
for(int i=hf+1;i<=n-hf;i++){
int num=a[i];
// cout<<num<<endl;
int dt=k*num-pre[hf]-(pre[i+hf]-pre[i-1]);

Max=max(Max,dt);
}
cout<<sum+Max<<"\n";
return;
}
else{
int hf=(k)/2;
int Max=-1e18;
for(int i=hf;i<=n-hf;i++){
double num=1.0*(a[i]+a[i+1])/2.0;
//cout<<num<<endl;
int dt=1.0*k*num-pre[hf-1]-(pre[i+hf]-pre[i-1]);
//int Dt=(int)dt;
Max=max(Max,dt);
}
cout<<sum+Max<<"\n";
return;
}
}

signed main(){
int _t;
cin>>_t;
while(_t--){
solve();
}
}

B;

线性基模板题

注意到所有数的亦或和固定，则对这个sumxor来说，它是1的维度被拆分也是1 0，对和没有影响，而原来是0的维度，我们则希望将它拆成 1 1，对和的增量为拆出来的数*2

a+b=(a^b)+(a&b)*2

把所有数xor xorsum为1的位，建立线性基，从高位往低位贪心的取，求最大值，最后的贡献就是这个Max*2;

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"
LL mod=998244353;
LL ksm(LL a,LL n){
LL res=1;
while(n){
if(n&1)res=res*a%mod;
n/=2;
a=a*a%mod;
}
return res%mod;
}
void solve(){
LL n;
cin>>n;
vector<LL>a(n+1);
LL ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
ans^=a[i];
}
vector<LL>f(60);
LL ans2=0;
for(int i=1;i<=n;i++){
for(int j=32;j>=0;j--){
if((ans>>j)&1){
if((a[i]>>j)&1){
a[i]-=(1ll<<j);
}
//ans2|=(1ll<<j);
}
}
for(int j=32;j>=0;j--){
if((a[i]>>j)&1){
if(f[j]){
a[i]^=f[j];

}
else{
f[j]=a[i];
break;
}
}
}
}
ans2=ans;
ans-=ans2;
LL ans1=0,x=0;
for(int i=32;i>=0;i--){
// if((x>>i)&1)continue;
if((x^f[i])>x)x^=f[i];
}
ans1=(x^ans)+x;
cout<<2*x+ans2<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
LL T=1;
// build();
cin>>T;
while(T--){
solve();
}
}

L

对于一组1≤ipj ，则如果Api >Ap j ，则对打乱后逆序对变化的贡献是+1， 因为一开始是逆序对，后来不是了；否则对打乱后逆序对变化的贡献是 −1 。 所以只需考虑p的逆序对，打乱前后逆序对的差的绝对值就是这些贡献 和的绝对值。

因为这些贡献绝对值都是1，能否让这些逆序对对结果的贡献都是同方 向的，即都是+1或−1，让整体变动的绝对值最大化呢？ 答案是肯定的，A=[1,2,...,n] 正是这样的一个排列。 所以我们要求的就是对于p中所有的逆序对(i,j)(1≤iAj 的排列A的个数。 根据这些大小关系，可以建立一个从小的数指向大的数的一个有向图， 我们相当于要求其拓扑序个数。

考虑一个还没确定拓扑序的子集S对应的答案是dp[S]，我们可以任意 去除一个子集中对它没有入边的点u，则我们可以将dp[S−{u}]转移 到dp[S] 中去。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"
LL mod=998244353;
LL ksm(LL a,LL n){
LL res=1;
while(n){
if(n&1)res=res*a%mod;
n/=2;
a=a*a%mod;
}
return res%mod;
}
mt19937 rnd(time(0));
void solve(){
LL n;
cin>>n;
vector<LL>p(n+1),b(n+1);
for(int i=1;i<=n;i++){
cin>>p[i];
}
int f=0;
vector<vector<LL>>edag(n+1);
vector<LL>dep(n+1);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(p[i]>p[j])edag[i-1].push_back(j-1),f=1,dep[j-1]++;

}
}
if(!f){
LL ans=1;
for(int i=1;i<=n;i++){
ans*=i;
ans%=mod;
}
cout<<ans<<endl;
return;
}
vector<LL>dp(1LL<<n);
dp[0]=1;
auto dfs=[&](auto&&self,int x)->LL{
if(x==0)return 1;
vector<LL>a;
for(int i=n;i>=0;i--){
if((x>>i)&1){
a.push_back(i);
}
}
LL res=0;
for(int x1:a){
if(dep[x1])continue;
for(int y:edag[x1]){
dep[y]--;
//dep[y]++;
}
if(dp[(x^(1ll<<x1))]==0)res+=self(self,x^(1ll<<x1));
else res+=dp[(x^(1ll<<x1))];
res%=mod;
for(int y:edag[x1]){
dep[y]++;
}
}
dp[x]+=res;
return dp[x]%mod;
};
LL ans=dfs(dfs,(1ll<<n)-1);
cout<<2*ans%mod<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
LL T=1;
// build();
// cin>>T;
while(T--){
solve();
}
}

G

如果存在一个质数p在u,v之间，则dis(u,v) 不超过 u→p的 边权加上p→v的边权，因此答案不超过2。

所以我们想到预处理（1，x)间存在的与n gcd =1 的数；

1.莫比乌斯反演 直接处理

2.容斥定理：某个区间含有因数p的数的个数是len/p,所有数-含单个因数的数+含两个因数的数...

(其实本质就是莫比乌斯反演）

但是考虑当区间被缩减到一个较小区间，不一定存在这样一个质数，所以我们考虑在临界开始dp求解，暴力dp即可

code:

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

#define int long long
vector<int>ins;
int k;
int n;
int calc(int x){
if(x<=0)return 0;
int Mask=(1<<k);
int cnt=0;
for(int i=0;i<Mask;i++){
int num=1;
int bits=0;
for(int j=0;j<k;j++){
if((i>>j)&1){
num*=ins[j];
bits++;
}
}
if(bits&1)cnt-=(x/num);
else cnt+=(x/num);
}
return cnt;
}
void solve(){
ins.clear();
int l,r;
cin>>l>>r>>n;
int tmp=n;
for(int i=2;i*i<=tmp;i++){
if(tmp%i==0){
ins.push_back(i);
while(tmp%i==0)tmp/=i;
}
}
if(tmp>1)ins.push_back(tmp);

k=ins.size();
int ans=0;
int nr=min(r,n-150-1);
if(l<=nr){
int len=nr-l+1;
int xx=calc(nr)-calc(l-1);
ans+=2*len-xx;
}
int st=max(l,n-150);
if(st<=r){
int len=n-st+1;
vector<int>dp(len);
dp[n-st]=0;
for(int i=n-1;i>=st;i--){
int Max=__gcd(i,n);
for(int j=i+1;j<n;j++){
Max=min(Max,__gcd(i,j)+dp[j-st]);
}
dp[i-st]=Max;
}
for(int i=st;i<=r;i++){
ans+=dp[i-st];
}
}

cout<<ans<<"\n";
}

signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _t;
cin>>_t;
while(_t--){
solve();
}
}

H

0 ∼2n−1 中的数中，二进制表示中有奇数个1的数有偶数个，偶数个 1 的数也有偶数个。 而配对的两个数满足二进制表示中1的个数的奇偶性相同，因此选取的 a, b 的二进制表示中1的个数的奇偶性也相同，否则无法构造。 对于奇偶性相同的情况，如何构造呢？ 有很多办法，这里给出一个比较不需要动脑的。首先，我可以将所有配 对的数都异或上一个a，这不影响配对关系。同时，我们可以将二进制 不同的位进行重新映射，把所有b当前是1的位全部都挪到最低的位上 去。

也就是，可以将题目转化为删去0,22k−1的情况。 对于22k ∼2n−1 的数，可以将每个数和它异或3的结果匹配。 k =1 的方案是显然的。 我们可以在删去0,22k−1 的对应方案的基础上，构造删去0,22(k+1)−1 的方案。 设V=22k−1 ，则将(V,2V) 和(2V⊕3,4V) 匹配即可，这样相当于拆 掉了原有的(2V,2V⊕3) 和 (4V,4V⊕3) 而重新构造了两对，同时也让 没有匹配的数从V变成了4V+3。 时间复杂度为O(2n) 。

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

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);

int t;
cin >> t;

while (t --) {
int n, x, y, c = 0;
cin >> n >> x >> y;

for (int i = 0; i < n; i ++) c += (x ^ y) >> i & 1;

if (c & 1) cout << "No\n";
else {
cout << "Yes\n";

int diff = x ^ y, k = c;

vector<int> pairing(1 << n);
for (int i = 0; i < (1 << n); i ++) {
pairing[i] = i ^ 3;
}

pairing[0] = 0;
pairing[3] = 3;

for (int i = 2; i < k; i += 2) {
int cur = (1 << i) - 1;
pairing[cur] = cur << 1;
pairing[cur << 1] = cur;

pairing[(cur << 1) ^ 3] = cur << 2;
pairing[cur << 2] = (cur << 1) ^ 3;

pairing[(cur << 2) ^ 3] = (cur << 2) ^ 3;
}

vector<int> vals = {0};

for (int i = 0; i < n; i ++) {
if (diff >> i & 1) {
int cur_len = vals.size();
for (int j = 0; j < cur_len; j ++) {
vals.emplace_back(vals[j] ^ (1 << i));
}
}
}

for (int i = 0; i < n; i ++) {
if (!(diff >> i & 1)) {
int cur_len = vals.size();
for (int j = 0; j < cur_len; j ++) {
vals.emplace_back(vals[j] ^ (1 << i));
}
}
}

for (int i = 0; i < (1 << n); i ++) {
if (pairing[i] > i) {
cout << (vals[i] ^ x) << ' ' << (vals[pairing[i]] ^ x) << '\n';
}
}
}
}

return 0;
}

F

首先，如果对于一棵树，其最大边权为W，则该树最大极差的最小值 不超过2W−1。

证明：直接对根节点赋值X，接下来从根节点出发进行搜索，每个新搜 索到的点一定能在[X−W,X+W)区间内找到一个可行的权值。

令dp[u][x]表示当前根为u，当前节点取x情况下子树最大节点的最小值

而因为所有节点的值可以同时平移，所以节点的最小值一定为0，则这个Min of Max 也可以表示子树最大极差；

对于叶子节点，它取几这个最大节点的最小值就是几，所以：for(intj=0;j<=Max;j++)dp[u][j]=j;

考虑转移 对于一个节点的固定值x，它的下级节点只能是x-w或者x+w;

所以：

intva=inf;

if(x-V.y0>=0)va=min(va,dp[V.x0][x-V.y0]);

if(x+V.y0<=Max)va=min(va,dp[V.x0][x+V.y0]);

我们贪心的取最小，

dp[u][x]=max(dp[u][x],va);

取Max的原因是要求全部满足

然后独立求解每颗子树即可

for(intx=0;x<=Max;x++)ans[u]=min(ans[u],dp[u][x]);

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=1e5+5,mod=998244353,M=5000;
int lowbit(int x){
return x&(-x);}
vector<Pii>g[N];
//int dp[N][M];
int f[N],fv[N];
void init(int n){
fr(i,1,n){
g[i].clear();
f[i]=0;
fv[i]=0;
}
//memset(dp,0,sizeof(dp));
}
void solve(){
int n;
cin>>n;
init(n);
int u,v,w;
int Max=0LL;
fr(i,2,n){
cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
Max=max(Max,w);
}
Max<<=1;
vector<vector<int>>dp(n+1,vector<int>(Max+1));
//dp[节点][当前节点值]= 子树节点最大权值的最小值
vector<int>node;
queue<int>q;
//node.pb(1);
f[1]=-1;
fv[1]=0;
q.push(1);
while(!q.empty()){
int t=q.front();
q.pop();
node.pb(t);
for(Pii V:g[t]){
if(V.x0==f[t])continue;
f[V.x0]=t;
fv[V.x0]=V.y0;
//node.pb(V.x0);
q.push(V.x0);
}
}
vector<int>ans(n+1,0);
for(int i=n-1;i>=0;i--){
int u=node[i];
for(int j=0;j<=Max;j++)dp[u][j]=j;
for(Pii V:g[u]){
if(f[V.x0]!=u)continue;
for(int x=0;x<=Max;x++){
int va=inf;
if(x-V.y0>=0)va=min(va,dp[V.x0][x-V.y0]);
if(x+V.y0<=Max)va=min(va,dp[V.x0][x+V.y0]);
dp[u][x]=max(dp[u][x],va);
//ans[u]=min(ans[u],dp[u][x]);
}
}
ans[u]=inf;
for(int x=0;x<=Max;x++)ans[u]=min(ans[u],dp[u][x]);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<"\n";
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}