let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2016 VOIEXAM - Tạo đề thi

Bài này ta tạo và tính giá trị tất cả các biểu thức có thể có của mỗi biểu thức trong đề bài. Sau đó tạo đồ thị 2 phía, 1 bên là N biểu thức, bên kia là giá trị của biểu thức. Sau đó ta tìm cặp ghép cực đại để in kết quả.

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <queue>
using namespace std;

#define LL long long

template<class T>
T C(T a, char op, T b) {
    if (op=='+') return a + b;
    if (op=='-') return a - b;
    if (op=='*') return a * b;
    throw 0;
}

template<class T, class P>
string V(T a, char op, P b) {
    stringstream ss;
    ss << '(' << a << op << b << ')';
    return string(ss.str());
}

vector<int> ke[2000];
int trace[2000];

int match(int n, int m) {
    vector<int> visited(n, -1);
    vector<int> ref(n);

    vector<int> mx(n, -1);
    vector<int> my(m, -1);
    int cnt = 0;

    for (int i=0; i<n; i++) if (mx[i] < 0) {
        struct { int u, v; } res = {-1, -1};

        queue<int> q;
        q.push(i);
        visited[i] = i;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v: ke[u]) {
                if (my[v] >= 0 && visited[my[v]] != i) {
                    q.push(my[v]);
                    ref[my[v]] = u;
                    visited[my[v]] = i;
                } else if (my[v] < 0) {
                    res = {u, v}; 
                    break;
                }
            }
            if (res.u >= 0) break;
        }

        if (res.u >= 0) {
            cnt++;
            while (true) {
                int vv = mx[res.u];
                mx[res.u] = res.v;
                my[res.v] = res.u;
                if (res.u == i) break;
                res = {ref[res.u], vv};
            };
        }
    }

    if (cnt < n) return cnt;

    for (int i=0; i<n; i++) if (mx[i] >= 0) {
        for (int j=0; j<(int)ke[i].size(); j++) {
            if (ke[i][j] == mx[i]) {
                trace[i] = j;
                break;
            }
        }
    } else trace[i] = -1;

    return cnt;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n; cin.ignore();
    vector<vector<string>> view(n);
    vector<vector<LL>> val(n);
    for (int i=0; i<n; i++) {
        string s;
        getline(cin, s);

        int cnt_op = 0;
        LL num[4] = {0,0,0,0};
        char op[4];
        for (char c: s) {
            if ('0' <= c && c <= '9') {
                num[cnt_op] *= 10;
                num[cnt_op] += c - '0';
            } else {
                op[cnt_op] = c;
                cnt_op++;
            }
        }

        if (cnt_op == 1) {
            val[i].push_back(C(num[0], op[0], num[1]));
            view[i].push_back(s);
        }
        if (cnt_op == 2) {
            val[i].push_back(C(C(num[0],op[0],num[1]),op[1],num[2]));
            val[i].push_back(C(num[0],op[0],C(num[1],op[1],num[2])));
            view[i].push_back(V(V(num[0],op[0],num[1]),op[1],num[2]));
            view[i].push_back(V(num[0],op[0],V(num[1],op[1],num[2])));
        }
        if (cnt_op == 3) {
            val[i].push_back(C(C(C(num[0],op[0],num[1]),op[1],num[2]),op[2],num[3])); // 0 1 2
            val[i].push_back(C(C(num[0],op[0],num[1]),op[1],C(num[2],op[2],num[3]))); // 0 2 1
            val[i].push_back(C(C(num[0],op[0],C(num[1],op[1],num[2])),op[2],num[3])); // 1 0 2
            val[i].push_back(C(num[0],op[0],C(C(num[1],op[1],num[2]),op[2],num[3]))); // 1 2 0
            val[i].push_back(C(num[0],op[0],C(num[1],op[1],C(num[2],op[2],num[3])))); // 2 1 0
            view[i].push_back(V(V(V(num[0],op[0],num[1]),op[1],num[2]),op[2],num[3])); // 0 1 2
            view[i].push_back(V(V(num[0],op[0],num[1]),op[1],V(num[2],op[2],num[3]))); // 0 2 1
            view[i].push_back(V(V(num[0],op[0],V(num[1],op[1],num[2])),op[2],num[3])); // 1 0 2
            view[i].push_back(V(num[0],op[0],V(V(num[1],op[1],num[2]),op[2],num[3]))); // 1 2 0
            view[i].push_back(V(num[0],op[0],V(num[1],op[1],V(num[2],op[2],num[3])))); // 2 1 0
        }

        /*
        cout << s << endl;
        for (int j=0; j<(int)ke[i].size(); j++) {
            cout << "\t" << view[i][j] << '=' << ke[i][j] << endl;
        }
        */
    }
    map<LL, int> map;
    for (int i=0; i<n; i++) {
        for (LL v: val[i]) {
            if (!map.count(v)) map.insert({v, (int)map.size()});
            ke[i].push_back(map[v]);
        }
    }

    if ((int)map.size() < n) { cout << "NO SOLUTION"; return 0; }
    int cnt = match(n, map.size());
    if (cnt < n) { cout << "NO SOLUTION"; return 0; }
    for (int i=0; i<n; i++) cout << view[i][trace[i]] << '\n';
    return 0;
}
Comments