- 題目連結 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 }
View Code
二、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 }