2025 牛客寒假算法基础集训营 1 个人题解

这场一道 DP 都没有，思维题为主，很神奇。

A 茕茕孑立之影#

显然最小的大于 $10^9$ 的质数 $1000000007$ 一定是一个合法解，仅在存在 $a_i=1$ 时无解。

~~如果读到 1 不要直接输出 -1，要先把数据读完。作者被这个坑了 10 分钟。~~

B 一气贯通之刃#

图是链，答案是链的头尾，否则无解。

D 双生双宿之决#

按题意用 map 计数即可，size != 2 都不符合题意，也要输出 -1。

G 井然有序之衡#

先求和 $a$ ，如果 $sum \not= {n(n+1) \over2}$ ，那么无法得到目标排列，否则答案是

\sum_{i=1}^{n}|a_i-i|

H 井然有序之窗#

蒟蒻作者麻烦的写法#

作者的做法比较麻烦。考虑优先让可以选的数少的位置选。选择时先选择前面没选到的，被需要次数少的数（就是被前面给定的区间包含的次数）。使用线段树来选择。

1
#include<bits/stdc++.h>
2
#define up(i,x,y) for(int i=x;i<=y;i++)
3
#define down(i,x,y) for(int i=x;i>=y;i--)
4
#define elif else if
5
#define ll long long
6
#define inf array<int,2>{1000000,-1}
7
using namespace std;
8

9
struct node{
10
  node *ls,*rs;
11
  array<int,2> x;
12
  void pull(){
13
    x=min(ls->x,rs->x);
14
  }
15
};
16
node *root,*p;
17

18
vector pre(0,0);
19

20
void assign(node *x,int l,int r,int p){
21
  if(l==r){
22
    x->x=inf;
23
    return;
24
  }
25
  int m=l+r>>1;
26
  if(p<=m) assign(x->ls,l,m,p);
27
  else assign(x->rs,m+1,r,p);
28
  x->pull();
29
};
30

31
void build(node *x,int l,int r){
32
  if(l==r){
33
    x->x={pre[l],l};
34
    return;
35
  }
36
  int mid=(l+r)/2;
37
  x->ls=++p;
38
  x->rs=++p;
39
  build(x->rs,mid+1,r);
40
  build(x->ls,l,mid);
41
  x->pull();
42
};
43

44
array<int,2> query(node *x,int l,int r,int ql,int qr){
45
  if (ql<=l and r<=qr){
46
    return x->x;
47
  }
48
  int mid=l+r>>1;
49
  auto ret=inf;
50
  if (ql<=mid){
51
    ret=min(ret,query(x->ls,l,mid,ql,qr));
52
  }
53
  if (qr>mid){
54
    ret=min(ret,query(x->rs,mid+1,r,ql,qr));
55
  }
56
  return ret;
57
}
58

59
void solve(){
60
  int n;
61
  cin>>n;
62
  vector<array<int,4>>a(n);
63
  pre=vector(n+2,0);
64
  {
65
    int cnt=0;
66
    for(auto&&[x,l,r,p]:a){
67
      cin>>l>>r;
68
      pre[l]++;
69
      pre[r+1]--;
70
      x=r-l+1;
71
      p=++cnt;
72
    }
73
    sort(a.begin(),a.end());
74
  }
75
  up(i,1,n){
76
    pre[i]+=pre[i-1];
77
  }
78
  vector<node> t(n<<2);
79
  root=&t[0],p=&t[0];
80
  build(root,1,n);
81
  vector ans(n+1,0);
82
  for(auto&&[x,l,r,p]:a){
83
    auto res=query(root,1,n,l,r);
84
    if(res[1]==-1){
85
      cout<<-1;
86
      return;
87
    }
88
    ans[p]=res[1];
89
    assign(root,1,n,res[1]);
90
  }
91
  up(i,1,n){
92
    cout<<ans[i]<<" ";
93
  }
94
}
95
int main(){
96
  ios::sync_with_stdio(0);
97
  cin.tie(0);
98
  cout.tie(0);
99
  int T=1;
100
  // cin>>T;
101
  while(T--)solve();
102
}

标程#

~~作者说这是一道非常典的题。~~

对于每个 $j$ ，选择填入在满足 $l_i\le j \le r_i$ 的所有 $i$ 中 $r_i$ 最小的 $i$ 。使用优先队列维护。

如果在选择的时候发现 $j$ 已经超出某组队列中的 $(l_i,r_i)$ ，那么无解（意味着 $a_i$ 没有数可以填入了）。没得选同样无解。

priority_queue 默认大顶堆。ranges::sort 是 C++20 引入的（牛客居然支持那么新的标准）。

1
#include<bits/stdc++.h>
2
#define up(i,x,y) for(int i=x;i<=y;i++)
3
#define down(i,x,y) for(int i=x;i>=y;i--)
4
#define elif else if
5
#define ll long long
6
using namespace std;
7

8
void solve(){
9
  int n;
10
  cin>>n;
11
  vector<array<int,3>>a(n);
12
  {
13
    int _=0;
14
    for (auto&&[l,r,i]:a){
15
      cin>>l>>r;
16
      i=++_;
17
    }
18
  }
19
  ranges::sort(a);
20
  vector ans(n+1,0);
21
  priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>q;
22
  auto it=a.begin();
23
  up(i,1,n){
24
    while(it!=a.end() and (*it)[0]<=i){
25
      auto &&[l,r,p]=*it;
26
      // cout<<l<<" "<<r<<" "<<p<<endl;
27
      q.push({r,l,p});
28
      it++;
29
    }
30
    if (q.empty()){
31
      cout<<"-1\n";
32
      return;
33
    }
34
    auto [r,l,j]=q.top();
35
    q.pop();
36
    if (r<i){
37
      cout<<"-1\n";
38
      return;
39
    }
40
    ans[j]=i;
41
  }
42
  up(i,1,n) cout<<ans[i]<<" \n"[i==n];
43
}
44

45
int main(){
46
  ios::sync_with_stdio(0);
47
  cin.tie(0);
48
  cout.tie(0);
49
  int T=1;
50
  // cin>>T;
51
  while(T--)solve();
52
}

J 硝基甲苯之袭#

预处理每个数除 1 以外的约数。然后枚举每个 $a_i$ 的约数 $x$ ，如果 $\gcd(a_i,a_i\oplus x)=x$ ，那么 $a_i \oplus x$ 显然就是一个合法的 $a_j$ 。 $a_i$ 范围很小，使用 cnt 记录数据出现次数即可。

特别的，对于 $a_i \oplus a_j=\gcd(a_i,a_j)=1$ ，显然只有 $a_i = a_j +1$ 时才会出现。

1
#include<bits/stdc++.h>
2
#define up(i,x,y) for(int i=x;i<=y;i++)
3
#define down(i,x,y) for(int i=x;i>=y;i--)
4
#define elif else if
5
#define ll long long
6
using namespace std;
7

8
const int mx=200000;
9
vector<vector<int>>z(mx+5);
10

11
void solve(){
12
  int n;
13
  cin>>n;
14
  vector<int>cnt(mx+5);
15
  ll ans=0;
16
  for(int idx=0;idx<n;idx++){
17
    int i;
18
    cin>>i;
19
    cnt[i]++;
20
    if (cnt[i+1] and (i^(i+1))==1)ans+=cnt[i+1];
21
    if (i>1 and cnt[i-1] and (i^(i-1))==1)ans+=cnt[i-1];
22
    for (auto&&j:z[i]){
23
      if ((i^j)<=mx and gcd(i^j,i)==j)ans+=cnt[i^j];
24
    }
25
  }
26
  cout<<ans<<"\n";
27
}
28

29
int main(){
30
  ios::sync_with_stdio(0);
31
  cin.tie(0);
32
  cout.tie(0);
33
  up(i,2,mx){
34
    for (int j=i;j<=mx;j+=i){
35
      if (i^j<=mx) z[j].push_back(i);
36
    }
37
  }
38
  int T=1;
39
  while(T--)solve();
40
}

M 数值膨胀之美#

从最小的数开始 *2，直到所有数都被 *2。每次将区间扩展到当前最小数的位置。时间复杂度 $O(n\log n)$ 。

1
#include<bits/stdc++.h>
2
#define up(i,x,y) for(int i=x;i<=y;i++)
3
#define down(i,x,y) for(int i=x;i>=y;i--)
4
#define elif else if
5
#define ll long long
6
using namespace std;
7

8
void solve(){
9
  int n;
10
  cin>>n;
11
  vector<array<int,2>>a(n+2);
12
  a[n+1]={2000000000,0};
13
  vector<int>b(n+1);
14
  up(i,1,n){
15
    cin>>b[i];
16
    a[i]={b[i],i};
17
  }
18
  sort(a.begin()+1,a.end());
19
  int l=a[1][1],r=l;
20
  int mx=max(a[1][0]*2,a[n][0]);
21
  int res=mx-min(a[1][0]*2,a[2][0]);
22
  up(i,2,n){
23
    while(a[i][1]<l){
24
      l--;
25
      mx=max(mx,b[l]*2);
26
    }
27
    while(a[i][1]>r){
28
      r++;
29
      mx=max(mx,b[r]*2);
30
    }
31
    res=min(res,mx-min(a[1][0]*2,a[i+1][0]));
32
  }
33
  cout<<res;
34
}
35

36
int main(){
37
  ios::sync_with_stdio(0);
38
  cin.tie(0);
39
  cout.tie(0);
40
  int T=1;
41
  // cin>>T;
42
  while(T--)solve();
43
}

E 双生双宿之错#

这道题三分可以做，但作者的三分一直 80 分，不知道什么原因，非常可惜。

结论是，如果我们想要让整个数组变成同一个数的，同时代价最小，选中位数就行。

变成两个数时，排序，前后分别取中位数即可。代价是

\sum_{i=1}^{n}|a_i-a_{mid}|

两部分代价相加就是所求答案。

绝对值可以用前缀和 + 二分优化，比如你要求 $\sum_{i=l}^{r}|a_i-x|$ ，你可以

1
auto calc=[&](ll l,ll r,ll x)->ll{
2
  ll p=lower_bound(a.begin()+l,a.begin()+r+1,x)-a.begin();
3
  return x*(p-1-l+1)-(pre[p-1]-pre[l-1])+(suf[p]-suf[r+1])-x*(r-p+1);
4
};

这样时间复杂度就是 $O(\log n)$ ，但我看标程就是暴力直接求了，我也懒得重新写了。

~~哭死，我的版本反而只有 80 分。~~

1
#include<bits/stdc++.h>
2
#define up(i,x,y) for(int i=x;i<=y;i++)
3
#define down(i,x,y) for(int i=x;i>=y;i--)
4
#define elif else if
5
#define ll long long
6
using namespace std;
7

8
void solve(){
9
  int n;
10
  cin>>n;
11
  vector a(n+1,0);
12
  up(i,1,n) cin>>a[i];
13
  ranges::sort(a);
14
  int mid=n>>1;
15
  auto get=[&](int l,int r){
16
    ll res=0;
17
    up(i,1,mid) res+=abs(a[i]-l);
18
    up(i,mid+1,n) res+=abs(a[i]-r);
19
    return res;
20
  };
21
  auto f=[&](int x,int y){
22
    return a[x]!=a[y] ? get(a[x],a[y]) : min(get(a[x]-1,a[y]),get(a[x],a[y]+1));
23
  };
24

25
  int x=(mid+(mid&1))/2;
26
  int y=mid+x+((mid&1)^1);
27
  cout<<f(x,y)<<"\n";
28
}
29

30
int main(){
31
  ios::sync_with_stdio(0);
32
  cin.tie(0);
33
  cout.tie(0);
34
  int T=1;
35
  cin>>T;
36
  while(T--)solve();
37
}

C 兢兢业业之移#

其实是暴力模拟题，但作者的暴力思路有问题，没过。

暴力思路就是先把所有 1 往上推，再往左推，这样 1 聚集在左上角呈类似三角形。再把超出范围的 1 推到范围内。

怎么把 1 推到范围内？不难发现，最外面的 1 一定是上、左、下不能走（边缘和 1 视为不能走，11 交换没用），或者上、左不能走。那么当这个 1 的坐标在目标范围且满足上左不能走的条件的时候，我们判断走到目标位置了就行。显然，最初 $y > {n\over 2}$ 的 1 只需要往右、上走， $x > {n\over 2}$ 的 1 则往左、下走。不可能存在同时满足这两个条件的 1。