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

link

A. Another One Bites The Dust

• 直接猜
• ac代码

/*************************************************************************
    > 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代码

/*************************************************************************
    > 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代码

/*************************************************************************
    > 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>b和a<b, 输入时将两种对分别储存起来
• 对于a<b的, 按a的降序进行排列, 对a>b的, 按b的升序进行排列就能保证符合题目要求
• ac代码

/*************************************************************************
    > 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;
}