2017.12.2 定段赛第一场 15:30分场 内含中文翻译
2017.12.2 定段赛第一场 18:30分场 内含中文翻译
Codeforces Round #436 (Div. 2)原题地址
本套题目相对基础，CD需要一定的实现能力，E需要对dp有较好的掌握。
A. Fair Game 模拟
本题写法比较多，如果会使用标准库中的map可以写得比较快比较稳。具体的思路就是统计出现次数后看是否只有两个相等的频率。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
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// head
int main()
{
int n, x;
while (scanf("%d", &n) == 1) {
map<int, int> ma;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
ma[x]++;
}
if (ma.size() == 2 && ma.begin()->se == n / 2) {
puts("YES");
printf("%d %d\n", ma.begin()->fi, ma.rbegin()->fi);
} else {
puts("NO");
}
ma.clear();
}
return 0;
}
B. Polycarp and Letters 模拟
本题的写法也很多，需要找到一系列位置，任意两个位置之间没有大写字母，然后位置中不同小写字母最多。简单思考可以发现：题目其实就是找出相邻两个大写字母之间有几个不同小写字母。可以利用set进行去重。一个可能出错的点是结尾处的小写字母后面没有大写字母，在后面补一个大写字母直接做即可。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
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// head
const int N = 205;
char s[N];
int main()
{
int n;
while (scanf("%d%s", &n, s) == 2) {
int last = 0;
int ans = 0;
s[n++] = 'A';
for (int i = 0; i < n; i++) {
if (isupper(s[i])) {
set<char> ch;
for (int j = last; j < i; j++) {
ch.insert(s[j]);
}
ans = max(ans, (int)ch.size());
last = i + 1;
}
}
printf("%d\n", ans);
}
return 0;
}
C. Bus 模拟 贪心
本题乍看之下很简单，无非就是一定要加油了才加油。实际写起来会有一些棘手，第一个问题在于出发时和最后结束时走过的是左半或者右半，而当中都是左半或者右半的两倍，第二个问题在于最后不知道是走左半结束还是右半结束。
许多做出来的同学的做法是进行多个判断，这也是最简单直接的做法，但是这种做法十分容易出错。一种更好的做法是把问题进行简化，直接计算出每次距离下次可以停止的位置有多远，获得一系列距离，对于这些距离直接裸贪心即可，不需要任何条件处理。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
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// head
int main()
{
int a, b, f, k;
while (scanf("%d%d%d%d", &a, &b, &f, &k) == 4) {
int lenL = f, lenR = a - f;
vector<int> v;
v.push_back(lenL);
for (int i = 1; i <= k; i++) {
if (i == k) {
v.push_back(lenR);
} else {
v.push_back(2 * lenR);
}
swap(lenL, lenR);
}
bool fail = false;
int ans = 0;
int curFuel = b;
for (auto &dis : v) {
if (dis > curFuel) {
ans++;
curFuel = b;
}
curFuel -= dis;
if (curFuel < 0) fail = true;
}
printf("%d\n", fail ? -1 : ans);
}
return 0;
}
D. Make a Permutation! 模拟 贪心
本题容易发现是贪心，一个数字若是出现了，一定保留一个然后其他变为没出现的数，对于早出现的可以替换的数，尽量让它小。显然是需要计数，需要维护最小的不在数组中的数，不断更新。有几个关键点，第一个是判别是否可以替换，第二个是可以替换的话也可能不换更好，因为当前的数可以比最小的不存在的数还小，第三个是可以替换选择不换之后后面就必须换了。
这题我开始的时候想简单了，推倒重写了一次，改完之后有些丑陋，但是暂时没有想到更好的写法。大概就是维护计数cnt，已经使用的标记used然后最小不在数组中的数cur，根据条件小心地更新。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
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// head
const int N = 2e5+5;
int a[N], cnt[N], used[N];
int main()
{
int n, x;
while (scanf("%d", &n) == 1) {
memset(cnt, 0, sizeof cnt);
memset(used, 0, sizeof used);
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
cnt[a[i]]++;
}
int ans = 0;
int cur = 1;
for (int i = 0; i < n; i++) {
while (cnt[cur] || used[cur]) cur++;
int choice = a[i];
cnt[a[i]]--;
if ((choice > cur && cnt[a[i]] > 0) || used[choice]) choice = cur;
if (choice != a[i]) ans++;
a[i] = choice;
used[choice] = true;
}
printf("%d\n", ans);
for (int i = 0; i < n; i++) {
printf("%d%c", a[i], i==n-1 ? '\n' : ' ');
}
}
return 0;
}
E. Fire dp 回溯
本题是基础的dp回溯。dp的部分，主要是要发现先炸的东西如果要救肯定是先救的，否则交换之后不会变差只会变好，然后就是中规中矩的转移，前$i$个物品在$j$时刻最多能取多少价值的物品，转移来源要么当前物品不取从上面一层直接复制过来，要么取物品，减去时刻加上价值。
回溯的部分相比dp会困难一些，主要就是多记录一个最优更新来源的数组，记录方式多种多样，第一种是直接记录状态更新用的是哪个物品，另一种是记录状态是从哪个状态更新来的，如果更新来的状态时刻变了说明当前物品被取了。需要谨慎地处理好边界。
第一种回溯方法
1 |
|
第二种回溯方法
1 |
|