官方题解
codeforces上题目一般高于平时的面试题。如果是为了面试的话，只刷LeetCode就可以了。不过如果是对算法和竞赛感兴趣，强烈鼓励试一试。题目的数量和质量都远超LeetCode。而且为不同水平的同学有不同的赛道，题目难度也不同。对于高水平玩家来说，竞赛体验会好的多。
我目前共参加过2场Div.2，rating 1480。没错，初始值是1500，我反而掉下来了。
A. Filling Diamonds
可以用动态规划的方式思考这个问题。对于长度为n的belt来说，共有2种状态：
/
和
1.
/
\
状态转移方程有:
dp[n][0] = dp[n-1][1] + dp[n-1][0],
dp[n][1] = dp[n-1][1].
对于初始值有:
dp[0][1] = 1,
dp[0][0] = 0.
答案为: dp[n][0].
通过该方程可以很快地得出dp[n][0] = n。
时间复杂度: O(1),
空间复杂度: O(1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
cout << n << endl;
}
return 0;
}
|
出题人也很骄傲地说，这是目前最简单的Div.2 A了。代码很简单，但是思路还挺巧妙。
B. Sorted Adjacent Differences
贪心。先排序，从中间开始选，向右跳一下，向左跳一下。
时间复杂度: O(n log n),
空间复杂度: O(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
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int SIZE = 1e5 + 5;
using ll = long long;
vector<int> a(SIZE);
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a.begin(), a.begin() + n);
int current = (n - 1) / 2;
int left = current, right = current;
bool direction = true;
while (current >= 0 && current < n) {
cout << a[current] << " ";
if (direction) {
++right;
current = right;
} else {
--left;
current = left;
}
direction = !direction;
}
cout << endl;
}
return 0;
}
|
C. Powered Addition
问题可以转化为: 可以给数组中的任何数 加 最多 2^k - 1. 使得整个数组非递减。求最小的k.
时间复杂度: O(N),
空间复杂度: O(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
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
ll max_value_in_array = numeric_limits<ll>::min();
ll max_demand = 0;
for (int i = 0; i < n; ++i){
ll current;
cin >> current;
if (current > max_value_in_array) {
max_value_in_array = current;
} else {
max_demand = max(max_demand, max_value_in_array - current);
}
}
int ans = 0;
ll could_present = 1;
while (could_present <= max_demand) {
++ans;
could_present *= 2;
}
cout << ans << endl;
}
return 0;
}
|