Skip to content

2018 Multi-University Training Contest 4

Contents

Problem A. Integers Exhibition

留坑。

Problem B. Harvest of Apples

题意：

计算 \sum_{i = 0}^{i = m}C(n, i)。

思路：

由 sum_{i = 0}^{i = m}C(n,i) 可以得到 sum_{i = 0}^{i = m + 1}C(n,i) 以及 sum_{i = 0}^{i = m}C(n + 1,i) 然后用莫对算法求解。

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

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;
const int maxn = 1e5 + 10;

int unit;
ll inv[maxn];
ll invfac[maxn];
ll fac[maxn];
ll ans[maxn];
int n, m;

struct node {
    int l, r, id;
    inline node() {}
    inline node(int l, int r, int id) : l(l), r(r), id(id) {}
    inline bool operator<(const node &b) const {
        if (l / unit != b.l / unit)
            return l / unit < b.l / unit;
        else
            return r < b.r;
    }
} arr[maxn];

inline void Init() {
    fac[0] = invfac[0] = 1;
    fac[1] = inv[1] = invfac[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
        invfac[i] = invfac[i - 1] * inv[i] % MOD;
    }
}

inline ll cal(int a, int b) {
    ll res = fac[a] * invfac[b] % MOD * invfac[a - b] % MOD;
    return res;
}

inline void work() {
    ll tmp = 0;
    for (int i = 0; i <= arr[1].r; ++i) {
        tmp = (tmp + cal(arr[1].l, i)) % MOD;
    }
    ans[arr[1].id] = tmp;
    int L = arr[1].l, R = arr[1].r;
    for (int i = 2; i <= n; ++i) {
        while (L < arr[i].l) {
            tmp = (tmp * 2 % MOD - cal(L++, R) + MOD) % MOD;
        }
        while (L > arr[i].l) {
            tmp = (tmp + cal(--L, R) + MOD) % MOD * inv[2] % MOD;
        }
        while (R < arr[i].r) {
            tmp = (tmp + cal(L, ++R)) % MOD;
        }
        while (R > arr[i].r) {
            tmp = (tmp - cal(L, R--) + MOD) % MOD;
        }
        ans[arr[i].id] = tmp;
    }
}

int main() {
    Init();
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &arr[i].l, &arr[i].r);
        arr[i].id = i;
    }
    unit = (int)sqrt(n);
    sort(arr + 1, arr + 1 + n);
    work();
    for (int i = 1; i <= n; ++i) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

Problem C. Problems on a Tree

留坑。

Problem D. Nothing is Impossible

题意：

给出 n 道题目，每道题目有 a_i 种正确选择，b_i 种错误选择。

一共有 m 个人，所有人都要选择一个题目集合去做，相当于去试答案，问最多能试出多少道题目答案。

思路：

排序，前缀积。

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

#define N 110
#define ll long long

struct node {
    int a, b, sum;
    inline void scan() {
        scanf("%d%d", &a, &b);
        sum = a + b;
    }
    inline bool operator<(const node &r) const {
        return sum < r.sum;
    }
} arr[N];

int t, n, m;
ll sum;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) arr[i].scan();
        sort(arr + 1, arr + 1 + n);
        int ans = 0;
        sum = 1;
        for (int i = 1; i <= n; ++i) {
            sum *= arr[i].sum;
            if (sum > m)
                break;
            ans = i;
        }
        printf("%d\n", ans);
    }
    return 0;
}

Problem E. Matrix from Arrays

题意：

给出一种构造二维数组的构造方式，然后给出一个左上角，一个右下角，求这个矩形内的数和。

思路：

打表找规律发现，大矩阵是由若干个 2L \cdot 2L 个小矩阵构成的，那么把给出的矩阵分成四块，整块整块的处理，边边角角的处理。

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

using namespace std;

#define N 110

typedef long long ll;

int n;
int x[2], y[2];
ll arr[N];
ll G[N][N];

inline ll cal(int x, int y) {
    if (x < 0 || y < 0)
        return 0ll;
    ll res = G[n - 1][n - 1] * (x / n) * (y / n) + G[n - 1][y % n] * (x / n) + G[x % n][n - 1] * (y / n) +
             G[x % n][y % n];
    return res;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%lld", arr + i);
        }
        for (int i = 0, cnt = 0; i < (n << 2); ++i) {
            for (int j = 0; j <= i; ++j) {
                G[j][i - j] = arr[cnt];
                cnt = (cnt + 1) % n;
            }
        }
        n <<= 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                G[i][j] += (i ? G[i - 1][j] : 0);
                G[i][j] += (j ? G[i][j - 1] : 0);
                G[i][j] -= ((i && j) ? G[i - 1][j - 1] : 0);
            }
        }
        int q;
        scanf("%d", &q);
        while (q--) {
            scanf("%d %d %d %d", &x[0], &y[0], &x[1], &y[1]);
            ll ans = cal(x[1], y[1]) - cal(x[0] - 1, y[1]) - cal(x[1], y[0] - 1) + cal(x[0] - 1, y[0] - 1);
            printf("%lld\n", ans);
        }
    }
    return 0;
}
Code 
#include <bits/stdc++.h>
using namespace std;

#define N 1100
#define ll long long

int t, n, q, x[2], y[2];
ll arr[N];
ll G[N][N];

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%lld", arr + i);
        memset(G, 0, sizeof G);
        for (int i = 0, cnt = 0; i <= (n << 2); ++i) {
            for (int j = 0; j <= i; ++j) {
                G[j][i - j] = arr[cnt + 1];
                cnt = (cnt + 1) % n;
            }
        }
        n <<= 1;
        ll base = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) base += G[i][j];
        scanf("%d", &q);
        while (q--) {
            scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);
            ll ans = 0, tmp;
            // compute Big
            ll xl = (x[1] - x[0] + 1) / n, yl = (y[1] - y[0] + 1) / n;
            ans += (base * xl * yl);
            // compute lower_left corner
            tmp = 0;
            for (int i = x[0] + xl * n; i <= x[1]; ++i) {
                for (int j = y[0], cnt = 1; cnt <= n; ++cnt, ++j) tmp += G[i % n][j % n];
            }
            // compute upper_right corner
            ans += tmp * yl;
            tmp = 0;
            for (int i = x[0], cnt = 1; cnt <= n; ++cnt, ++i) {
                for (int j = y[0] + yl * n; j <= y[1]; ++j) tmp += G[i % n][j % n];
            }
            // compute lower_right corner
            ans += tmp * xl;
            tmp = 0;
            for (int i = x[0] + xl * n; i <= x[1]; ++i) {
                for (int j = y[0] + yl * n; j <= y[1]; ++j) ans += G[i % n][j % n];
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

Problem F. Travel Through Time

留坑。

留坑。

Problem H. Eat Cards, Have Fun

留坑。

Problem I. Delightful Formulas

留坑。

Problem J. Let Sudoku Rotate

题意：

给出一个 16 \times 16 的数独，有一些 4 \times 4 的矩阵被逆时针旋转过，然后求恢复最少需要旋转多少次。

思路：

爆搜，两条剪枝，一个是判断是否有冲突，一个是判断当前步数是否比已有答案大。

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

using namespace std;

const int maxn = 1e2 + 10;

int ans;
bool vis[20];
char s[20];
int G[maxn][maxn];

inline bool judge(int x, int y) {
    for (int i = x * 4 - 3; i <= x * 4; ++i) {
        memset(vis, false, sizeof vis);
        for (int j = 1; j <= y * 4; ++j) {
            if (vis[G[i][j]])
                return false;
            vis[G[i][j]] = true;
        }
    }
    for (int i = y * 4 - 3; i <= y * 4; ++i) {
        memset(vis, false, sizeof vis);
        for (int j = 1; j <= x * 4; ++j) {
            if (vis[G[j][i]])
                return false;
            vis[G[j][i]] = true;
        }
    }
    return true;
}

inline void fun(int x, int y) {
    int tmp[10][10];
    for (int i = 1; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
            tmp[j][4 - i + 1] = G[(x - 1) * 4 + i][(y - 1) * 4 + j];
        }
    }
    for (int i = 1; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
            G[(x - 1) * 4 + i][(y - 1) * 4 + j] = tmp[i][j];
        }
    }
}
inline void DFS(int x, int y, int res) {
    if (res >= ans)
        return;
    if (y > 4) {
        DFS(x + 1, 1, res);
        return;
    }
    if (x == 5) {
        ans = min(ans, res);
        return;
    }
    for (int i = 0; i < 4; ++i) {
        if (i) {
            fun(x, y);
            /*            if(x == 3 && y == 1 && i == 1)
            {
            for(int i = x * 4 - 3; i <= x * 4; ++i)
            {
            for(int j = y * 4 - 3; j <= y * 4; ++j)
            {
            printf("%d%c", G[i][j], " \n"[j == y * 4]);
            }
            }
            }*/
        }
        if (judge(x, y)) {
            DFS(x, y + 1, res + i);
        }
    }
    fun(x, y);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        ans = 1 << 16;
        for (int i = 1; i <= 16; ++i) {
            scanf("%s", s + 1);
            for (int j = 1; j <= 16; ++j) {
                if (s[j] >= '0' && s[j] <= '9') {
                    G[i][j] = s[j] - '0';
                } else if (s[j] >= 'A' && s[j] <= 'F') {
                    G[i][j] = (s[j] - 'A') + 10;
                }
            }
        }
        //    fun(1, 1);
        DFS(1, 1, 0);
        printf("%d\n", ans);
    }
    return 0;
}

Problem K. Expression in Memories

按题意模拟即可

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

#define N 100010

int t;
char s[N];

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s);
        bool flag = true;
        int len = strlen(s);
        for (int i = 0; i < len; ++i) {
            if (s[i] == '*' || s[i] == '+') {
                if (i == 0 || i == len - 1) {
                    flag = false;
                    break;
                } else if (s[i + 1] == '*' || s[i + 1] == '+') {
                    flag = false;
                    break;
                }
            } else if (s[i] == '0') {
                if (i == 0 || s[i - 1] == '*' || s[i - 1] == '+') {
                    if (i + 1 < len && s[i + 1] >= '0' && s[i + 1] <= '9') {
                        flag = false;
                        break;
                    } else if (s[i + 1] == '?')
                        s[i + 1] = '+';
                }
            } else if (s[i] == '?') {
                s[i] = '1';
            }
        }
        if (flag) {
            printf("%s\n", s);
        } else {
            printf("IMPOSSIBLE\n");
        }
    }
    return 0;
}

Problem L. Graph Theory Homework

水。

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);
        for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
        int ans = (int)floor(sqrt(abs(arr[1] - arr[n])));
        printf("%d\n", ans);
    }
    return 0;
}
Last update: March 28, 2022
Created: March 28, 2022
Back to top