TX的笔试难度还是挺大的，尤其是第2题和第3题。不过TX并不生产算法题，它只是算法题的搬运工。

2. 寻找2个点集中最近的对

原题链接
大雪菜提供了视频讲解。简而言之，就是把2个点集的点分别做个标记，然后利用一个点集内找最近对的算法（不同标记的点，相当于无穷远）。一个点集内找最近对就是一个十分经典的问题了，采用分治可以解决。

时间复杂度: O(N log N), 空间复杂度: O(N).

2. 卡牌翻转

原题 Swap and Flip

动态规划。DP[mask][i]表示mask中的牌在最左边，第i个牌在这些牌中的最后，保证非降的最小操作数。

时间复杂度: O(n^2 * 2^n),
空间复杂度: O(n * 2 ^ n)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 0x3f3f3f3f;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }
    vector<vector<int>> dp((1 << N), vector<int>(N, INF));
    // dp[mask][i]: the minimum operation when cards in mask are in leftmost and the ith card is in the end
    for (int i = 0; i < N; ++i) {
        dp[1 << i][i] = 0;  // there is no card in leftmost whose id larger than i
    }
    for (int s = 0; s < (1 << N); ++s) {
        for (int i = 0; i < N; ++i) {
            if (((s >> i) & 1) == 0)
                continue;                  // i is not in state
            int c = __builtin_popcount(s); // card number in s
            int value_i = (c % 2) == (i % 2) ? B[i] : A[i];
            int cost = c; // the number of card in s, whose id is larger than j
            for (int j = 0; j < N; ++j) {
                if (((s >> j) & 1) == 1) {
                    --cost;
                    continue; // j is in state already
                }
                int value_j = (j % 2) == (c % 2) ? A[j] : B[j];
                if (value_j >= value_i) {
                    dp[s | (1 << j)][j] =
                        min(dp[s | (1 << j)][j], dp[s][i] + cost);
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < N; ++i) {
        ans = min(ans, dp[(1 << N) - 1][i]);
    }
    ans = ans >= INF ? -1 : ans;
    cout << ans << endl;
    return 0;
}