Hello 2018

题目列表

http://codeforces.com/contest/913

分题详解

A.Modular Exponentiation

题目大意:给定n和m,计算$ m%2^n $
解题思路:计算$ 2^n $,直到$ 2^n \geq m$或者得到$2^n$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int main(int argc, char **argv){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
int tmp = 1;
for (int i = 0; i < n; ++i){
tmp *= 2;
if (tmp * 2 > m){
break;
}
}
cout << m % tmp << endl;
return 0;
}

B.Christmas Spruce

题目大意:输入一个树,判断是否每个叶子节点都有3个叶子儿子,当然不考虑非叶子儿子。
解题思路:用数组来记录每个节点是否是一个叶子节点,并且记录当前节点的叶子儿子的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*************************************************************************
> File Name: B.cpp
> Author: xudian
> Email: xudianc@gmail.com
> Created Time: 一 1/ 8 22:23:12 2018
************************************************************************/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
// 当前节点的父亲节点数组
int father[1020];
// 当前节点的叶子儿子节点个数
int sum[1020];
// 当前节点是否的叶子节点
bool leaf[1020];

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
memset(father, 0, sizeof father);
memset(sum, 0, sizeof sum);
memset(leaf, true, sizeof leaf);
for (int i = 2; i <= n; ++i){
cin >> father[i];
//如果当前节点的父亲节点之前还是标记为叶子节点,即这个节点是当前父亲节点的第一个儿子节点。
if (leaf[father[i]] == true){

if (father[father[i]] != 0){
// 当前节点的父亲节点的父亲节点的叶子节点数减一
--sum[father[father[i]]];
}
// 当前节点的父亲节点置为非叶子节点
leaf[father[i]] = false;
}
++sum[father[i]];
}
bool ans = true;
for (int i = 1; i <= n; ++i){
if (leaf[i] == false and sum[i] < 3){
ans = false;
break;
}
}
if (ans == true){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}

C.Party Lemonade

题目大意:现在有$n$种大小的饮料,容量分别为$2^0,2^1,,,2^{n-1}$升,价格在输入数据里面,问现在要买至少$L$升饮料至少花费多少.
解题思路:先假设所有的饮料都买最大的瓶子,那么需要$L/2^{n-1}$个$2^{n-1}$容量的瓶子,目前的花费是$ L/2^{n-1} * c_n $,当然也许不能完全平分的话$ tmp = L \% 2^{n-1}$,我们就把多余的部分用一个最大的瓶子来装,那么花费就是$(L/2^{n-1}+1) * c_n$,当然,多余的部分我们一直需要额外处理,我们做完这一部分之后检查稍微小一点的瓶子饮料的性价比是否比当前的瓶子饮料的性价比高,如果高的话,我们换一下瓶子,以此类推,每推一步,我们需要比较一下花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

long long c[33];
long long cnt[33];
long long ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
long long n, L;
cin >> n >> L;
for (int i = 0; i < n; ++i){
cin >> c[i];
}
ans = 0x3f3f3f3f3f3f3f3f;
memset(cnt, 0, sizeof cnt);
long long tmp = L;
for(int i = n - 1; i >= 0; --i){
for (int j = n - 1; j > i; --j){
if (c[i] *(1<< (j - i)) < c[j]){
cnt[i] += cnt[j] << (j - i);
cnt[j] = 0;
}
}
cnt[i] += tmp / (1 << i);
tmp = tmp % (1 << i);
long long tmp_ans = 0;
for (int j = 0; j < n; ++j){
tmp_ans += c[j] * cnt[j];
}
if (tmp != 0){
tmp_ans += c[i];
}
ans = min(ans, tmp_ans);
}
cout << ans << endl;
return 0;
}

D.Too Easy Problems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
const int maxn = 200100;
const int inf = 0x3f3f3f3f;

int n, T;
vector<pair<int, int>> vec[maxn];
priority_queue<pair<int, int>> pq;
int x, y;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n >> T;
for (int i = 1; i <= n; ++i){
cin >> x >> y;
vec[x].push_back(make_pair(y, i));
}
long long sum = 0;
for (int i = n; i >= 0; --i){
for (auto u : vec[i]){
pq.push(u);
sum += u.first;
}
while (pq.size() > i){
sum -= pq.top().first;
pq.pop();
}
if (pq.size() == i and sum <= T){
cout << i << endl;
cout << i << endl;
while (pq.size()){
cout << pq.top().second << " ";
pq.pop();
}
cout << endl;
break;
}
}

return 0;
}

总结

菜,菜,菜,真的菜。
读题读错,丢脸丢到外太空去了。