滴滴笔试

T1等数量的逆序对（100%）

定理：从一个n数量数组中减少数字，逆序对只会减少或不变

然后建图找无边的点，10五次方，直接逆序遍历，如果a[i] == i 并且后面的数都比它大，那么它无边。

然后快速幂求解。

T2 大富翁（100%）

题目描述太多了，不说了，来个uu、评论区补充。核心代码：

int s, n, m, k;
vector<int> a[105];
// 行列变化后
vector<int> b[105];
// 记录到了第ind行后，手里cm钱的情况下，拿到的最大利润。
unordered_map<ll, ll> mp;

ll dfs(int ind, int cm) {
    if (ind == n) return 0;
    ll key = (((ll)ind << 20) | (ll)cm);
    if (mp.find(key) != mp.end()) return mp[key];
    ll ans = 0, ii = 0, cur = 0;
    for (int i = 0; i <= cm; i++) {
        // 当前列花 i 元
        while (ii < s && (i > 2 * b[ind][ii])) {
            ii++;
            cur = cur + ind + 1;
        }
        ans = max(ans, cur + dfs(ind + 1, cm - i));
    }
    return mp[key] = ans;
}

int main()
{
    cin >> s >> n >> m;
    for (int i = 1; i <= s; i++) {
        for (int j = 0; j < n; j++) {
            cin >> k;
            a[i].push_back(k);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= s; j++) {
            b[i].push_back(a[j][i]);
        }
    }
    for (int i = 0; i < n; i++) sort(b[i].begin(), b[i].end());
    ll res = dfs(0, m);
    cout << res << endl;
    return 0;
}