Skip to content

2018 Multi-University Training Contest 2

Contents

A. Absolute

留坑。

B. Counting Permutations

留坑。

C. Cover

留坑。

D. Game

puts("Yes")。

Code 
#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
    while (scanf("%d", &n) != EOF) {
        puts("Yes");
    }
    return 0;
}

E. Hack It

留坑。

F. Matrix

留坑。

G. Naive Operations

题意：

给出 b[] 数组，里面是 1-n 的全排列。

两种操作：

  • 区间 +1。
  • 区间求 \displaystyle \sum_{i = l} ^ {i = r} \lfloor \frac{a_i}{b_i} \rfloor。

思路：

维护一个 Min 表示这个区间内需要的最少的进位，如果有进位，就更新到底，如果没有进位就区间更新。

Code 
#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define ll long long

ll arr[N];

struct node {
    int l, r;
    ll Min, lazy, sum, v;
    inline node() {}
    inline node(int _l, int _r) {
        l = _l;
        r = _r;
        Min = 0, lazy = 0, sum = 0, v = 0;
    }
} tree[N << 2];

inline void pushup(int id) {
    tree[id].Min = min(tree[id << 1].Min, tree[id << 1 | 1].Min);
    tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
}

inline void pushdown(int id) {
    if (tree[id].l >= tree[id].r)
        return;
    if (tree[id].lazy) {
        tree[id << 1].lazy += tree[id].lazy;
        tree[id << 1 | 1].lazy += tree[id].lazy;
        tree[id << 1].Min -= tree[id].lazy;
        tree[id << 1 | 1].Min -= tree[id].lazy;
        tree[id].lazy = 0;
    }
}

inline void build(int id, int l, int r) {
    tree[id] = node(l, r);
    if (l == r) {
        tree[id].v = arr[l];
        tree[id].Min = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}

inline void update(int id, int l, int r) {
    if (tree[id].l == l && tree[id].r == r && tree[id].Min > 1) {
        tree[id].lazy++;
        tree[id].Min--;
        return;
    }
    if (tree[id].l == tree[id].r && tree[id].Min == 1) {
        tree[id].Min = tree[id].v;
        tree[id].sum++;
        return;
    }
    pushdown(id);
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (r <= mid)
        update(id << 1, l, r);
    else if (l > mid)
        update(id << 1 | 1, l, r);
    else {
        update(id << 1, l, mid);
        update(id << 1 | 1, mid + 1, r);
    }
    pushup(id);
}

ll anssum;

inline void query(int id, int l, int r) {
    if (tree[id].l >= l && tree[id].r <= r) {
        anssum += tree[id].sum;
        return;
    }
    pushdown(id);
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (l <= mid)
        query(id << 1, l, r);
    if (r > mid)
        query(id << 1 | 1, l, r);
    pushup(id);
}

int n, m;
char str[100];
int l, r;

int main() {
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 1; i <= n; ++i) scanf("%lld", arr + i);
        build(1, 1, n);
        for (int i = 1; i <= m; ++i) {
            scanf("%s", str);
            if (str[0] == 'a') {
                scanf("%d %d", &l, &r);
                update(1, l, r);
            } else {
                scanf("%d %d", &l, &r);
                anssum = 0;
                query(1, l, r);
                printf("%lld\n", anssum);
            }
        }
    }
    return 0;
}

H. Odd Shops

留坑。

I. Segment

留坑。

J. Swaps and Inversions

水。

逆序对的意义就是每次只能交换相邻两个，最少的交换次数。

Code 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N 100010

int n, m;
ll x, y;
int arr[N], brr[N];
int a[N];

inline void Init() {
    for (int i = 1; i <= n; ++i) brr[i] = arr[i];
    sort(brr + 1, brr + 1 + n);
    m = unique(brr + 1, brr + 1 + n) - brr - 1;
}

inline int Get(int x) {
    return lower_bound(brr + 1, brr + 1 + m, x) - brr;
}

inline int lowbit(int x) {
    return x & (-x);
}

inline void update(int x, int val) {
    for (int i = x; i <= n; i += lowbit(i)) a[i] += val;
}

inline int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) res += a[i];
    return res;
}

int main() {
    while (scanf("%d%lld%lld", &n, &x, &y) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
        Init();
        memset(a, 0, sizeof a);
        for (int i = 1; i <= n; ++i) arr[i] = Get(arr[i]);
        ll ans = 0;
        for (int i = 1; i <= n; ++i) {
            //    ans += i - 1 - query(arr[i] - 1);
            //    printf("%d %d\n", arr[i], query(arr[i] - 1));
            update(arr[i], 1);
            ans += i - query(arr[i]);
            //    cout << arr[i] << " " << query(arr[i]) << endl;
        }
        printf("%lld\n", min(ans * x, ans * y));
    }
    return 0;
}
Last update: March 27, 2022
Created: March 27, 2022
Back to top