• 日期: 2026-02-09
  • 标签: 程序员

C++小白训练第十三天

以下为牛客挑战

今日收获

 vector>v;用于存储坐标，如果坐标：
 方式：v.push_back({i,j}),v.emplace_back(i,j);
 
 v.push_back(make_pair(i, j));

dp联想的又一个条件，就是因为限制只存在与相邻，那就和后面没有关系，所以考虑dp


理解了置换环：n-环数等于操作数。

牛客周赛 Round 130

红美铃的访客登记

A-红美铃的访客登记_牛客周赛 Round 130 (nowcoder.com)

image-20260209082136953

解题代码

#include
#define int long long
#define lll __uint128_t
#define PII pair
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];

signed main(){

	std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    int count=0;
    for(int i=0;i

爱丽丝的魔力零件分类

B-爱丽丝的魔力零件分类_牛客周赛 Round 130 (nowcoder.com)

image-20260209084218695

3
5
.....
.....
.***.
..*..
.....
5
.....
..*..
..*..
.**..
.....
6
......
..*...
.**...
..*...
......
......

T
L
T

题解

解题代码

可以先把这些为*的点先存起来，然后去判断他们的度数双重循环，来判断，当我们发现最多度数为3的时候就就是t，其他的就不是t，是l

#include
#define int long long
#define lll __uint128_t
#define PII pair
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){
    int n;
    cin>>n;
    vector>v;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char m;
            cin>>m;
            if(m=='*'){
                v.emplace_back(i,j);
            }
        }
    }
    int mx=0;
    for(auto [x,y]:v){
        int degree=0;
        for(auto [nx,ny]:v){
            if(abs(x-nx)+abs(y-ny)==1){
                degree++;
            }
        }
        mx=max(degree,mx);
    }
    if(mx==3){
        cout<<"T"<

博丽大结界的稳定轴心

C-博丽大结界的稳定轴心_牛客周赛 Round 130 (nowcoder.com)

image-20260209090135699

5
1 2
1 3
1 4
4 5

4

我们可以去分析一下二叉树的特点，是不是最多的节点数在3个以下，且这个3个的节点不会作为轴心点。

两个的和一个的都可以作为轴心点。

所有我们可以去先判断到底哪个最大的点数有多大。大于3就直接是零，小于的3就可以作为轴心点。

解题代码

#include
#define int long long
#define lll __uint128_t
#define PII pair
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];

signed main(){

	std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector>g(n+1);
    for(int i=1;i>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int mx=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,(int)g[i].size());
    }
    if(mx<=3){
        for(int i=1;i<=n;i++){
            if(g[i].size()<=2){
                ans++;
            }
        }
    }
    cout<

魔法人偶的十进制校准

image-20260209094949846

3
1 5
2 3
5 7

1 2
1 3
3 7

首先我们通过打标确定一下规律。

for(double y=2;y<=1000;y++){
	cout<

image-20260209095354057

可以发现特殊的

1/9----》得到这个。0.1111111，这个我们就可以去构造一下了，但是，b/9

然后特判别的，应为没有9/9，所以我们看到0.9090...
我们可以通过奇偶代换×一个10就可以了，我们直接9得到这个数.
然后特判一些0，和可以被3，6的情况就行了

解题代码

#include
#define int long long
#define lll __uint128_t
#define PII pair
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;

void solve(){
    int a,b;
    cin>>a>>b;
    if(b==0){
        if(a==1){
            cout<<1<<" "<<1000<

爱丽丝的人偶圆舞曲

E-爱丽丝的人偶圆舞曲_牛客周赛 Round 130 (nowcoder.com)

image-20260209112816198

abca

1

因为限制只存在与相邻。我们就可以去考虑dp的做法

这个是一个线性dp的题目，我们可以定义一个

因为d没有确认，所以我们去枚举d

f[i][j]--->表示前i个位置均合法，且si=j的最小次数

你们转移就是
min（f[i-1][(j-d+26)%26],f[(i+d)%26]）+这个数到底是不是等于j，不等于就要用一次，最后再算出最小值。

解题代码

#include
#define int long long
#define lll __uint128_t
#define PII pair
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];

signed main(){

	std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;

    int n=s.size();
    s=" "+s;

    //dp初始化。
    int mx=2e8;
    for(int d=0;d<=25;d++){
        vector>f(n+1,vector(26,2e8));
        for(int j=0;j<=25;j++){
            if(j==s[1]-'a'){
                f[1][j]=0;
            }else{
                f[1][j]=1;
            }
        }
        for(int i=2;i<=n;i++){
            for(int j=0;j<=25;j++){
                f[i][j]=min(f[i-1][(j-d+26)%26],f[i-1][(j+d)%26])+(j!=s[i]-'a');
            }
        }

        for(int i=0;i<=25;i++){
            mx=min(mx,f[n][i]);
        }

    }
    cout<

红魔馆的微瑕序位

F-红魔馆的微瑕序位_牛客周赛 Round 130 (nowcoder.com)

image-20260209120106423

2
5
1 2 4 3 5
2
1 2

0
1

本题考的一个经典置换环

如果一个1-n的排列，要交换几次才能使得它是一个排列。
结论是
n-环的个数，相当于拆环。

image-20260209120521887

如图是4元环

我们邀得到2，肯定得一个两个相邻的元素之间没有去交换

1 2 4 3 5

那我们先把交换的次数算出来，再考虑原来到底存不存在相邻的环。

解题代码

#include
#define int long long
#define lll __uint128_t
#define PII pair
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){
    int n;
    cin>>n;
    vectorv(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int loop=0;
    for(int i=1;i<=n;i++){
        if(v[i])continue;
        int j=i;
        loop++;
        while (!v[j]){
            v[j]=loop;
            j=a[j];
        }
    }
    int ans=n-loop+1;
    for(int i=2;i<=n;i++){//判断是不是相邻的环
        if(v[i-1]==v[i]){
            ans-=2;
            break;
        }
    }
    cout<
"

原文地址: https://www.cveoy.top/t/topic/qFVt 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录