寒假营第四场题解

2025牛客寒假算法基础集训营4

世界第一可爱的嘤嘤嘤的题解

Easy：E、I、K

Mid：B、C、D

Hard：A、F、J、L

AK：G、H

E Tokitsukaze and Dragon’s Breath

https://ac.nowcoder.com/acm/contest/95336/E

枚举、哈希

一个非常经典（很原）的题。

存储对角线有一个小技巧：

1） 从左上到右下的对角线满足 x+y都相等。

1） 从左下到右上的对角线满足 x−y 都相等。

不信的话你可以试一下。

因此我们可以将每一条对角线上所有的数字之和记录下来。

然后枚举每一个格子作为“龙之吐息”的中心位置。

中心位置所在的两条对角线上的数字之和减去中心的数字就是这在这个中心使用“龙之吐息”的收益。

枚举所有位置作为中心计算收益后取一个最大值即可。

时间复杂度)O(n×m×log(n×m)) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>v(n+1,vector<int>(m+1));
    map<int,int>mp1,mp2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>v[i][j];
            mp1[i+j]+=v[i][j];
            mp2[i-j]+=v[i][j];
        }
    }   
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int shu=mp1[i+j]+mp2[i-j]-v[i][j];
            ans=max(ans,shu);
        }
    }
    cout<<ans<<'\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

I Tokitsukaze and Pajama Party

https://ac.nowcoder.com/acm/contest/95336/I

枚举、前缀和

非常无趣的一个题，一个简单的知识点，缝合了一个长长的背景。

本质上等价于问字符串中有多少个 “ab” 子序列。

上述问题的做法是枚举每一个 ‘b’ ，看这个 ‘b’ 的前面有多少个 ‘a’ ，记录前面有多少个 ‘a’ 需要使用前缀和的思想。

我们把 “u” 作为 ‘a’ ， “uwawauwa” 看成一个整体作为 ‘b’ ，接下来就是看这个 ‘b’ 前面有多少个 ‘a’ 。

由于这里的 “*” 号至少需要占一个位置，因此我们需要看的是 ‘b’ 的前一个位置之前有多少个 ‘a’ 。

（但是正则表达式中 ‘*’ 应该是可以匹配 0 个字符的，匹配非 0 个字符要用 ‘+’ 才对）

时间复杂度 O(n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=" "+s+"kkkkkkkkkkk";
    int ans=0;
    int f=0;
    for(int i=1;i<=n;i++)
    {
        if(s.substr(i+1,8)=="uwawauwa")
        {
            ans+=f;
        }
        if(s[i]=='u')f++;
    }
    cout<<ans<<'\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

K Tokitsukaze and Shawarma

https://ac.nowcoder.com/acm/contest/95336/K

这一题就是直接模拟，没有难度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve(){
    int x,y,z,a,b,c;
    cin>>x>>y>>z>>a>>b>>c;
    int ans=max({x*a,y*b,z*c});
    cout<<ans<<'\n';    
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

B Tokitsukaze and Balance String (easy)

https://ac.nowcoder.com/acm/contest/95336/B

这个感觉就是分类讨论一下就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int cnt=0;
    for(auto ch:s)
    {
        if(ch=='?')cnt++;
    }
    if(n==1)
    {
        if(s[0]=='?')cout<<2<<'\n';
        else cout<<1<<'\n';
    }    
    else 
    {
        if(s[0]=='?'&&s[n-1]=='?')
        {
            cout<<pow(2,cnt-2)*2*n<<'\n';
        }
        else if(s[0]=='?'||s[n-1]=='?')
        {
            cout<<pow(2,cnt-1)*n<<'\n';
        }
        else 
        {
            if(s[0]==s[n-1])cout<<pow(2,cnt)*(n-2)<<'\n';
            else cout<<pow(2,cnt)*2<<'\n';
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

C Tokitsukaze and Balance String (hard)

https://ac.nowcoder.com/acm/contest/95336/C

这一题是上一题的hard版本，记得这种取模的一定要所有位置都记得取模，不然有的样例过不了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int mod=1e9+7;
ll power(ll x,ll y)
{
    ll ret=1;
    while(y)
    {
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ret;
}
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int cnt=0;
    for(auto ch:s)
    {
        if(ch=='?')cnt++;
    }
    if(n==1)
    {
        if(s[0]=='?')cout<<2<<'\n';
        else cout<<1<<'\n';
    }    
    else 
    {
        if(s[0]=='?'&&s[n-1]=='?')
        {
            cout<<((power(2,cnt-2)*2)%mod*n)%mod<<'\n';
        }
        else if(s[0]=='?'||s[n-1]=='?')
        {
            cout<<(power(2,cnt-1)*n)%mod<<'\n';
        }
        else 
        {
            if(s[0]==s[n-1])cout<<(power(2,cnt)*(n-2))%mod<<'\n';
            else cout<<(power(2,cnt)*2)%mod<<'\n';
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

D Tokitsukaze and Concatenate‌ Palindrome

https://ac.nowcoder.com/acm/contest/95336/D

1
2
3
4
5
6
7
```

## A Tokitsukaze and Absolute Expectation

[https://ac.nowcoder.com/acm/contest/95336/A](https://ac.nowcoder.com/acm/contest/95336/A)

```cpp

F Tokitsukaze and Kth Problem (easy)

https://ac.nowcoder.com/acm/contest/95336/F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
```

## J Tokitsukaze and Recall

[https://ac.nowcoder.com/acm/contest/95336/J](https://ac.nowcoder.com/acm/contest/95336/J)

**图论、并查集、BFS、贪心**

```cpp
#include <bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
// #define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<bool> vis(n + 1);
    // p数组存每一个联通块的从大到小排序s
    vector<vector<int>> p;
    // 对每一个联通块进行bfs并且填入数组s中之后进行排序
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
            continue;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        vector<int> s;
        while (q.size())
        {
            int t = q.front();
            q.pop();
            s.push_back(t);
            for (auto j : adj[t])
            {
                if (!vis[j])
                {
                    vis[j] = 1;
                    q.push(j);
                }
            }
        }
        ranges::sort(s);
        p.push_back(s);
    }
    // q是优先队列，存最先访问的几个节点，然后按照bfs进行搜索。
    priority_queue<int, vector<int>, greater<int>> q;
    set<int> s;
    for (int i = 1; i <= n; i++)
        s.insert(i);
    // 排序，先找连通块大的，然后同样大小的找最小节点最小的。
    sort(p.begin(), p.end(), [&](vector<int> &a, vector<int> &b)
         {
        if(a.size()!=b.size())return a.size()>b.size();
        return a[0]<b[0]; });
    // 优先将k分配给不同的连通块
    for (int i = 0; i < p.size() && k; i++)
    {
        q.push(p[i][0]);
        k--;
        s.erase(p[i][0]);
    }
    vector<int> ans;
    while (!q.empty())
    {
        int t = q.top();
        // 如果联通块还有剩余的话就将连通块分给s中的节点，将他们也添加到q优先队列	
        if (!s.empty() && *s.begin() < t && k)
        {
            k--;
            q.push(*s.begin());
            s.erase(s.begin());
            continue;
        }
        q.pop();
        ans.push_back(t);
        for (auto j : adj[t])
        {
            if (s.contains(j))
            {
                q.push(j);
                s.erase(j);
            }
        }
    }
    cout << ans.size() << '\n';
    for (auto x : ans)
        cout << x << " ";
    cout << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--)
    {
        solve();
    }

    return 0;
}

L Tokitsukaze and XOR-Triangle

https://ac.nowcoder.com/acm/contest/95336/L

1