当前位置：首页 > news >正文

C++小白训练第十三天

news 2026/3/26 17:58:54

C++小白训练第十三天

以下为牛客挑战

今日收获

 vector<pair<int,int>>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)

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#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<s.size();i++){if(s[i]!='0'){count=i;break;}}for(int i=count;i<s.size();i++){cout<<s[i];}return 0;
}

爱丽丝的魔力零件分类

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

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

T
L
T

题解

解题代码

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

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#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<pair<int,int>>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"<<endl;}else{cout<<"L"<<endl;}};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

博丽大结界的稳定轴心

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

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

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

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

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#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<vector<int>>g(n+1);for(int i=1;i<n;i++){int u,v;cin>>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<<ans<<endl;return 0;
}

魔法人偶的十进制校准

1 2
1 3
3 7

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

for(double y=2;y<=1000;y++){cout<<fixed<<setprecision(10)<<(1.0/y)<<endl;
}

可以发现特殊的

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

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#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<<endl;}else{cout<<1<<" "<<2<<endl;}return;}else if(b==9){if(a%2){cout<<10<<" "<<11<<endl;}else{cout<<1<<" "<<11<<endl;}return;}if(b==3){cout<<1<<" "<<3<<endl;return;}if(b==6){cout<<2<<" "<<3<<endl;return;}cout<<b<<" "<<9<<endl;
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

爱丽丝的人偶圆舞曲

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

abca

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

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

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

f[i][j]--->表示前i个位置均合法，且si=j的最小次数你们转移就是
min（f[i-1][(j-d+26)%26],f[(i+d)%26]）+这个数到底是不是等于j，不等于就要用一次，最后再算出最小值。

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#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<vector<int>>f(n+1,vector<int>(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<<mx<<endl;return 0;
}

红魔馆的微瑕序位

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

0
1

本题考的一个经典置换环

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

如图是4元环

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

1 2 4 3 5

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

解题代码

#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#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<int>v(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<<ans<<endl;
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}

查看全文

http://www.jsqmd.com/news/360955/