# Thầy Đông (13/06/2023)
## [Đề bài](https://1drv.ms/b/s!Ao2gYQsApYcg8Vudk4koWqPhxGiU?e=jCYnJ1)

## Bài 2:
### Sub 1: Duyệt nhị phân
### Sub 2: Duyệt nhị phân chia đôi tập
### Sub 3: DP knapsack
### Sub 4: Dễ
### Sub 5: Thử cộng các $w_i$ vào tổng hiện tại, với $i$ chạy từ $n$ về $1$.
### Sub 6:
* Sắp xếp dãy $w$ theo thứ tự từ bé đến lớn.
* Tìm số $k$ sao cho tổng của $k$ số hạng nhỏ nhất bé hơn $r$ và tổng của $k$ số hạng lớn nhất lớn hơn $l$.
* Vì hai tổng trên chênh nhau không quá $w_n - w_1$, tức là không quá $r - l$, suy ra tồn tại một tổng của $k$ số liên tiếp thỏa mãn đề bài.
* Độ phức tạp: $\mathcal{O}(n)$.
* Code:

const int maxn = 2e5 + 10;
int n, l, r;
pair<int,int> w[maxn];

void solve()
{
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        cin >> w[i].first;
        w[i].second = i;
    }
    sort(w + 1, w + n + 1);
    for (int i = 1; i <= n; i++) {
        w[i].first += w[i - 1].first;
    }
    int k;
    for (k = 1; k <= n; k++) {
        if (w[k].first <= r && w[n].first - w[n - k].first >= l) break;
    }
    for (int i = 0; i <= n; i++) {
        if (w[k + i].first - w[i].first >= l
         || w[k + i].first - w[i].first <= r) {
            cout << k << '\n';
            for (int j = i + 1; j <= i + k; j++) {
                cout << w[j].second << ' ';
            }
            cout << '\n';
            return;
        }
    }
}

___

## Bài 3
### Sub 1: Cây khung nhỏ nhất
### Sub 2 $\rightarrow$ 4: DP bitmask
* $dp[u][mask]$ là tới đỉnh $u$ và đã đi qua các đỉnh trong $mask$ thì tốn ít nhất bao nhiêu tiền.
* Code:

priority_queue<pair<int,pair<int,int> >, 
                vector<pair<int,pair<int,int> > >, 
                greater<pair<int,pair<int,int> > > > pq;

void solvet1()
{
    memset(dp, 60, sizeof dp); // memset dp bằng vô hạn
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0;
        if (imp[i] != -1) { // i là đỉnh đặc biệt
            dp[i][1 << imp[i]] = 0; // imp[i] chứa thứ tự của đỉnh i 
                                    // trong các đỉnh đặc biệt
        }
    }
    
    for (int mask = 0; mask < (1 << k); mask++) {
        while (!pq.empty()) pq.pop();
        for (int m1 = 0; m1 < (1 << k); m1++) {
            if ((m1 | mask) != mask) continue; // m1 là bit con của mask
            int m2 = m1 ^ mask;
            for (int i = 1; i <= n; i++) {
                mini(dp[i][mask], dp[i][m2] + dp[i][m1]);
            }
        }
        
        for (int i = 1; i <= n; i++) 
            pq.push(make_pair(dp[i][mask], make_pair(i, mask)));
        
        while (!pq.empty()) {
            int w = pq.top().first;
            int u = pq.top().second.first;
            int mask = pq.top().second.second;
            pq.pop();
            if (w != dp[u][mask]) continue;
            for (auto [v, w] : adj[u]) {
                if (mini(dp[v][mask], dp[u][mask] + w)) {
                    pq.push(make_pair(dp[v][mask], make_pair(v, mask)));               
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        mini(res, dp[i][(1 << k) - 1]);
    }
    cout << res << '\n';
}

### Sub 5:
* Ta sẽ tìm cây khung nhỏ nhất mà chỉ đi qua một số các đỉnh đặc biệt.
* Vì $k \leq 10$ nên ta có thể thử tìm cây khung với tất cả các tập con của các đỉnh đặc biệt.
* Code:

struct Edge
{
    int u, v, w;
    Edge(int u = 0, int v = 0, int w = 0) {
        this->u = u, this->v = v, this->w = w;
    }
    bool operator < (const Edge &e) const {
        return w < e.w;
    }
};

vector<Edge> E;

void solvet2()
{
    sort(E.begin(), E.end());
    for (int mask = 0; mask < (1 << k); mask++) {
        memset(visited, 0, sizeof visited);
        memset(par, 0, sizeof par);
        int cur = 0;

        for (Edge &e : E) {
            if ((imp[e.u] == -1 || bit(mask, imp[e.u]))
             && (imp[e.v] == -1 || bit(mask, imp[e.v]))) {
                if (merge(e.u, e.v)) {
                    visited[e.u] = true;
                    visited[e.v] = true;
                    cur += e.w;
                }
             }
        }

        bool ok = true;
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && imp[i] == -1) {
                ok = false;
                break;
            }
        }

        if (ok) {
            mini(res, cur);
        }
    }
    cout << res << '\n';
}

## Bài 4
### Cách dựng đồ thị thỏa mãn yêu cầu đề bài:
* Ta sẽ chia bản đồ vương quốc thành các lớp:
* Lớp $1$ gồm các thành phố từ $2$ $\rightarrow$ $7$.
* Lớp $2$ gồm các thành phố từ $8$ $\rightarrow$ $19$.
$...$
* Ta thấy các lớp sau sẽ hơn lớp trước $6$ thành phố.
* Giờ ta sẽ tìm cách nối các đỉnh trong một lớp và các đỉnh của lớp sau với lớp trước.
* Với các đỉnh vàng thì sẽ liên kết với $1$ đỉnh ở dưới.
* Còn các đỉnh còn lại thì sẽ liên kết với $2$ đỉnh ở dưới.
* Code:

void addEdge(int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void init()
{
    for (int lay = 1, st = 2, mid = 2; lay <= n; lay++) {
        int siz = lay * 6;
        int en = st + siz - 1;
        // lay là thứ tự của lớp
        // siz là số lượng đỉnh trong lớp
        // st là đỉnh đầu tiên của lớp
        // en là đỉnh cuôi cùng trong lớp
        // mid là đỉnh vàng đầu tiên của lớp
        for (int i = st, cur = st - 1; i <= en; i++) {
            // cur là đỉnh cuối cùng của lớp trước
            addEdge(i, (i - st + 1) % siz + st); 
            // nối i với đỉnh liền sau i
            addEdge(i, cur);
            if ((i - mid) % lay != 0) { // i không phải đỉnh vàng
                cur = (cur - (st - (siz - 6) - 1)) % (siz - 6) + st - siz + 6; 
                // chuyển cur thành đỉnh liền sau cur
                addEdge(i, cur);
            }
        }
        st += siz;
        mid += siz + 1;
    }
}

### Còn lại ý tưởng bài này giống với sub 2 $\rightarrow$ 4 của bài 3.
* Code:

void solve()
{
    cin >> n >> t;
    m = 3 * n * (n + 1) + 1;
    for (int i = 1; i <= m; i++) cin >> val[i];
    init();
    memset(dp, 60, sizeof dp);
    memset(imp, -1, sizeof imp);
    for (int i = 1; i <= m; i++) dp[i][0] = val[i];
    for (int i = 0; i < 6; i += (3 - t)) {
        imp[m - i * n] = i;
        dp[m - i * n][1 << i] = val[m - i * n];
        dp[m - i * n][0] = oo;
    }
    for (int mask = 1; mask < (1 << 6); mask++) {
        for (int m1 = 0; m1 < mask; m1++) {
            if ((m1 | mask) != mask) continue;
            int m2 = m1 ^ mask;
            for (int i = 1; i <= m; i++) {
                if (imp[i] == -1) {
                    mini(dp[i][mask], dp[i][m1] + dp[i][m2] - val[i]);
                }
                else mini(dp[i][mask], dp[i][m1] + dp[i][m2] - val[i]);
            }
        }
        priority_queue<pair<int, int>, 
                       vector<pair<int, int>>, 
                       greater<pair<int,int> > > pq;
        for (int i = 1; i <= m; i++) {
            pq.push(make_pair(dp[i][mask], i));
        }
        while (!pq.empty()) {
            auto [w, u] = pq.top();
            pq.pop();
            if (w != dp[u][mask]) continue;
            for (int v : adj[u]) {
                if (mini(dp[v][mask], w + val[v])) {
                    pq.push(make_pair(dp[v][mask], v));
                }
            }
        }
    }
    int need = (t == 1) ? 21 : 63;
    for (int i = 1; i <= m; i++) {
        mini(res, dp[i][need]);
    }
    cout << res << '\n';
}