西南民族大学 春季 2023 训练赛 8
思路：每行只算一个（*^*）
#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 (看图即可理解)
#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
#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
思路：模拟...
#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根据后序遍历的顺序对应出层序的顺序
#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
#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