Skip to content

2018 Multi-University Training Contest 1

Contents

A. Maximum Multiple

题意：

给出一个 n 找 x, y, z 使得 n = x + y +z 并且 n \equiv 0 \pmod x, n \equiv 0 \pmod y, n \equiv 0 \pmod z 并且使得 x \cdot y \cdot z 最大。

思路：

设 a = \frac{n}{x}, b = \frac{n}{y}, c = \frac{n}{z} 那么 \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = 1 那么我们考虑去凑 a, b, c。

两种方案 {3, 3, 3} 或者 {2, 4, 4} 取 max。

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

using namespace std;

typedef long long ll;

ll n;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        if (n % 3 == 0) {
            ll ans = n / 3;
            ans *= n / 3;
            ans *= n / 3;
            printf("%lld\n", ans);
        } else if (n % 4 == 0) {
            ll ans = n / 2;
            ans *= n / 4;
            ans *= n / 4;
            printf("%lld\n", ans);
        } else {
            puts("-1");
        }
    }
    return 0;
}

B. Balanced Sequence

题意：

求如何拼接，使得 balanced Sequence 最长。

思路：

首先预处理，使得剩下的串都是 ((( 或者 ))) 或者 )))(((。

((( 这种都放左边 ))) 都放右边。

目前的问题就是 )))((( 这种在中间按什么顺序放使得答案最大。

我们定义 L_1, R_1 L_2, R_2 分别为两个串的左括号数量和右括号数量：

  • 假如 1 放在 2 前面 那么对答案的贡献是 min(R_1, L_2)。
  • 假如 1 放在 2 后面 那么对答案的贡献是 min(R_2, L_1)。

比较对答案的贡献，哪个答案贡献大，选哪种放置方式。

如果读答案的贡献一样大，那么我们让左括号多的放前面，因为这样对后面的答案贡献大。

Dup4's Code 
#include <bits/stdc++.h>

using namespace std;

#define N 100010

struct node {
    int l, r;
    inline node() {}
    inline node(int l, int r) : l(l), r(r) {}
    inline bool operator<(const node &b) const {
        int t1 = min(l, b.r), t2 = min(r, b.l);
        return t1 > t2 || (t1 == t2 && (l > b.l));
    }
} arr[N];

int t, n;
char s[N];

int main() {
    scanf("%d", &t);
    while (t--) {
        int L = 0, R = 0, ans = 0, cnt = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%s", s);
            int LL = 0, RR = 0;
            for (int j = 0, len = strlen(s); j < len; ++j) {
                if (s[j] == '(')
                    ++LL;
                else {
                    if (LL) {
                        --LL;
                        ans += 2;
                    } else
                        ++RR;
                }
            }
            if (LL && RR)
                arr[++cnt] = node(LL, RR);
            else if (LL)
                L += LL;
            else
                R += RR;
        }
        sort(arr + 1, arr + 1 + cnt);
        for (int i = 1; i <= cnt; ++i) {
            int LL = arr[i].l, RR = arr[i].r;
            ans += min(L, RR) * 2;
            L -= min(L, RR);
            L += LL;
        }
        ans += min(L, R) * 2;
        printf("%d\n", ans);
    }
    return 0;
}
Hsueh-'s Code 
#include <bits/stdc++.h>

using namespace std;

#define N 100010

struct node {
    int l, r;
    inline node() {}
    inline node(int l, int r) : l(l), r(r) {}
    inline bool operator<(const node &b) const {
        if (l >= r && b.l < b.r)
            return true;
        if (l < r && b.l >= b.r)
            return false;
        if (l >= r && b.l >= b.r)
            return r < b.r;
        if (l < r && b.l < b.r)
            return l > b.l;
    }
} arr[N];

int t, n;
char s[N];

int main() {
    scanf("%d", &t);
    while (t--) {
        int ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%s", s);
            int LL = 0, RR = 0;
            for (int j = 0, len = strlen(s); j < len; ++j) {
                if (s[j] == '(')
                    ++LL;
                else {
                    if (LL) {
                        --LL;
                        ans += 2;
                    } else
                        ++RR;
                }
            }
            arr[i] = node(LL, RR);
        }
        sort(arr + 1, arr + 1 + n);
        int L = 0;
        for (int i = 1; i <= n; ++i) {
            int LL = arr[i].l, RR = arr[i].r;
            ans += min(L, RR) * 2;
            L -= min(L, RR);
            L += LL;
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Triangle Partition

水。（排序）

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

using namespace std;

const int maxn = 1e3 + 10;

struct node {
    int x, y, id;
    inline node() {}
    inline node(int x, int y, int id) : x(x), y(y), id(id) {}
    inline bool operator<(const node &b) const {
        return x == b.x ? y < b.y : x < b.x;
    }
} P[maxn << 2];

int n;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= 3 * n; ++i) {
            scanf("%d %d", &P[i].x, &P[i].y);
            P[i].id = i;
        }
        sort(P + 1, P + 1 + 3 * n);
        for (int i = 1; i <= 3 * n; i += 3) {
            printf("%d %d %d\n", P[i].id, P[i + 1].id, P[i + 2].id);
        }
    }
    return 0;
}

D. Distinct Values

按题意模拟即可。

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

using namespace std;

#define N 100010

struct node {
    int l, r;
    inline void scan() {
        scanf("%d%d", &l, &r);
    }
    inline bool operator<(const node &r) const {
        return l < r.l || (l == r.l && this->r > r.r);
    }
} Data[N];

int t, n, m;
int ans[N];
bool vis[N];
int R;

int main() {
    scanf("%d", &t);
    while (t--) {
        memset(ans, 0, sizeof ans);
        R = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) Data[i].scan();
        sort(Data + 1, Data + 1 + m);
        for (int i = 1; i <= m; ++i) {
            int l = Data[i].l, r = Data[i].r;
            if (R >= r)
                continue;
            if (R + 1 < l)
                for (int j = R + 1; j < l; ++j) ans[j] = 1;
            memset(vis, false, sizeof vis);
            for (int j = l; j <= R; ++j) vis[ans[j]] = true;
            int L = 1;
            for (int j = max(R + 1, l); j <= r; ++j) {
                while (vis[L]) ++L;
                ans[j] = L;
                vis[L] = true;
            }
            R = max(R, r);
        }
        while (R < n) {
            R++;
            ans[R] = 1;
        }
        for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);
    }
    return 0;
}

E. Maximum Weighted Matching

留坑。

F. Period Sequence

留坑。

G. Chiaki Sequence Revisited

题意：

定义 a_n，求 \sum_{i = 1} ^ {i = n} a_i。

思路：

先不考虑 a_1。

我们对每个最后一个 2 的幂次数处理出它前面有多少个数，以及这些数的前缀和是多少。

比如说处理出：

1 2 4 8 16

1 3 7 15 31

1 5 20 76 288

然后给出 n 计算的时候 按二进制拆分 比方说：

27 = 15 + 7 + 3 + 3

定义 F[i] 为 前面 i 个数的前缀和。

ans[27] = F[15] + F[7] + 7 * 8 + F[3] + 3 * (8 + 2) + F[3] + 3 * (8 + 2 + 2)

对于后面，相当于所有数向右偏移。

注意取模。

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

using namespace std;

#define N 64
#define ll long long

const ll MOD = (ll)1e9 + 7;

int t;
ll n;
ll a[N], b[N], c[N];

inline void Init() {
    a[0] = 1;
    for (int i = 1; i <= 59; ++i) a[i] = a[i - 1] << 1;
    b[0] = 1;
    for (int i = 1; i <= 59; ++i) b[i] = (b[i - 1] << 1) + 1;
    c[0] = 1;
    for (int i = 1; i <= 59; ++i)
        c[i] = ((c[i - 1] << 1) % MOD + (a[i - 1] % MOD) * (b[i - 1] % MOD) % MOD + a[i]) % MOD;
    //    for (int i = 0; i <= 59; ++i) printf("%lld %lld %lld\n", a[i], b[i], c[i]);
}

int main() {
    Init();
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        --n;
        ll ans = 1, tmp = 0;
        for (int i = 59; i >= 0; --i) {
            while (n >= b[i]) {
                ans = (ans + c[i]) % MOD;
                ans = (ans + (b[i] % MOD * tmp) % MOD) % MOD;
                tmp = (tmp + a[i]) % MOD;
                n -= b[i];
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

H. RMQ Similar Sequence

留坑。

I. Lyndon Substring

留坑。

J. Turn Off The Light

留坑。

K. Time Zone

按题意模拟即可。

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

using namespace std;

int t, a, b;
char s[10];

inline void work1() {
    int ans = 0;
    int flag = 1;
    if (s[0] == '-')
        flag = -1;
    int len = strlen(s);
    for (int i = 1; i < len; ++i) ans = ans * 10 + s[i] - '0';
    ans *= flag;
    int gap = ans - 8;
    a = (a + gap + 24) % 24;
    printf("%02d:%02d\n", a, b);
    return;
}

inline void work2() {
    int A = 0, B = 0;
    int flag = 1;
    if (s[0] == '-')
        flag = -1;
    int len = strlen(s), i;
    for (i = 1; s[i] != '.'; ++i) A = A * 10 + s[i] - '0';
    for (++i; i < len; ++i) B = B * 10 + s[i] - '0';
    int tot = a * 60 + b;
    A *= flag, B = B * 6 * flag;
    int tmptot = A * 60 + B - 480;
    tot = (tot + tmptot + 24 * 60) % (24 * 60);
    printf("%02d:%02d\n", tot / 60, tot % 60);
    return;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d UTC%s", &a, &b, s);
        bool flag = true;
        for (int i = 0, len = strlen(s); i < len; ++i)
            if (s[i] == '.') {
                flag = false;
                break;
            }
        if (flag)
            work1();
        else
            work2();
    }
    return 0;
}
Last update: March 27, 2022
Created: March 27, 2022
Back to top