100% 100% 64% 100% 100%
第一题
#include<iostream> #include<vector> #include<algorithm> using namespace std; int N, K; int main(){ int T ; cin>>T; while(T--){ cin>>N >> K; vector<int> data(N); for(int i=0;i<N;i++) cin >> data[i]; sort(data.begin(), data.end()); int ans; if(K>N){ cout<< "NO" <<endl; continue; } if(K==0) ans = 1; else ans = data[K-1] + 1; if(ans < 1 || ans > N){ cout<<"NO"<<endl; continue; } if(K<N && data[K-1]==data[K]){ cout<< "NO" <<endl; continue; } cout<<"YES"<<endl; cout<<ans<<endl; } }第二题
#include<iostream> #include<vector> using namespace std; int main(){ string str; getline(cin,str); string ret; for(int i=0 ; i<str.size() ;i++){ if(str[i] == ' ') continue; else{ ret+=str[i]; int tmp = i+1; while( tmp <str.size() && (str[tmp] == str[i] || str[tmp] == ' ') ) tmp++; i = tmp-1; } } cout<<ret<<endl; return 0; }第三题
#include<iostream> #include<vector> #include<set> using namespace std; int main(){ int N; cin>>N; vector<int> data(N); for(int i=0;i<N;i++) cin>>data[i]; set<int> s; int ans = 0; for(int i=0;i<N;i++){ auto it = s.lower_bound(data[i]); if(it != s.begin()){ ans += (*(--it) * (i+1)); } s.insert(data[i]); } cout<< ans <<endl; return 0; }第四题
#include<iostream> #include<vector> #include<algorithm> using namespace std; int getIndex(vector<int>& tree , int num){ int l = 0 , r = tree.size() -1; while(l<r){ int mid = (l+r)>>1; if(tree[mid] == num) return mid; if(tree[mid] > num) r = mid; else l = mid + 1; } return l; } int findroot(vector<int> & tree , int x){ if(tree[x] != -1){ tree[x] = findroot(tree,tree[x]); return tree[x]; }else return x; } int main(){ int N; cin>>N; vector<int> data(N); for(int i=0;i<N;i++) cin>>data[i]; vector<int> tmp(data); sort(tmp.begin(),tmp.end()); tmp.erase( unique(tmp.begin(),tmp.end()) , tmp.end()); vector<int> tree(tmp.size(),-1); int ans = 0; for(int i=0;i<N/2 ;i++){ if(data[i] != data[i+N/2]){ int x = getIndex(tmp,data[i]) , y = getIndex(tmp,data[i+N/2]); int xroot = findroot(tree,x) , yroot = findroot(tree,y); if(xroot!=yroot){ tree[xroot] = yroot; ans++; } } } cout<< ans <<endl; return 0; }第五题
#include<iostream> #include<vector> #include<stack> using namespace std; typedef struct node{ struct node* left; struct node* right; int val; node():left(nullptr) , right(nullptr) ,val(0){} node(int v):left(nullptr) , right(nullptr) ,val(v){} }Node; vector<Node*> Tree; void createTree(vector<pair<int,int>>& data , Node* root){ Tree[root->val] = root; int l = data[root->val].first , r = data[root->val].second; if(l){ root->left = new Node(l); createTree(data,root->left); } if(r){ root->right = new Node(r); createTree(data,root->right); } } int main(){ int N,M,K; cin>>N>>M>>K; vector<pair<int,int>> data(N+1); Tree.resize(N+1); for(int i=1;i<=N;i++) cin>>data[i].first >> data[i].second; Node* root = new Node(K); createTree(data,root); while(M--){ int t; cin>>t; Node* tmp = Tree[t]->left; Tree[t]->left = Tree[t]->right; Tree[t]->right = tmp; } stack<Node*> s; while(!s.empty() || root){ while(root){ s.push(root); root = root->left; } Node* tmp = s.top() ; s.pop(); cout<<tmp->val << " "; root = tmp->right; } cout<<endl; return 0; }
全部评论
(8) 回帖