Codeforces Round #624 (Div. 3)

传送门

A. Add Odd or Subtract Even

签到。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/2/24 22:38:13
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;

int a, b;

void run(){
    cin >> a >> b;
    if((a & 1) == (b & 1)) {
        if(a > b) cout << 1 << '
';
        else if(a == b) cout << 0 << '
';
        else cout << 2 << '
';
    } else {
        if(a > b) {
            cout << 2 << '
';
        } else {
            cout << 1 << '
';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

B. WeirdSort

直接暴力就行。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/2/24 22:44:40
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 100 + 5;

int n, m;
int a[N], b[N], p[N];
vector <int> v[N];
bool chk[N];

void run(){
    for(int i = 1; i <= 100; i++) v[i].clear();
    memset(chk, false, sizeof(chk));
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i]; b[i] = a[i];
        v[a[i]].push_back(i);
    }
    for(int i = 1; i <= m; i++) {
        cin >> p[i];
        chk[p[i]] = true;
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        if(a[i] != b[i]) {
            for(int j = i; j <= n; j++) {
                if(b[j] == a[i]) {
                    swap(b[i], b[j]);
                    break;   
                }
                if(!chk[j]) {
                    cout << "NO" << '
';
                    return;   
                }
            }   
        }
    }
    cout << "YES" << '
';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

C. Perform the Combo

对每个字符利用前缀单独统计答案即可。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/2/24 23:25:46
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;

int n, m;
char s[N];
int p[N];
int sum[N][26];

void run(){
    cin >> n >> m;
    cin >> (s + 1);
    for(int i = 1; i <= m; i++) cin >> p[i]; p[m + 1] = n;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 26; j++) sum[i][j] = sum[i - 1][j];
        ++sum[i][s[i] - 'a'];   
    }
    auto query = [&](int l, int r, int v) {
        return sum[r][v] - sum[l - 1][v];   
    };
    vector <ll> ans(26, 0);
    for(int i = 1; i <= m + 1; i++) {
        for(int j = 0; j < 26; j++) {
            ans[j] += query(1, p[i], j);   
        }
    }
    for(int i = 0; i < 26; i++) cout << ans[i] << ' ';
    cout << '
';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

D. Three Integers

题意：
给出(a,b,c,aleq bleq cleq 10^4)。
现在可以对任意一个数执行任意次加减(1)的操作，但不能出现非正数。
问最少执行多少次操作，使得(a|b|c)。

思路：
直接在范围内找出所有满足整除关系的三元组然后暴力算就行。
我的做法是枚举中间那个数，然后据此来找第一个和第三个数。
但这个题有个坑点就是，(a,b,c)三个数的值可能会超过(10^4)，所以要把范围设大一点。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/2/24 23:39:25
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 20000 + 5;
 
int a, b, c;
vector <int> d[N];
 
void init() {
    for(int i = 1; i <= 20000; i++) {
        for(int j = 1; 1ll * j * j <= i; j++) {
            if(i % j == 0) {
                d[i].push_back(j);
                int k = i / j;
                if(j != k) d[i].push_back(k);
            }   
        }
        sort(all(d[i]));
    }   
}
 
void run(){
    cin >> a >> b >> c;
    pair<pii, int> ans;
    int Min = INF;
    for(int i = 1; i <= 20000; i++) {
        int aa, bb, cc;
        int res = abs(b - i);
        bb = i;
        int t = lower_bound(all(d[i]), a) - d[i].begin();
        if(abs(d[i][t] - a) > abs(d[i][max(0, t - 1)] - a)) {
            aa = d[i][max(0, t - 1)];
            res += abs(d[i][max(0, t - 1)] - a);
        } else {
            aa = d[i][t];
            res += abs(d[i][t] - a);
        }
        int v1 = c / i * i, v2 = (c / i + 1) * i;
        if(abs(v1 - c) > abs(v2 - c)) {
            cc = v2;
            res += abs(v2 - c);
        } else {
            cc = v1;
            res += abs(v1 - c);
        }
        if(res < Min) {
            Min = res;   
            ans = MP(MP(aa, bb), cc);
        }
    }
    cout << Min << '
';
    cout << ans.fi.fi << ' ' << ans.fi.se << ' ' << ans.se << '
';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    init();
    int T; cin >> T;
    while(T--) run();
    return 0;
}

E. Construct the Binary Tree

题意：
构造一颗以(1)为根，有(n)个点的二叉树，所有结点的深度和为(d)。
每个结点的深度为从他出发到达根节点的路径长度。
(n,dleq 5000)。

思路：

• 显然我们知道(n)个点的树，深度和最大和最小为多少。据此可以判掉不合法的情况。
• 然后从(1)开始(dfs)，并且在每个结点枚举两颗子树的(sz)，若两颗子树的(sz)能够满足当前需要的深度(r)(见代码)，则求出每颗子树需要的深度然后往下递归即可；不行就只有一颗子树。

注意一下细节：因为每次算一颗子树的贡献时我们都以当前结点作为根结点，所以(r)要减去子树(sz)才能满足。
时间复杂度：(O(n^2))。
详见代码：

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/2/25 11:20:11
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 5000 + 5;

int n, d, son;
int f[N];

pii get(int n, int s = 0) {
    pii res(0, 0);
    int t = n, p = 1, now = s;
    while(t >= p) {
        t -= p;
        res.fi += now * p;
        ++now;
        p <<= 1;
    }
    res.fi += now * t;
    res.se = (2 * s + n - 1) * n / 2;
    return res;
}

bool chk(int n, int d) {
    pii res = get(n);
    return res.fi <= d && d <= res.se;   
}

void gao(int u, int now, int r) {
    --now;
    r -= now;
    for(int i = 0; i < now; i++) {
        pii t1 = get(i), t2 = get(now - i);
        if(t1.fi + t2.fi <= r && r <= t1.se + t2.se) {
            int lt = t1.fi, rt = t2.se;
            if(lt + rt > r) {
                rt -= lt + rt - r;
            } else if(lt + rt < r) {
                lt += r - (lt + rt);
            }
            if(i) {
                f[++son] = u;
                gao(son, i, lt);
            }
            if(now - i) {
                f[++son] = u;
                gao(son, now - i, rt);
            }
            return;
        }
    }
}

void run(){
    son = 1;
    cin >> n >> d;
    if(!chk(n, d)) {
        cout << "NO" << '
';
        return;   
    }
    cout << "YES" << '
';
    gao(1, n, d);
    for(int i = 2; i <= n; i++) {
        cout << f[i] << " 
"[i == n];   
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

F. Moving Points

类似于一个二维偏序的问题，对横坐标排序后，用两个树状数组分别维护负速度和正速度的值。
我们将一对(d_i-d_j)拆开，每次对于一个点只计算(d_i)最终出现的次数即可。
我们从前往后、从后往前扫两遍即可计算出(cnt_i)。
最后的答案就为(displaystylesum_{i=1}^n d_icdot cnt_i)。
细节见代码：

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/2/24 23:59:19
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;

int n;
pii a[N];

struct Bit {
    int c[N];
    void clear() {
        memset(c, 0, sizeof(c));   
    }
    int lowbit(int x) {return x & (-x);}
    void add(int x) {
        for(; x < N; x += lowbit(x)) ++c[x];
    }
    int query(int x) {
        int res = 0;
        for(;x ; x -= lowbit(x)) res += c[x];   
        return res;   
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}bit[2];

int ans[N];

void run(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].fi;
    for(int i = 1; i <= n; i++) cin >> a[i].se;
    sort(a + 1, a + n + 1, [&](pii A, pii B) {
        if(A.fi == B.fi) return A.se < B.se;
        return A.fi < B.fi;
    });
    vector <int> f, z;
    for(int i = 1; i <= n; i++) {
        if(a[i].se > 0) z.push_back(a[i].se);
        else f.push_back(a[i].se);
    }
    sort(all(f)), sort(all(z));
    f.erase(unique(all(f)), f.end()), z.erase(unique(all(z)), z.end());
    auto find = [&](int it, vector <int>& v) {
        return lower_bound(all(v), it) - v.begin() + 1;
    };
    for(int i = 1; i <= n; i++) {
        if(a[i].se > 0) {
            int t = find(a[i].se, z);
            ans[i] += bit[0].query(t);
            ans[i] += bit[1].query(N - 1);
            bit[0].add(t);
        } else {
            int t = find(a[i].se, f);
            ans[i] += bit[1].query(t);
            bit[1].add(t);
        }
    }
    bit[0].clear(), bit[1].clear();
    for(int i = n; i >= 1; i--) {
        if(a[i].se > 0) {
            int t = find(a[i].se, z);
            ans[i] -= bit[0].query(t, N - 1);
            bit[0].add(t);
        } else {
            int t = find(a[i].se, f);
            ans[i] -= bit[1].query(t, N - 1);
            ans[i] -= bit[0].query(N - 1);
            bit[1].add(t);
        }   
    }
    ll res = 0;
    for(int i = 1; i <= n; i++) res += 1ll * a[i].fi * ans[i];
    cout << res << '
';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}