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)
解题代码
/* by yours.tools - online tools website : yours.tools/zh/guid.html */ #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
/* by yours.tools - online tools website : yours.tools/zh/guid.html */ #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)
5 1 2 1 3 1 4 4 54我们可以去分析一下二叉树的特点，是不是最多的节点数在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; }魔法人偶的十进制校准
3 1 5 2 3 5 71 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)
abca1因为限制只存在与相邻。我们就可以去考虑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)
2 5 1 2 4 3 5 2 1 20 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; }
