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

A 一起奏响历史之音！#

签到，判断 a>=1 and a<=6 and a!=4 即可。

B 能去你家蹭口饭吃吗#

还是签到，答案为 $sorted(a)_{\lfloor{n\over2}\rfloor}-1$ 。

D 字符串里串#

正反跑一边，只有当前字母 $s_i$ / $s_{n-i}$ 在后面 / 前面还有出现，答案就可以更新为 $\max(i,ans)$ 。

F 一起找神秘的数！#

首先理解

a+b=2(a\And b)+(a \oplus b)

$2(a\And b)$ 是只进位二进制加法， $a \oplus b$ 是不进位二进制加法。

将上面公式代入题目，得到

a|b=a\And b

显然解只有 $a=b$ 。答案为 $r-l+1$ 。

G 一起铸最好的剑！#

找到距离 $n$ 最小的两个 $m^x$ ，使之更接近的 $x$ 就是答案。

罚时吃满，这题要求一定要启动炉子，答案最小为 1。所以特判 n==1 or m==1 : ans=1

H 一起画很大的圆！#

外接圆半径

R={abc \over4S}

在长边的最左 / 右选一个长度为 1 的线段为三角形一边，剩下部分与短边与长边相邻的长度 1 线段，构成的斜边为三角形第二条边。至此三角形已经确定。

横着可以找到一个答案是 $(a,d−1),(b,d),(b−1,d)$ ，但如果 $d−c>b−a$ 的话，就应该竖着找。

1
void solve(){
2
  int a,b,c,d;
3
  cin>>a>>b>>c>>d;
4
  if (b-a>d-c){
5
    cout<<a<<" "<<d-1<<"\n";
6
    cout<<b-1<<" "<<d<<"\n";
7
    cout<<b<<" "<<d<<"\n";
8
  }else{
9
    cout<<a+1<<" "<<c<<"\n";
10
    cout<<a<<" "<<d-1<<"\n";
11
    cout<<a<<" "<<d<<"\n";
12
  }
13
}

J 数据时间？#

Python 秒

1
from collections import defaultdict
2
from datetime import datetime
3
strptime=datetime.strptime
4

5
ri=lambda : int(input())
6
rl=lambda : list(map(int,input().split()))
7

8
def solve():
9
  n,h,m=rl()
10
  res=[set() for i in range(3)]
11
  for i in range(n):
12
    a=input().split()
13
    d=strptime(a[1]+" "+a[2],f"%Y-%m-%d %H:%M:%S")
14
    if d.year==h and d.month==m:
15
      if d.hour>=7 and d.hour<=8 or d.hour==9 and d.minute==0 and d.second==0:
16
        res[0].add(a[0])
17
      elif d.hour>=18 and d.hour<=19 or d.hour==20 and d.minute==0 and d.second==0:
18
        res[0].add(a[0])
19
      elif d.hour>=11 and d.hour<=12 or d.hour==13 and d.minute==0 and d.second==0:
20
        res[1].add(a[0])
21
      elif d.hour>=22 or d.hour==0 or d.hour==1 and d.minute==0 and d.second==0:
22
        res[2].add(a[0])
23
  print(len(res[0]),len(res[1]),len(res[2]))

K 可以分开吗？#

DFS 板子题之一，遍历所有连通块，找最少的相邻灰块。

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
vector<vector<int>>vis;
8
vector<array<int,2>>path;
9
vector<string>tu;
10
vector<array<int,2>>dt{{-1,0},{0,-1},{0,1},{1,0}};
11
int n,m;
12
void dfs(int y,int x){
13
  path.push_back({y,x});
14
  vis[y][x]=1;
15
  for (auto&&[dy,dx]:dt){
16
    int gy=y+dy,gx=x+dx;
17
    if (gy>n or gy<1 or gx>m or gx<1 or tu[gy][gx]=='0' or vis[gy][gx]) continue;
18
    dfs(gy,gx);
19
  }
20
}
21

22
void solve(){
23
  cin>>n>>m;
24
  vis=vector(n+2,vector(m+2,0));
25
  tu=vector<string>(n+1);
26
  int mxc=INT_MAX;
27
  up(i,1,n) {
28
    cin>>tu[i];
29
    tu[i]="^"+tu[i];
30
  }
31
  up(i,1,n){
32
    up(j,1,m){
33
      if (not vis[i][j] and tu[i][j]=='1'){
34
        path.resize(0);
35
        dfs(i,j);
36
        int cnt=0,flg=i*m+j;
37
        for (auto&&[y,x]:path){
38
          for (auto&&[dy,dx]:dt){
39
            int gy=y+dy,gx=x+dx;
40
            if (gy>n or gy<1 or gx>m or gx<1 or tu[gy][gx]=='1' or vis[gy][gx]==flg) continue;
41
            vis[gy][gx]=flg;
42
            cnt++;
43
          }
44
                }
45
        mxc=min(mxc,cnt);
46
      }
47
    }
48
  }
49
  cout<<mxc<<"\n";
50
}
51

52
int main(){
53
  ios::sync_with_stdio(0);
54
  cin.tie(0);
55
  cout.tie(0);
56
  int T=1;
57
  // cin>>T;
58
  while(T--)solve();
59
}

C 字符串外串#

构造题。

形如 "cbaaaabc" 的构造方法，构造一个长度为 $n$ 的字符串，最后的 $m$ 应该等于 $n$ 减去最后 "abc..z" 的长度。显然 n==m 时无解，n-m > 26 or n-m > m+1 时这种方法无解。

形如 "cbadefgabc" 的构造方法，构造一个长度为 $n$ 的字符串，最后的 $m$ 应该等于最后 "abc..z" 的长度。显然 n-2*m>26-m 的时候这种方法无解。

相结合得到本题答案。

1
#include<bits/stdc++.h>
2
#define up(i,x,y) for(auto i=x;i<=y;i++)
3
#define down(i,x,y) for(auto i=x;i>=y;i--)
4
#define elif else if
5
#define ll long long
6
using namespace std;
7
void solve(){
8
  int n,m;
9
  cin>>n>>m;
10
  if (n<=m or n-m>26 or (n-m>m+1)){
11
    if (n-2*m>=0 and n-2*m<=26-m){
12
      cout<<"YES\n";
13
      up(i,'a',char('a'+m-1)){
14
        cout<<i;
15
      }
16
      up(i,char('a'+m),char('a'+m+(n-m*2)-1)) cout<<i;
17
      down(i,char('a'+m-1),'a'){
18
        cout<<i;
19
      }cout<<"\n";
20
      return;
21
    }
22
    cout<<"NO\n";
23
    return;
24
  }
25
  cout<<"YES\n";
26
  {
27
    int gap=n-m;
28
    char cur='a'+gap-1;
29
    while(cur>='a'){
30
      cout<<cur;
31
      cur--;
32
    }
33
    up(i,1,n-gap*2){
34
      cout<<"a";
35
    }
36
    up(i,int(n-m==m+1),gap-1) cout<<char('a'+i);
37
  }
38
  cout<<"\n";
39
}
40

41
int main(){
42
  ios::sync_with_stdio(0);
43
  cin.tie(0);
44
  cout.tie(0);
45
  int T=1;
46
  cin>>T;
47
  while(T--)solve();
48
}

E 一起走很长的路！#

蒟蒻作者的解法（比 std 快！）#

贪心的想，增加重量一定不会比减少重量更劣，把重量增加给 $a_l$ 一定不会比后面更劣。

设 $cur$ 为当前增加的重量。

当我们确定 $a_{i}$ （ $i\not=l$ ）可行，想要确定接下来的点可不可行，由于 $a_i$ 可行的条件是 $pre_{i-1}-pre_{l-1}+cur\ge a_i$ ，我们可以确定现在的和一定 $\ge 2a_i$ ，也就是说我们每次只需要判断下一个大于 $2a_i$ 的 $a_j$ 符不符合条件就行，相当于会一直倍增判断值。显然到一定值以后，后面就不会有更大的值，查询就结束了。这样每次查询时间复杂度就是 $O(\log V)$ ，题中 $V=10^9$ ，可以通过这道题。

初始时 $a_l$ 显然一定可以，设置要判断的点 $p=l+1$ ，运行到 $p>r$ 结束。

怎么找到下一个大于 $2a_i$ 的值？预处理，使用离散化 + 树状数组，倒着跑一遍，记录下一个大于 $a_i$ 的值的下标。预处理时间复杂度 $O(n\log n)$ （我的代码是大于等于，导致查询常数稍微大一点）。

整体复杂度 $O(n\log n+q\log V)$ 。

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

8
ll nn;ll n,q;
9
vector<ll>t;
10

11
void assign(ll p,ll x){
12
  while(p){
13
    t[p]=min(t[p],x);
14
    p-=(p&(-p));
15
  }
16
}
17
ll query(ll p){
18
  ll res=n+1;
19
  while(p<=nn){
20
    res=min(res,t[p]);
21
    p+=(p&(-p));
22
  }
23
  return res;
24
}
25

26
void solve(){
27
  cin>>n>>q;
28
  vector<ll>a(n+1),pre(n+1);
29
  pre[0]=0;
30
  vector<ll>nxt(n+1,n+1);
31
  vector<array<ll,2>>b(n+1);
32
  up(i,1,n){
33
    cin>>a[i];
34
    pre[i]=pre[i-1]+a[i];
35
    b[i]={a[i],i};
36
  }
37
  sort(b.begin(),b.end());
38
  vector<ll>rev(1,0);
39
  vector<ll>get(n+1);
40
  {
41
    ll p=0,last=0;
42
    for (auto&&[x,i]:b){
43
      if (x!=last){
44
        last=x;
45
        p++;
46
        rev.push_back(x);
47
      }
48
      get[i]=p;
49
    }nn=p;
50
  }
51
  t=vector(nn+1,n+1);
52
  down(i,n,1){
53
    int pos=lower_bound(rev.begin(),rev.end(),a[i]*2)-rev.begin();
54
    nxt[i]=query(pos);
55
    assign(get[i],i);
56
  }
57
  while(q--){
58
    ll u,v;
59
    cin>>u>>v;
60
    if (u==v){
61
      cout<<"0\n";
62
      continue;
63
    }
64
    ll res=0;
65
    ll p=u+1;
66
    while(p<=v){
67
      if (a[p]>pre[p-1]-pre[u-1]+res){
68
        res+=a[p]-(pre[p-1]-pre[u-1]+res);
69
      }
70
      p=nxt[p];
71
    }
72
    cout<<res<<"\n";
73
  }
74

75
}
76

77
int main(){
78
  ios::sync_with_stdio(0);
79
  cin.tie(0);
80
  cout.tie(0);
81
  int T=1;
82
  // cin>>T;
83
  while(T--)solve();
84
}

标程#

林林实测标程思维的线段树写法比蒟蒻作者写法慢 6 倍不到。标程 ST 表作者实测也是慢 6 倍左右。

我们在上面说过，贪心的想，增加重量一定不会比减少重量更劣，把重量增加给 $a_l$ 一定不会比后面更劣。

显然，答案就是

\max_{i=l+1}^{r}(a_i-(pre_{i-1}-pre_{l-1}))

如果暴力求 $\max$ ，时间复杂度就是 $O(n)$ 。

我们发现（作者考试时没发现 qwq），对于每次查询， $pre_{l-1}$ 是固定的，所以我们求的其实是

\max_{i=l+1}^{r}(a_i-pre_{i-1})+pre_{l-1}

使用 ST 表等处理 RMQ 即可。

作者还没写，先用王嘤嘤的代码顶上。

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
template <typename T>
6
class ST{
7
public:
8
    const int n;
9
    vector<vector<T>> st;
10
    ST(int n = 0, vector<T> &a = {}) : n(n){
11
        st = vector(n + 1, vector<T>(22 + 1));
12
        build(n, a);
13
    }
14

15
    inline T get(const T &x, const T &y){
16
        return max(x, y);
17
    }
18

19
    void build(int n, vector<T> &a){
20
        for(int i = 1; i <= n; i++){
21
            st[i][0] = a[i];
22
        }
23
        for(int j = 1, t = 2; t <= n; j++, t <<= 1){
24
            for(int i = 1; i <= n; i++){
25
                if(i + t - 1 > n) break;
26
                st[i][j] = get(st[i][j - 1], st[i + (t >> 1)][j - 1]);
27
            }
28
        }
29
    }
30

31
    inline T find(int l, int r){
32
        int t = log(r - l + 1) / log(2);
33
        return get(st[l][t], st[r - (1 << t) + 1][t]);
34
    }
35
};
36

37
int main(){
38
    int n, q;
39
    cin >> n >> q;
40
    vector f(n + 1, 0ll), d = f;
41
    for(int i = 1; i <= n; i++){
42
        int x;
43
        cin >> x;
44
        f[i] = f[i - 1] + x;
45
        d[i] = x - f[i - 1];
46
    }
47
    ST<long long> st(n, d);
48
    while(q--){
49
        int l, r;
50
        cin >> l >> r;
51
        if(l == r){
52
            cout << 0 << endl;
53
            continue;
54
        }
55
        auto ma = st.find(l + 1, r);
56
        auto ans = max(ma + f[l - 1], 0ll);
57
        cout << ans << endl;
58
    }
59
}