西南民族大学 2023 天梯自主训练 3
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; string a,b; int x,y; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); bool ok1=true,ok2=true; string s; getline(cin,s); for(int i=0;i<s.size();++i){ if(s[i]==' '){ b=s.substr(i+1);break; } else a+=s[i]; } for(int i=0;i<a.size();++i){ int t=a[i]-'0'; if(t>=0&&t<=9)x=x*10+t; else{ ok1=false;break; } } if(x<1||x>1000)ok1=false; //if(x< pow(10,a.size()-1))ok1=false; for(int i=0;i<b.size();++i){ int t=b[i]-'0'; if(t>=0&&t<=9)y=y*10+t; else { ok2=false;break; } } if(y<1||y>1000)ok2=false; //if(y<pow(10,b.size()-1))ok1=false; if(ok1)cout<<x<<' '; else cout<<"? "; cout<<"+ "; if(ok2)cout<<y<<' '; else cout<<"? "; cout<<"= "; if(ok1&&ok2)cout<<x+y; else cout<<"?"; return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; string s="I Love GPLT"; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); for(int i=0;i<s.size();++i)cout<<s[i]<<'\n'; return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; string s; bool st[10]; int a[10]; vector<int>x,ans; bool cmp(int aa,int bb){return aa>bb;} int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>s; for(int i=0;i<s.size();++i){ int t=s[i]-'0'; if(!st[t]){ x.push_back(t); st[t]=true; } } sort(x.begin(),x.end(),cmp); for(int i=0;i<x.size();++i){ a[x[i]]=i; } for(int i=0;i<s.size();++i){ int t=s[i]-'0'; ans.push_back(a[t]); } cout<<"int[] arr = new int[]{"; for(int i=0;i<x.size();++i){ cout<<x[i]; if(i!=x.size()-1)cout<<","; else cout<<"};\n"; } cout<<"int[] index = new int[]{"; for(int i=0;i<ans.size();++i){ cout<<ans[i]; if(i!=ans.size()-1)cout<<","; else cout<<"};"; } return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,m; bool P(int x){ if(x==1)return false; for(int i=2;i<=sqrt(x);++i){ if(x%i==0)return false; } return true; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; while(n--){ cin>>m; if(P(m))cout<<"Yes"; else cout<<"No"; if(n)cout<<'\n'; } return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int h; double w; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>h; w=(h-100)*0.9*2; cout<<fixed<<setprecision(1)<<w; return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; queue<PSI>all; stack<string>b,g; unordered_set<string>se; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n,op; string s; cin>>n; for(int i=0;i<n;++i){ cin>>op>>s; if(op==0)g.push(s); else b.push(s); all.push({s,op}); } while(all.size()){ auto t=all.front();all.pop(); if(se.count(t.first)==1)continue; se.insert(t.first); cout<<t.first<<' '; if(t.second==0){ while(se.count(b.top())==1)b.pop(); cout<<b.top(); se.insert(b.top()),b.pop(); } else{ while(se.count(g.top())==1)g.pop(); cout<<g.top(); se.insert(g.top()),g.pop(); } cout<<'\n'; } return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=0;i<n;++i){ int h;double w; cin>>h>>w; double a=(h-100)*0.9*2; if(abs(w-a)<a*0.1)cout<<"You are wan mei!\n"; else if(w>a)cout<<"You are tai pang le!\n"; else cout<<"You are tai shou le!\n"; } return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n; char c; string s,ans; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>c; getline(cin,s); getline(cin,s); for(int i=n-1,j=s.size()-1;i>=0;--i,--j){ if(j>=0)ans+=s[j]; else ans+=c; } std::reverse(ans.begin(), ans.end()); cout<<ans; return 0; }View Code
思路:用并查集或dfs重新求每次删除一个节点后的连通块个数,判断是否增加
#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,fa[N]; bool del[N]; struct E{ int a,b; }g[5005]; int find(int x){ if(x!=fa[x])fa[x]=find(fa[x]); return fa[x]; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=0;i<n;++i)fa[i]=i; for(int i=0;i<m;++i){ cin>>g[i].a>>g[i].b; int a=find(g[i].a),b=find(g[i].b); if(a!=b)fa[a]=b; } int pre=0; for(int i=0;i<n;++i){ if(fa[i]==i)pre++; } int k,last; cin>>k; for(int i=0,x;i<k;++i){ cin>>x; last=0; del[x]=true; for(int j=0;j<n;++j)fa[j]=j; for(int j=0;j<m;++j){ if(!del[g[j].a]&&!del[g[j].b]){ int a=find(g[j].a),b=find(g[j].b); if(a!=b)fa[a]=b; } } for(int j=0;j<n;++j)if(!del[j]&&fa[j]==j)last++; if(last>pre)cout<<"Red Alert: City "<<x<<" is lost!\n"; else cout<<"City "<<x<<" is lost.\n"; pre=last; if(i==n-1)cout<<"Game Over."; } return 0; }View Code
思路:每个队列里的数都是递减的,按顺序存,若没有队列可以插入则新增队列;暴力会t,可以将每个队列队头按从小到大排,二分查找即可
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n; vector<int>ve; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; for(int i=0,x;i<n;++i){ cin>>x; if(ve.empty()||ve[ve.size()-1]<x)ve.push_back(x); else { int mid= upper_bound(ve.begin(),ve.end(),x)-ve.begin(); ve[mid]=x; } } cout<<ve.size(); return 0; }View Code
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,k,m,a[10]; vector<double>ve; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>k>>m; for(int i=0;i<n;++i){ int s=0; for(int j=0;j<k;++j){ cin>>a[j];s+=a[j]; } sort(a,a+k); s-=a[0],s-=a[k-1]; ve.push_back(1.0*s/(k-2)); } sort(ve.begin(),ve.end()); for(int i=n-m;i<n;++i){ cout<<fixed<<setprecision(3)<<ve[i]; if(i!=n-1)cout<<' '; } return 0; }View Code
思路:往上找相同祖先即可,深度小于4则NO,深度大于等于4或无父母或同性直接YES
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; struct E{ int dad=-1,mom=-1; char sex='M'; }g[N]; int n,m; bool find(int a,int b,int cnt){ if(a==-1||b==-1)return true; if((g[a].dad!=-1&&g[a].dad==g[b].dad)||(g[a].mom!=-1&&g[a].mom==g[b].mom))return false; cnt++; if(cnt>=4)return true; return (find(g[a].dad,g[b].mom,cnt)&&find(g[a].mom,g[b].dad,cnt)&&find(g[a].dad,g[b].dad,cnt)&&find(g[a].mom,g[b].mom,cnt)); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; for(int i=0,id,a,b;i<n;++i){ char c; cin>>id>>g[id].sex>>g[id].dad>>g[id].mom; if(g[id].dad!=-1)g[g[id].dad].sex='M'; if(g[id].mom!=-1)g[g[id].mom].sex='F'; } cin>>m; for(int i=0,a,b;i<m;++i){ cin>>a>>b; if(g[a].sex==g[b].sex)cout<<"Never Mind\n"; else{ if(find(a,b,0))cout<<"Yes\n"; else cout<<"No\n"; } } return 0; }View Code
思路:按左子树大,右子树小存,存的最后一个数刚好为第n个则YES
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,a[N]; void add(int i,int x){ if(a[i]==-1){ a[i]=x;return ; } if(x>a[i])add(i*2,x); else add(i*2+1,x); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; memset(a,-1,sizeof a); for(int i=0,x;i<n;++i){ cin>>x; add(1,x); } int l=0,r=0; while(l<n){ while(a[r]==-1)r++; if(!l)cout<<a[r]; else cout<<" "<<a[r]; r++,l++; }cout<<"\n"; if(r==n+1)cout<<"YES"; else cout<<"NO"; return 0; }View Code
思路:哈希下每个点,dij的同时按最短路,经过最多个数,杀敌数排
#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,k,kil[N],dis[N],v[N],cnt[N],path[N],num[N]; string my,his; unordered_map<string,int>mp; unordered_map<int,string>pm; vector<PII>ve[N]; bool st[N]; void dij(int u){ memset(dis,0x3f,sizeof dis); priority_queue<PII,vector<PII>,greater<PII> >q; q.push({0,u}); dis[u]=0;path[u]=-1,num[u]=1,cnt[u]=1; while(q.size()){ auto t=q.top(); q.pop(); if(st[t.second])continue; st[t.second]=true; for(auto vv:ve[t.second]){ int v1=vv.first,w1=vv.second; if(st[v1])continue; if(dis[v1]>dis[t.second]+w1){ dis[v1]=dis[t.second]+w1; path[v1]=t.second; num[v1]=num[t.second]; cnt[v1]=cnt[t.second]+1; kil[v1]=kil[t.second]+v[v1]; q.push({dis[v1],v1}); } else if(dis[v1]==dis[t.second]+w1){ num[v1]+=num[t.second]; if(cnt[v1]<cnt[t.second]+1){ cnt[v1]=cnt[t.second]+1; path[v1]=t.second; kil[v1]=kil[t.second]+v[v1]; } else if(cnt[v1]==cnt[t.second]+1){ if(kil[v1]<kil[t.second]+v[v1]){ kil[v1]=kil[t.second]+v[v1]; path[v1]=t.second; } } } } } stack<int>stk; int p=mp[his]; while(p!=-1){ stk.push(p); p=path[p]; } while(stk.size()){ cout<<pm[stk.top()]; stk.pop(); if(stk.size())cout<<"->"; } cout<<'\n'; p=mp[his]; cout<<num[p]<<' '<<dis[p]<<' '<<kil[p]; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>k>>my>>his; mp[my]=0;pm[0]=my; for(int i=1;i<n;++i){ string s; cin>>s>>v[i]; mp[s]=i; pm[i]=s; } for(int i=0,x;i<k;++i){ string a,b; cin>>a>>b>>x; ve[mp[a]].push_back({mp[b],x}); ve[mp[b]].push_back({mp[a],x}); } dij(mp[my]); return 0; }View Code
标签:typedef,const,自主,int,cin,long,天梯,2023,tie From: https://www.cnblogs.com/bible-/p/17334737.html