西南民族大学 春季 2023 训练赛 8
思路:每行只算一个(*^*)
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int all,p,a; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); string b="chi1 huo3 guo1"; while(1){ string s; getline(cin,s); if(s==".")break; all++; int t; t=s.find(b); if(t!=-1){ if(a==0)p=all; a++; } } cout<<all<<'\n'; if(a==0)cout<<"-_-#"; else cout<<p<<' '<<a; return 0; }View Code
思路:
1.左子树 (*2),右子树 (*2+1),减去2^n即为结论数
2.记录当前节点的叶子节点数为k,若是'y',ans不变,若是'n',ans加上k/2 (看图即可理解)
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,m; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; int k=pow(2,n); for(int i=0;i<m;++i){ int zi=k; string s; cin>>s; int ans=1; for(int j=0;j<s.size();++j){ if(s[j]=='n')ans+=zi/2; zi/=2; } cout<<ans<<'\n'; } return 0; }View Code 1
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,m; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; int k=pow(2,n); for(int i=0;i<m;++i){ int a=1; string s; cin>>s; for(int j=0;j<s.size();++j){ a*=2; if(s[j]=='n')a+=1; } cout<<a-k+1<<'\n'; } return 0; }View Code 2
思路:模拟...
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int D,P; unordered_map<string,int>pre,st; struct E{ string na,id,t; int p; bool operator<(const E&e)const{ if(t!=e.t) return t<e.t; return p<e.p; } }; struct EE{ string na,id; }; vector<EE>ans1,ans2; bool check(string s){ for(int i=0;i<s.size();++i){ if(s[i]<'0'||s[i]>'9')return false; } return true; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>D>>P; for(int i=1,T,S;i<=D;++i){ cin>>T>>S; vector<E>ve; for(int j=0;j<T;++j){ string s1,s2,t; int op; cin>>s1>>s2>>op>>t; E a={s1,s2,t,j}; if(s2.size()==18&&check(s2)){ ve.push_back(a); if(op==1&&!st[s1]){ ans2.push_back({s1,s2}); st[s1]=1; } } } sort(ve.begin(),ve.end()); for(int j=0;j<ve.size();++j){ if(i>pre[ve[j].na]&&S){ ans1.push_back({ve[j].na,ve[j].id}); pre[ve[j].na]=i+P;S--; } } } for(auto t:ans1){ cout<<t.na<<' '<<t.id<<'\n'; } for(auto t:ans2){ cout<<t.na<<' '<<t.id<<'\n'; } return 0; }View Code
思路:dfs根据后序遍历的顺序对应出层序的顺序
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,int>PLI; const int N=1e5+5,M=1e6+5,Mod=1e6; const int INF=0x3f3f3f3f3f3f3f3f; const double eps=1e-8; int n; vector<int>post,a,b; void dfs(int u){ if(u*2<=n)dfs(u*2); if(u*2+1<=n)dfs(u*2+1); a.push_back(u); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; post=vector<int>(n); b=vector<int>(n+1); for(int i=0;i<n;++i)cin>>post[i]; dfs(1); for(int i=0;i<n;++i){ b[a[i]]=post[i]; } for(int i=1;i<=n;++i){ cout<<b[i]; if(i!=n)cout<<" "; } return 0; }View Code
思路:dfs求所有点到终点的路径条数,若有节点已遍历但无路径数则NO
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,int>PLI; const int N=5e2+5,M=1e6+5,Mod=1e6; const int INF=0x3f3f3f3f; const double eps=1e-8; int n,m,path[N]; vector<int>ve[N]; bool vis[N]; int dfs(int x){ vis[x]=true; if(path[x])return path[x]; for(auto v:ve[x]){ path[x]+=dfs(v); } return path[x]; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=0,a,b;i<m;++i){ cin>>a>>b; ve[a].push_back(b); } int x,y; cin>>x>>y; path[y]=1; int cnt=dfs(x); bool ok=true; for(int i=1;i<=n;++i){ if(vis[i]&&!path[i]){ ok=false;break; } } cout<<cnt<<' '; if(ok)cout<<"Yes"; else cout<<"No"; return 0; }View Code
标签:typedef,const,int,cin,春季,训练赛,long,2023,tie From: https://www.cnblogs.com/bible-/p/17330429.html