- 题目链接http://120.78.128.11/Contest.jsp?cid=18
- 题面不贴了
- 都是英文题，看的我心力憔悴 =7=
一、Ugly Numbers
- 题目说一个数的质因数只包含2、3或者5（一个或多个），就是丑陋数。拜托，为啥这些数就丑陋了。然后题目特别说明第一个丑陋数是1
- 题目多组数据输入到0为止，然后输出第n个丑陋数。
- 解题思路就是对于一个丑陋数k，那么一定有2*k、3*k和5*k也是丑陋数，所以按照这个思路入队模拟打表即可
- 值得注意的是，对于2*k1来说可能和 3*k2重复,例如2*12 = 3*8；所以在入队的时候不能让重复元素入队。
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 priority_queue<ll,vector<ll>,greater<ll> >q; 45 vector<ll>p(1501); 46 47 void init(){ 48 q.push(1); 49 int num = 1; 50 for(int i = 1; i <= 1501; i++){ 51 ll sum = q.top(); 52 q.pop(); 53 p[num++] = sum; 54 ll a = sum*2, b = sum*3, c = sum*5; 55 if((a % 5) && (a % 3)) 56 q.push(a); 57 if(b % 5) 58 q.push(b); 59 q.push(c); 60 } 61 } 62 63 int main(){ 64 ios_base::sync_with_stdio(false); 65 cout.tie(0); 66 cin.tie(0); 67 int n; 68 init(); 69 while(cin>>n && n){ 70 cout << p[n] << endl; 71 } 72 73 return 0; 74 }
二、The kth great number
- 题意就是第一行输入n，k，表示下面有n行操作，I a表示把a入队，Q表示查询并输出当前数字中第k大的数。
- 用优先队列存k个元素，当已经存了k个元素，新元素进入再出队就行了。
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 int num; 46 friend bool operator < (node a,node b){ 47 return a.num > b.num; 48 } 49 }temp; 50 51 int main(){ 52 ios_base::sync_with_stdio(false); 53 cout.tie(0); 54 cin.tie(0); 55 int n,k; 56 while(~scanf("%d%d",&n,&k)){ 57 priority_queue<node>q; 58 for(int i = 0; i < n; i++){ 59 char tp; 60 int num; 61 scanf(" %c",&tp); 62 if(tp == 'I'){ 63 scanf("%d",&num); 64 if(q.size() >= k){ 65 if(num > q.top().num){ 66 q.pop(); 67 temp.num = num; 68 q.push(temp); 69 } 70 } 71 else{ 72 temp.num = num; 73 q.push(temp); 74 } 75 } 76 else{ 77 int res = q.top().num; 78 cout << res << endl; 79 } 80 } 81 } 82 83 return 0; 84 }
三、Fence Repair
- 题面坑死我了，好半天才搞懂题意，就是第一行n，然后下面n个数，表示要把原木头锯成这么n段。然后每一次锯木头就消耗木头长度的钱，问最少要多少钱。
- 思路是递归的思路，从最短的开始往回推，因为设锯开后的长度分别为a，b，肯定要保证a+b最小，才能消耗最少。
- 所以就是从最小和次小的开始，加起来入队，同时消耗的金钱也要加上这个和。
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 int main(){ 45 ios_base::sync_with_stdio(false); 46 cout.tie(0); 47 cin.tie(0); 48 int n; 49 while(cin>>n){ 50 priority_queue<int, vector<int>,greater<int> >q; 51 ll ans = 0,num,a,b; 52 for(int i = 0; i < n; i++){ 53 cin>>num; 54 q.push(num); 55 } 56 while(q.size() > 1){ 57 a = q.top(); 58 q.pop(); 59 b = q.top(); 60 q.pop(); 61 q.push(a+b); 62 ans += a+b; 63 } 64 cout << ans << endl; 65 } 66 67 return 0; 68 }
四、看病要排队
- 另一篇文章有讲这个题，思路就是开三个优先队列模拟即可
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 int id; 46 int cnt; 47 node(int id,int cnt):id(id),cnt(cnt){} 48 friend operator < (node a,node b){ 49 if(a.cnt == b.cnt){ 50 return a.id > b.id; 51 } 52 return a.cnt < b.cnt; 53 } 54 }; 55 56 int main(){ 57 ios_base::sync_with_stdio(false); 58 cout.tie(0); 59 cin.tie(0); 60 int n; 61 while(cin>>n){ 62 priority_queue<node>j,k,l; 63 int tot = 1; 64 for(int i = 1; i <= n; i++){ 65 string s; 66 int a,b; 67 cin>>s; 68 if(s[0] == 'I'){ 69 cin>>a>>b; 70 node tp(tot++,b); 71 if(a == 1){ 72 j.push(tp); 73 } 74 else if(a == 2){ 75 k.push(tp); 76 } 77 else if(a == 3){ 78 l.push(tp); 79 } 80 } 81 else if(s[0] == 'O'){ 82 cin>>a; 83 if(a == 1){ 84 if(j.empty()){ 85 cout<<"EMPTY"<<endl; 86 } 87 else{ 88 node tp = j.top(); 89 j.pop(); 90 cout<<tp.id<<endl; 91 } 92 } 93 else if(a == 2){ 94 if(k.empty()){ 95 cout<<"EMPTY"<<endl; 96 } 97 else{ 98 node tp = k.top(); 99 k.pop(); 100 cout<<tp.id<<endl; 101 } 102 } 103 else if(a == 3){ 104 if(l.empty()){ 105 cout<<"EMPTY"<<endl; 106 } 107 else{ 108 node tp = l.top(); 109 l.pop(); 110 cout<<tp.id<<endl; 111 } 112 } 113 114 } 115 } 116 } 117 return 0; 118 }
五、Windows Message Queue
- 就是叫你模拟信息队列
- 两种操作GET就是得到优先级最高的信息出队，PUT三个参数，序号，信息，优先级值。
- 题目说明优先级值越低的优先级越高，然后优先级值相同时，谁先进谁优先级高。
- 队列为空时输出EMPTY QUEUE!
- 开个结构体存信息，优先级值，序号，重载一下<号，模拟即可
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 string msg; 46 int num,id; 47 node(string _msg,int _num,int _id):msg(_msg),num(_num),id(_id){} 48 friend operator < (node a,node b){ 49 if(a.num == b.num){ 50 return a.id > b.id; 51 } 52 return a.num > b.num; 53 } 54 }; 55 56 int main(){ 57 ios_base::sync_with_stdio(false); 58 cout.tie(0); 59 cin.tie(0); 60 priority_queue<node,vector<node>,less<node> >p; 61 int i = 0; 62 while(++i){ 63 string s; 64 if(!(cin>>s)){ 65 break; 66 } 67 if(s[0] == 'G'){ 68 if(p.empty()){ 69 cout << "EMPTY QUEUE!" << endl; 70 } 71 else{ 72 node tp = p.top(); 73 p.pop(); 74 cout << tp.msg << endl; 75 } 76 } 77 else{ 78 string msg,ct; 79 int num; 80 cin>>msg>>ct>>num; 81 //cout << msg << " " << ct << " " << num << endl; 82 msg = msg + ' ' + ct; 83 //cout << msg << endl; 84 p.push(node(msg,num,i)); 85 86 } 87 } 88 89 return 0; 90 }
六、Black Box
- 也是欺负我英语不好，翻译老半天
- 第一行给你一个n和k
- 第二行n个数，第三行k个数
- 然后输出当第ki个数输入是，第i小的数是多少。
- 思路是开一个小顶堆和大顶堆，当查询第i个元素时，把前ki个元素先入小顶堆，然后把交换两个堆的元素，直到保证小顶堆所有元素都大于大顶堆里面的，这样小顶堆的首元素就是第i小的数。然后依次把小顶堆的数往大顶堆移即可。
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 int a[30010]; 45 46 int main(){ 47 ios_base::sync_with_stdio(false); 48 cout.tie(0); 49 cin.tie(0); 50 int n,m,x; 51 priority_queue<int, vector<int>,greater<int> >p; 52 priority_queue<int, vector<int>,less<int> >q; 53 cin>>n>>m; 54 for(int i = 0; i < n; i++){ 55 cin>>a[i]; 56 } 57 int c = 0; 58 for(int i = 0; i < m; i++){ 59 cin>>x; 60 while(c < x){ 61 p.push(a[c++]); 62 } 63 while(!q.empty() && p.top() < q.top()){ 64 int t = p.top(); 65 p.pop(); 66 p.push(q.top()); 67 q.pop(); 68 q.push(t); 69 } 70 cout << p.top() << endl; 71 q.push(p.top()); 72 p.pop(); 73 } 74 return 0; 75 }
七、Stones
- 另一篇博文也有些，就是开个结构体存位置和能抛多远就行，再重构一下排序操作。
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 int pos,num; 46 bool operator < (const node b)const{ 47 if(pos != b.pos) 48 return b.pos < pos; 49 return b.num < num; 50 } 51 }; 52 53 int main(){ 54 ios_base::sync_with_stdio(false); 55 cout.tie(0); 56 cin.tie(0); 57 int t,n; 58 node tp; 59 cin>>t; 60 while(t--){ 61 cin>>n; 62 priority_queue<node>q; 63 for(int i = 0; i < n; i++){ 64 cin>>tp.pos>>tp.num; 65 q.push(tp); 66 } 67 int flag = 1; 68 while(!q.empty()){ 69 tp = q.top(); 70 q.pop(); 71 if(flag){ 72 flag = 0; 73 tp.pos += tp.num; 74 q.push(tp); 75 } 76 else 77 flag = 1; 78 } 79 cout << tp.pos << endl;; 80 } 81 return 0; 82 }
八、求中位数
- 这道题开始我想偷懒vector处理直接tle =7=
- 和黑盒子那题一样，开两个优先队列维护即可。
- 不过这题有个坑点就是题目说明数据在int范围内，但你开int的堆就会wa，得开longlong（别问我为啥会知道=7=）
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 int main(){ 45 ios_base::sync_with_stdio(false); 46 cout.tie(0); 47 cin.tie(0); 48 int n; 49 while(cin>>n){ 50 priority_queue<ll>q; 51 priority_queue<ll,vector<ll>,greater<ll> >p; 52 for(int i = 0; i < n; i++){ 53 ll a,b; 54 cin>>a; 55 if(a == 1){ 56 cin>>b; 57 if(q.empty() && p.empty()){ 58 q.push(b); 59 } 60 else{ 61 if(b > q.top()){ 62 p.push(b); 63 } 64 else{ 65 q.push(b); 66 } 67 if(q.size() < p.size()){ 68 q.push(p.top()); 69 p.pop(); 70 } 71 else if(q.size() > p.size() + 1){ 72 p.push(q.top()); 73 q.pop(); 74 } 75 } 76 } 77 else{ 78 if((q.size() + p.size()) % 2 == 0){ 79 ll res = q.top() + p.top(); 80 if(res % 2 == 0) 81 cout << res/2 << endl; 82 else 83 cout << fixed << setprecision(1) << (db)res/2.0 << endl; 84 } 85 else{ 86 ll res = q.top(); 87 cout << res << endl; 88 } 89 } 90 } 91 } 92 93 return 0; 94 }
