前言
上青后掉分的第一把。Round998 Div3手感好做出了5题上青，F是个组合数学（还没去学）没补，紧接着第二天网上打了这场1+2，结果打的稀碎。
赛时做了A、B，赛后补C、D
A. Kevin and Arithmetic
算法标签 math
题目大意
有n个元素的数组和一个初始化为0的s，每次从数组中取一个整数a[i]，并将s更新为s+a[i]。如果s为偶数，得分+1，并将s反复除以2，直到s变为奇数。
解题思路
注意到只有s为偶数时加分，且每次得到的s加分之后都会变为奇数，所以除第一次外，选取偶数元素对得分无贡献，选取奇数元素得分+1。对于第一次选数，如果选择偶数，得分+1，否则得分不变。
只需要统计数组中奇偶数个数，如果偶数个数不为0，得分为奇数个数+1；否则为奇数个数-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void solve() {
int cnt1 = 0, cnt2 = 0;
cin >> n;
for(int x, i = 1; i <= n; ++i) {
cin >> x;
if(x & 1) ++cnt1;
else ++cnt2;
}
if(cnt2 > 0) {
cout << cnt1 + 1 << '\n';
} else {
cout << cnt1 - 1 << '\n';
}
}
|
B. Kevin and Geometry
算法标签：geometry，greedy
题目大意
有n根木棍，求能否拿其中的4个木棍拼出等腰梯形。
解题思路
找到最大的腰，以及差最小的底和高。
可以用map去找数值相同的元素，用一个变量记录可作为腰的最大值（其实可相等值对不只一对的话可以直接输出），将数组去掉这个腰后排序，遍历数组找到最小的arr[i + 1] - arr[i]。
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
| void solve() {
cin >> n;
map<int, int> s;
int edge = 0;
for(int i = 1; i <= n; ++i) {
cin >> arr[i];
s[arr[i]]++;
if(s[arr[i]] > 1) {
edge = max(edge, arr[i]);
}
}
int flag = s[edge] - 2;
for(int i = 1; i <= n; ++i) {
if(arr[i] == edge) {
if(flag) {
flag--;
}
else arr[i] = 0x7fffffff;
}
}
if(edge == 0) {
cout << -1 << '\n';
return;
}
sort(arr + 1, arr + 1 + n);
for(int i = 1; i <= n; ++i) {
int len;
if(arr[i] == edge) {
if(s[arr[i]] <= 2) continue;
}
len = arr[i] + 2 * edge;
if(arr[i + 1] < len) {
cout << edge << ' ' << edge << ' ' << arr[i] << ' ' << arr[i + 1] << '\n';
return;
}
}
cout << -1 << '\n';
}
|
其实这个代码有很多可以简化的部分（比如使用erase去掉腰），但是鸽了）
C. Kevin and Puzzle
算法标签：dp
题目大意
n个人站成一排，每个人说自己左边有多少骗子。已知两个骗子不能紧挨着站，骗子可以说谎话也可以说实话，求可能的情况数模998244353。
解题思路
赛时读错题了（翻译插件出锅），想用种类并查集做。发现读错题后觉得是个DP（我dp不好）就去看D题了，当时觉得D有思路，C就先放下了。
因为骗子不能紧挨着站，所以如果a是骗子，那么a左边和右边的人都说真话。所以对于3~n内的每个i，第i个人说真话时的情况数可以由i - 1和i - 2两个人说谎的情况数得到。
即：如果arr[i] = arr[i - 2] + 1，那么dp[i] += dp[i - 2]；如果arr[i] = arr[i - 1]，那么dp[i] += dp[i - 1]。
如果第i个人一定为骗子，那么dp[i] = 0
（dp[i]表示第i个人说真话的方案数）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> arr[i];
}
memset(dp, 0, sizeof(dp));
dp[1] = (arr[1] == 0);
dp[0] = 1;
for(int i = 2; i <= n; ++i) {
if(arr[i] == arr[i - 1]) {
dp[i] += dp[i - 1];
}
if(arr[i] == arr[i - 2] + 1) {
dp[i] += dp[i - 2];
}
dp[i] %= 998244353;
}
int ans = (dp[n] + dp[n - 1]) % 998244353;
cout << ans << '\n';
}
|
D. Kevin and Numbers
算法标签：greedy
题目大意
有一个序列a，一个序列b。有一个操作：从a中取出两个差值小于等于1的元素x和y，并将x+y放入序列a。能否执行任意次操作实现将a转变为b（对于任意x，x在两个序列中出现的次数相同）。
解题思路
赛时用map和优先队列写了个假贪心，结果一直wa3。当时想着每次从a中取最小的元素，如果b中没有这个元素，就从a中取第二小的元素并尝试执行合并操作。
赛后找到了hack数据：
如果按照原来的思路，那么对a操作最后会得到 3 9， 无法得到b。
正确的做法应该将操作转化为将b中元素分解。因为每次合并的元素差值小于等于1，所以b中每个元素的分解方法是唯一的。
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
| void solve() {
cin >> n >> m;
priority_queue<int> a;
priority_queue<int> b;
for(int x, i = 1; i <= n; ++i) {
cin >> x;
a.push(x);
}
for(int x, i = 1; i <= m; ++i) {
cin >> x;
b.push(x);
}
while(!a.empty()) {
if(b.empty() || b.size() > a.size()) {
cout << "NO" << '\n';
return;
}
int x = b.top(); b.pop();
if(x < a.top()) {
cout << "NO" << '\n';
return;
}
if(x == a.top()) {
a.pop();
continue;
}
b.push(x >> 1); b.push(x + 1 >> 1);
}
if(!b.empty()) {
cout << "NO" << '\n';
}
else cout << "YES" << '\n';
|
具体做法还是用优先队列去实现。
