19.6.2 CF 2019 GR3 解题报告 (4 / 8)

A. Another One Bites The Dust

  • 直接猜
  • ac代码
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
/*************************************************************************
> File Name: a.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: 2019年06月01日 星期六 22时33分07秒
************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#define iofuck std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
ll a, b, c;
int main(){
iofuck;
ll ans = 0;
cin >> a >> b >> c;
ans += c * 2;
ll minn = min(a, b);
ll maxn = max(a, b);
if(maxn > minn){
ans += minn * 2 + 1;
}else{
ans += minn * 2;
}
cout << ans << endl;
return 0;
}

B. Born This Way

  • 二分 + 暴力
  • ac代码
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
/*************************************************************************
> File Name: b.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: 2019年06月01日 星期六 22时44分32秒
************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#define iofuck std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int nmax = 2 * 100000 + 5;
const int inf = 1 << 28;
ll n, m, ta, tb, k;
ll a[nmax], b[nmax];
int main(){
iofuck;
cin >> n >> m >> ta >> tb >> k;
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < m; i++){
cin >> b[i];
//timeb[i] = b[i] + tb;
}
if(k >= n){
cout << -1 << endl;
return 0;
}
ll ans = 0;
for(ll i = 0; i <= k; i++){
ll tmp = lower_bound(b, b + m, a[i] + ta) - b;
if(tmp == m || k - i >= (m - tmp)) {
cout << -1 << endl;
return 0;
}
ans = max(b[tmp + k - i] + tb, ans);
}
cout << ans << endl;
return 0;
}

C. Crazy Diamond

  • 刚开始用的选择排序, 果断t了
  • 注意到数据只是1~n, 就是说直接通过当前位置找到要改变的位置
  • ac代码
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*************************************************************************
> File Name: c_2.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: 2019年06月02日 星期日 11时46分46秒
************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#define iofuck std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
vector<P> v;
const int nmax = 3e5 + 5;
int a[nmax], pos[nmax];
int n, ans = 0;
void swp(int i, int j){
v.push_back(P(i, j));
swap(pos[a[i]], pos[a[j]]);
swap(a[i], a[j]);
/*
for(int k = 1; k <= n; k++){
cout << a[k] << " - ";
}
*/
cout << endl;
}
int main(){
iofuck;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
pos[a[i]] = i;
}
for(int i = 2; i < n; i++){
if(a[i] == i) continue;
int p = pos[i];
if(abs(p - i) >= n / 2){
ans++;
swp(i, p);
}else{
if(i <= n / 2 && p <= n / 2){
ans += 2;
swp(p, n);
swp(i, n);
}else if(i <= n / 2 && p > n / 2){
ans += 3;
swp(1, p);
swp(1, n);
swp(i, n);
}else{
ans += 2;
swp(1, p);
swp(1, i);
}
}
}
if(a[1] != 1) swp(1, n), ans++;
cout << ans << endl;
for(auto tmp : v){
cout << tmp.first << " " << tmp.second << endl;
}
return 0;
}

D. Dirty Deeds Done Dirt Cheap

  • 注意到有两种对a>ba<b, 输入时将两种对分别储存起来
  • 对于a<b的, 按a的降序进行排列, 对a>b的, 按b的升序进行排列就能保证符合题目要求
  • ac代码
    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
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    /*************************************************************************
    > File Name: d.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年06月02日 星期日 20时03分41秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    #define iofuck std::ios::sync_with_stdio(false)
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> P;
    const int nmax = 3e5 + 5;
    int n;
    vector<P> a_b, b_a;
    map<P, int> mapp;
    bool cmpa_b(P a, P b){
    return a.second < b.second;
    }
    bool cmpb_a(P a, P b){
    return a.first > b.first;
    }
    int main(){
    iofuck;
    cin >> n;
    int a, b;
    int mark = 0;
    int marka_b = 0;
    int markb_a = 0;
    for(int i = 0; i < n; i++){
    cin >> a >> b;
    if(a > b){
    a_b.push_back(P(a, b));
    marka_b++;
    mapp[P(a, b)] = ++mark;
    }else{
    markb_a++;
    b_a.push_back(P(a, b));
    mapp[P(a, b)] = ++mark;
    }
    }
    sort(a_b.begin(), a_b.end(), cmpa_b);
    sort(b_a.begin(), b_a.end(), cmpb_a);
    if(marka_b > markb_a){
    cout << marka_b << endl;
    for(auto tmp : a_b){
    cout << mapp[tmp] << " ";
    }
    }else{
    cout << markb_a << endl;
    for(auto tmp : b_a){
    cout << mapp[tmp] << " ";
    }
    }
    /*
    cout << "-----------" << endl;
    for(auto tmp : a_b){
    cout << tmp.first << " " << tmp.second << endl;
    }
    cout << "-----------" << endl;
    for(auto tmp : b_a){
    cout << tmp.first << " " << tmp.second << endl;
    }
    */
    return 0;
    }