牛客周赛Round 130

牛客周赛Round 130

Lionlnuc
Lionlnuc Lv4
  2026-02-09 2026-02-09 创建   2026-02-09 2026-02-09 更新      

比赛链接：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A 红美铃的访客登记

思路：
去除前导零，拿 flag 标注一下是否可以正常输出，避免输出前导零。
代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void solve()
{
    string s;
    cin>>s;
    bool flag=false;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!='0')flag=true;
        if(flag)cout<<s[i];
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

B 爱丽丝的魔力零件分类

思路：
找到 L 和 T 最大的区别是 L 最多有 2 个*相连，T 最多有 3 个，所以遍历每个*上下左右，如果有大于三的，flag 为 true。
代码： 

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void solve()
{
    int n;
    cin>>n;
    vector<vector<char>> a(n,vector<char>(n));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>a[i][j];
        }
    }
    bool flag=false;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]=='*'){
                int cnt=0;
                for(int d=0;d<4;d++)
                {
                    int x=i+dx[d];
                    int y=j+dy[d];
                    if(x>=0&&x<n&&y>=0&&y<n)
                    {
                        if(a[x][y] == '*')
                            cnt++;
                    }
                    if(cnt>=3)flag=true;
                }
            }
        }
    }
    if(flag)cout<<"T"<<endl;
    else cout<<"L"<<endl;
}
signed main(){
	IOS
	int t;
	cin>>t;
	//int t=1;
	while(t--)
	{
		solve();
	}
}

C 博丽大结界的稳定轴心

思路：
这里统计下每个节点所连接的节点数量，大于 3 时无法成为二叉树（二叉树中，每个节点最多有 2 个子节点，这样的话不合法）。
代码： 

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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
const int N=1e5+5;
int d[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        d[u]++;
        d[v]++;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]<=2)cnt++;
        if(d[i]>3){
            cout<<"0";
            return;
        }
    }
    cout<<cnt;
}
signed main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
}

D 魔法人偶的十进制校准

思路：
构造吧，构造一个满足条件的无限循环小数。可以发现 1~8 都是可以通过 来构造的。对于 0，如果 a=1 可以用 ，其他的可以用 。对于 9，可以分奇偶性，因为 ，。
需要注意的是 3，6 和 9 不互质，换成 和 就可以了。
代码： 

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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
const int N=1e5+5;
int d[N];
void solve()
{
    int a,b;
    cin>>a>>b;
    if(b>0&&b<9)
    {
        if(b==3)cout<<"1 3";
        else if(b==6)cout<<"2 3";
        else cout<<b<<" 9";
    }
    else if(b==0){
        if(a==1)cout<<"1 100";
        else cout<<"1 10";
    }else {
        if(a%2)cout<<"10 11";
        else cout<<"1 11";
    }
    cout<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

E 爱丽丝的人偶圆舞曲

思路：
动态规划，枚举步长，用 dp[i][j] 表示第 i 个字符改为 j 时，前 i 个字符的最小修改次数。
转移时，从两个可能的“前驱状态”中选择修改次数最少的那个。
状态转移方程为：
需要修改不需要修改
代码： 

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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
void solve()
{
    string s;
    cin>>s;
    int n=s.size();
    s=' '+s;
    int ans=1e8;
    for(int d=0;d<26;d++)
    {
        vector<vector<int>> dp(n+1,vector<int>(26));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<26;j++)
            {
                if(j==s[i]-'a')dp[i][j]=min(dp[i-1][(j-d+26)%26],dp[i-1][(j+d+26)%26]);
                else dp[i][j]=min(dp[i-1][(j-d+26)%26],dp[i-1][(j+d+26)%26])+1;
            }
        }
        ans=min(ans,*min_element(dp[n].begin()+1,dp[n].end()));
    }
    cout<<ans;
}
signed main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
}

F 红魔馆的微瑕序位

思路：
先来了解一下置换环：
置换环是用来求解数组排序元素间所需最小交换次数这类问题。
置换环将每个元素指向其排序后应在的位置，最终首位相连形成一个环（若数字在最终位置，则其自身成环）。所以每个环的最小交换次数为 环上元素数量。
把所有环的交换次数加起来，得到 最小交换次数置换环数环上元素数数组元素个数环数。
要让最终的混乱度为 2，这意味着必然是相差为 1​ 的两个元素交换位置。所以如果有两个相邻的数且在同一个置换环里则说明减少一次操作直接得到符合题意的数组；否则还要在进行一次操作才能得到符合题意的数组。
代码： 

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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
const int N=2e5+5;
int a[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int cnt=0;
    vector<int> id(n+1);
    for(int i=1;i<=n;i++)
    {
        if(!id[i]){
            cnt++;
            int cur=i;
            while(!id[cur])
            {
                id[cur]=cnt;
                cur=a[cur];
            }
        }
    }
    int ans=-1;
    for(int i=1;i<n;i++)
    {
        if(id[i]==id[i+1])
        {
            ans=1;
            break;
        }
    }
    cout<<n-cnt-ans<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

有空可以找两道题练练。

  • 标题: 牛客周赛Round 130
  • 作者: Lionlnuc
  • 创建于 : 2026-02-09 00:00:00
  • 更新于 : 2026-02-09 00:00:00
  • 链接: https://lionlnuc.github.io/2026/02/09/牛客周赛Round 130/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
牛客周赛Round 130
  1. A 红美铃的访客登记
  2. B 爱丽丝的魔力零件分类
  3. C 博丽大结界的稳定轴心
  4. D 魔法人偶的十进制校准
  5. E 爱丽丝的人偶圆舞曲
  6. F 红魔馆的微瑕序位