Skip to content

2018 Multi-University Training Contest 3

Contents

Problem A. Ascending Rating

题意：

给出 n 个数，给出区间长度 m。对于每个区间，初始值的 max 为 0，cnt 为 0. 遇到一个 a[i] > ans, 更新 ans 并且 cnt++。

计算

\begin{eqnarray*} A &=& \sum_{i = 1}^{i = n - m +1} (max \oplus i) \\ B &=& \sum_{i = 1}^{i = n - m +1} (cnt \oplus i) \end{eqnarray*}

思路：

单调队列，倒着扫一遍，对于每个区间的 cnt 就是队列的长度，扫一遍即可。

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

using namespace std;

const int maxn = 1e7 + 10;
typedef long long ll;

int t;
int n, m, k;
ll p, q, r, mod;
ll arr[maxn];
ll brr[maxn];

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d %lld %lld %lld %lld", &n, &m, &k, &p, &q, &r, &mod);
        for (int i = 1; i <= n; ++i) {
            if (i <= k)
                scanf("%lld", arr + i);
            else
                arr[i] = (p * arr[i - 1] + q * i + r) % mod;
        }
        ll A = 0, B = 0;
        int head = 0, tail = -1;
        for (int i = n; i > (n - m + 1); --i) {
            while (head <= tail && arr[i] >= arr[brr[tail]]) tail--;
            brr[++tail] = i;
        }
        for (int i = n - m + 1; i >= 1; --i) {
            while (head <= tail && arr[i] >= arr[brr[tail]]) tail--;
            brr[++tail] = i;
            while (brr[head] - i >= m) head++;
            A += arr[brr[head]] ^ i;
            B += (tail - head + 1) ^ i;
        }
        printf("%lld %lld\n", A, B);
    }
    return 0;
}

Problem B. Cut The String

留坑。

Problem C. Dynamic Graph Matching

题意：

给出 n 个点。

两种操作，一种是加边，一种是减边，每次加一条或者减一条。

每次操作后输出 1, 2, \cdots, \frac{n}{2} 表示对应的数量的边。

问有几种取法，并且任意两个边不能相邻。

思路：

每加一条边，都可以转移状态 比如说 110100 到 111110 就是 dp[111110] += dp[110100]。

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

using namespace std;

typedef long long ll;
const int maxn = 1 << 10;
const int MOD = 1e9 + 7;

int t, n, m;
ll dp[maxn];
ll ans[12];

inline int cal(int x) {
    int cnt = 0;
    while (x) {
        if (x & 1)
            cnt++;
        x >>= 1;
    }
    return cnt;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        memset(ans, 0, sizeof ans);
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        scanf("%d %d", &n, &m);
        while (m--) {
            char op[10];
            int u, v;
            scanf("%s %d %d", op, &u, &v);
            --u, --v;
            for (int s = 0; s < (1 << n); ++s) {
                if ((s & (1 << u)) || (s & (1 << v)))
                    continue;
                int S = s | (1 << u);
                S |= (1 << v);
                if (op[0] == '+') {
                    dp[S] = (dp[S] + dp[s]) % MOD;
                    ans[cal(S)] = (ans[cal(S)] + dp[s]) % MOD;
                } else if (op[0] == '-') {
                    dp[S] = (dp[S] - dp[s] + MOD) % MOD;
                    ans[cal(S)] = (ans[cal(S)] - dp[s] + MOD) % MOD;
                }
            }
            for (int i = 2; i <= n; i += 2) {
                printf("%lld%c", ans[i], " \n"[i == n]);
            }
        }
    }
    return 0;
}

Problem D. Euler Function

打表找规律。

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

using namespace std;

#define N 100010

inline int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

inline void Init() {
    for (int i = 1; i <= 100; ++i) {
        int res = 0;
        for (int j = 1; j < i; ++j) res += (gcd(i, j) == 1);
        printf("%d %d\n", i, res);
    }
}

int t, n;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        if (n == 1)
            puts("5");
        else
            printf("%d\n", n + 5);
    }
    return 0;
}

Problem E. Find The Submatrix

留坑。

Problem F. Grab The Tree

题意：

一棵树，每个点有点权，小 Q 可以选择若干个点，并且任意两个点之间没有边，小 T 就是剩下的所有点，然后两个人的值就是拥有的点异或起来，求小 Q 赢还是输还是平局。

思路：

显然，只有赢或者平局的情况，只要考虑是否有平局情况就可以，当所有点异或起来为 0 便是平局。

Code 
#include <bits/stdc++.h>
using namespace std;

#define N 100010

int t, n;
int arr[N];

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", arr + i);
            res ^= arr[i];
        }
        for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v);
        if (res == 0) {
            puts("D");
            continue;
        }
        puts("Q");
    }
    return 0;
}

Problem G. Interstellar Travel

题意：

给出 n 个点。

要从 i -> j 当且仅当 x_i < x_j 花费为 x_i \cdot y_j - x_j \cdot y_i。

求从 1 -> n 的权值最小。

如果多解输出字典序最小的解。

思路：

可以发现权值就是叉积。

求个凸包。

然后考虑在一条线上的情况。

Code 
#include <bits/stdc++.h>
using namespace std;

#define N 200010

const double eps = 1e-8;

inline int sgn(double x) {
    if (fabs(x) < eps)
        return 0;
    if (x < 0)
        return -1;
    else
        return 1;
}

struct Point {
    double x, y;
    int id;
    inline Point() {}
    inline Point(double x, double y) : x(x), y(y) {}
    inline void scan(int _id) {
        id = _id;
        scanf("%lf%lf", &x, &y);
    }
    inline bool operator==(const Point &r) const {
        return sgn(x - r.x) == 0 && sgn(y - r.y) == 0;
    }
    inline bool operator<(const Point &r) const {
        return x < r.x || x == r.x && y < r.y || x == r.x && y == r.y && id < r.id;
    }
    inline Point operator+(const Point &r) const {
        return Point(x + r.x, y + r.y);
    }
    inline Point operator-(const Point &r) const {
        return Point(x - r.x, y - r.y);
    }
    inline double operator^(const Point &r) const {
        return x * r.y - y * r.x;
    }
    inline double distance(const Point &r) const {
        return hypot(x - r.x, y - r.y);
    }
};

struct Polygon {
    int n;
    Point p[N];
    struct cmp {
        Point p;
        inline cmp(const Point &p0) {
            p = p0;
        }
        inline bool operator()(const Point &aa, const Point &bb) {
            Point a = aa, b = bb;
            int d = sgn((a - p) ^ (b - p));
            if (d == 0) {
                return sgn(a.distance(p) - b.distance(p)) < 0;
            }
            return d < 0;
        }
    };
    inline void norm() {
        Point mi = p[0];
        for (int i = 1; i < n; ++i) mi = min(mi, p[i]);
        sort(p, p + n, cmp(mi));
    }
    inline void Graham(Polygon &convex) {
        sort(p + 1, p + n - 1);
        int cnt = 1;
        for (int i = 1; i < n; ++i) {
            if (!(p[i] == p[i - 1]))
                p[cnt++] = p[i];
        }
        n = cnt;
        norm();
        int &top = convex.n;
        top = 0;
        if (n == 2) {
            top = 2;
            convex.p[0] = p[0];
            convex.p[1] = p[1];
            return;
        }
        if (n == 3) {
            top = 3;
            convex.p[0] = p[0];
            convex.p[1] = p[1];
            convex.p[2] = p[2];
            return;
        }
        convex.p[0] = p[0];
        convex.p[1] = p[1];
        top = 2;
        for (int i = 2; i < n; ++i) {
            while (top > 1 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^ (p[i] - convex.p[top - 2])) >= 0) {
                if (sgn((convex.p[top - 1] - convex.p[top - 2]) ^ (p[i] - convex.p[top - 2])) == 0) {
                    if (p[i].id < convex.p[top - 1].id)
                        --top;
                    else
                        break;
                } else {
                    --top;
                }
            }
            convex.p[top++] = p[i];
        }
        if (convex.n == 2 && (convex.p[0] == convex.p[1]))
            --convex.n;
    }
} arr, ans;

int t, n;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        arr.n = n;
        //    cout << n << endl;
        for (int i = 0; i < n; ++i) arr.p[i].scan(i + 1);
        arr.Graham(ans);
        for (int i = 0; i < ans.n; ++i) printf("%d%c", ans.p[i].id, " \n"[i == ans.n - 1]);
    }
    return 0;
}

Problem H. Monster Hunter

留坑。

Problem I. Random Sequence

留坑。

Problem J. Rectangle Radar Scanner

留坑。

Problem K. Transport Construction

留坑。

Problem L. Visual Cube

按题意模拟即可，分块解决。

Code 
#include <bits/stdc++.h>
using namespace std;

int t, a, b, c, n, m;
char ans[200][200];

int main() {
    scanf("%d", &t);
    while (t--) {
        memset(ans, 0, sizeof ans);
        scanf("%d%d%d", &a, &b, &c);
        n = (b + c) * 2 + 1;
        m = (a + b) * 2 + 1;
        for (int i = n, cnt = 1; cnt <= c; ++cnt, i -= 2) {
            for (int j = 1; j <= 2 * a; j += 2) ans[i][j] = '+', ans[i][j + 1] = '-';
        }
        for (int i = n - 1, cnt = 1; cnt <= c; ++cnt, i -= 2) {
            for (int j = 1; j <= 2 * a; j += 2) ans[i][j] = '|';
        }
        for (int i = 2 * b + 1, tmp = 0, cnt = 1; cnt <= b + 1; ++cnt, i -= 2, tmp += 2) {
            for (int j = 1 + tmp, cntt = 1; cntt <= a; ++cntt, j += 2) ans[i][j] = '+', ans[i][j + 1] = '-';
        }
        for (int i = 2 * b, tmp = 1, cnt = 1; cnt <= b; ++cnt, tmp += 2, i -= 2) {
            for (int j = 1 + tmp, cntt = 1; cntt <= a; ++cntt, j += 2) ans[i][j] = '/';
        }
        for (int j = m, cntt = 1, tmp = 0; cntt <= b + 1; ++cntt, j -= 2, tmp += 2) {
            for (int i = 1 + tmp, cnt = 1; cnt <= c + 1; ++cnt, i += 2) {
                ans[i][j] = '+';
                if (cnt <= c)
                    ans[i + 1][j] = '|';
            }
        }
        for (int j = m - 1, tmp = 1, cntt = 1; cntt <= b; ++cntt, tmp += 2, j -= 2) {
            for (int i = 1 + tmp, cnt = 1; cnt <= c + 1; ++cnt, i += 2) ans[i][j] = '/';
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j)
                if (!ans[i][j])
                    ans[i][j] = '.';
            ans[i][m + 1] = 0;
            printf("%s\n", ans[i] + 1);
        }
    }
    return 0;
}

Problem M. Walking Plan

题意：

给出一张图，询问从 u -> v 至少经过 k 条路的最少花费。

思路：

因为 k <= 10000 那么我们可以拆成 k = x * 100 + y 然后考虑分块

G[k][i][j] 表示 i -> j 至少经过 k 条路。

dp[k][i][j] 表示 i -> j 至少经过 k \cdot 100 条路。

然后查询的时候枚举中间点。

Code 
#include <bits/stdc++.h>
using namespace std;

#define N 210
#define INFLL 0x3f3f3f3f3f3f3f3f
#define ll long long

int t, n, m, q;
ll G[N][55][55], dp[N][55][55];

inline void Init() {
    memset(G, 0x3f, sizeof G);
    memset(dp, 0x3f, sizeof dp);
}

inline void Floyd() {
    for (int l = 2; l <= 200; ++l)
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j) G[l][i][j] = min(G[l][i][j], G[l - 1][i][k] + G[1][k][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int l = 199; l >= 0; --l) G[l][i][j] = min(G[l][i][j], G[l + 1][i][j]);  // at least K roads;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) dp[1][i][j] = G[100][i][j];
    for (int l = 2; l <= 100; ++l)
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j) dp[l][i][j] = min(dp[l][i][j], dp[l - 1][i][k] + dp[1][k][j]);
}

inline void Run() {
    scanf("%d", &t);
    while (Init(), t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1, u, v, w; i <= m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            G[1][u][v] = min(G[1][u][v], (ll)w);
        }
        Floyd();
        scanf("%d", &q);
        for (int i = 1, u, v, k; i <= q; ++i) {
            scanf("%d%d%d", &u, &v, &k);
            int unit = floor(k * 1.0 / 100), remind = k - unit * 100;
            ll ans = INFLL;
            if (k <= 100)
                ans = G[k][u][v];
            else {
                for (int j = 1; j <= n; ++j) ans = min(ans, dp[unit][u][j] + G[remind][j][v]);
            }
            if (k > 100 && remind == 0)
                ans = min(ans, dp[unit][u][v]);
            printf("%lld\n", ans >= INFLL ? -1 : ans);
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("Test.in", "r", stdin);
#endif

    Run();
    return 0;
}
Last update: March 27, 2022
Created: March 27, 2022
Back to top