【XJTU 2020暑期集训】Day14 - 2019 Multi-University Training Contest 8

I - Calabash and Landlord

显然可以分类讨论两个矩形的位置关系，但是很蠢（指比赛时候的我......）。可以将所有坐标离散化在 [0,4]\times [0,4] 的区域内，然后打标记并dfs即可。

J - Quailty and CCPC

签到题，先判断再排序输出即可。

K - Roundgod and Milk Tea

原题可以转化为：有一个二分图，左边是学生节点，右边是奶茶节点，每一个学生可以连向非自己班制作的奶茶，问你最大匹配。由霍尔定理「对于二分图 (U+V,E)，最大匹配数 |M|=|U|-\max_{S\subseteq U}(|S|-|N(S)|)，其中 N(S) 表示点集 S 中每个点所连点集的并」，我们可以分类讨论。当 S=\varnothing 时，|M|=|U|；当 S 中有两个来自不同班级的同学时，有 N(S)=V，可得 |M|=|V|；当 S 中的同学全部来自同一个班级时，|N(S)|=|V|-b_i，可得 |M|=|U|+|V|-b_i-a_i。

Code

I - Calabash and Landlord

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 10

using namespace std;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int T, x[2][2], y[2][2];
int f[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];

int getid(vector<int> &v, int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

bool ok(int x, int y) {
    return 0 <= x && x < 5 && 0 <= y && y < 5;
}

void dfs(int x, int y) {
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (!vis[nx][ny] && ok(nx, ny) && f[nx][ny] == f[x][y]) {
            dfs(nx, ny);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        vector<int> vx, vy;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                cin >> x[i][j] >> y[i][j];
                vx.push_back(x[i][j]);
                vy.push_back(y[i][j]);
            }
        }
        sort(vx.begin(), vx.end());
        sort(vy.begin(), vy.end());
        vx.erase(unique(vx.begin(), vx.end()), vx.end());
        vy.erase(unique(vy.begin(), vy.end()), vy.end());
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                x[i][j] = getid(vx, x[i][j]);
                y[i][j] = getid(vy, y[i][j]);
            }
        }
        memset(f, 0, sizeof(f));
        for (int k = 0; k < 2; k++) {
            for (int i = x[k][0]; i < x[k][1]; i++) {
                for (int j = y[k][0]; j < y[k][1]; j++) {
                    f[i][j] |= (1 << k);
                }
            }
        }
        memset(vis, false, sizeof(vis));
        int ans = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (!vis[i][j]) {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
}

J - Quailty and CCPC

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 100005
#define int long long

using namespace std;

struct Data {
    string s;
    int p, t;
    friend bool operator<(const Data &a, const Data &b) {
        if (a.p != b.p) {
            return a.p > b.p;
        }
        return a.t < b.t;
    }
};

int T, n, d;
Data a[MAX_N];

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> d;
        for (int i = 1; i <= n; i++) {
            cin >> a[i].s >> a[i].p >> a[i].t;
        }
        if (n * d % 10 != 5) {
            cout << "Quailty is very great" << endl;
            continue;
        }
        sort(a + 1, a + 1 + n);
        int pos = n * d / 10 + 1;
        cout << a[pos].s << endl;
    }
}

K - Roundgod and Milk Tea

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005
#define int long long

using namespace std;

int T, n;
int a[MAX_N];
int b[MAX_N];

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i] >> b[i];
        }
        int sa = 0, sb = 0;
        for (int i = 1; i <= n; i++) {
            sa += a[i], sb += b[i];
        }
        int ans = min(sa, sb);
        for (int i = 1; i <= n; i++) {
            ans = min(ans, sa + sb - b[i] - a[i]);
        }
        cout << ans << endl;
    }
}