abc 332 D

对于一个交换相邻的数（冒泡）形成的排列，逆序对的数量等于最小交换次数
这道题里面，行和列是相对独立的，可以用排列的方法做

尝试用bfs做这道题，每次挑一个行和列交换，有最多 10 种选择，最多为 20 层
那么可以哈希一下，构建一个最短路的问题

这道题的关键，在于改变列的时候不会改变行，改变行的时候不会改变列
也就是说，行里面有哪些东西，不会因为改变列的顺序而改变，同理，列也一样
那么分别考虑行和列就行
但如果想要贪心来得出答案，那么就会 wa * 4，因为交换的时候没法保证先把前面的交换到后面去是最佳的答案
n 很小，可以考虑用暴力
参考官解，需要知道的是排列与贡献的关系，也就是这种问题怎么暴力
暴力用到全排列，两个全排列嵌套，分别表示行的排列和列的排列
如果当前的排列能让 a 与 b 相等（也就是让a的行set和列set与b对应），计算该方法的交换次数
这也是这道题的核心，操作多少次可以让行和列变为这种排列
大概的意思是，计算逆序对的数量
有效交换会制造一个逆序对，无效交换会减少一个逆序对，那最小的交换次数等于逆序对的数量

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int h, w;
    cin >> h >> w;

    vector<vector<int>> a(h, vector<int> (w)), b(h, vector<int> (w));
    for (int i = 0; i < h; i ++)    
        for (int j = 0; j < w; j ++) 
            cin >> a[i][j];

    for (int i = 0; i < h; i ++)    
        for (int j = 0; j < w; j ++) 
            cin >> b[i][j];

    int ans = inf;

    vector<int> p(h), q(w);
    iota(p.begin(), p.end(), 0);
    iota(q.begin(), q.end(), 0);

    do {
        do {
            bool ok = true;
            for (int i = 0; i < h; i ++) 
                for (int j = 0; j < w; j ++) 
                    if (a[p[i]][q[j]] != b[i][j]) 
                        ok = false;

            if (!ok) continue;

            int k = 0;
            for (int i = 0; i < h; i ++)
                for (int j = i + 1; j < h; j ++) 
                    if (p[j] < p[i]) k ++;

            for (int i = 0; i < w; i ++) 
                for (int j = i + 1; j < w; j ++) 
                    if (q[j] < q[i]) k ++;

            ans = min(ans, k);
        } while (next_permutation(q.begin(), q.end()));
    } while (next_permutation(p.begin(), p.end()));

    if (ans == inf) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

abc 331 D

二维前缀和，加上边界处理

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<vector<ll>> a(n + 1, vector<ll> (n + 1)), s(n + 1, vector<ll> (n + 1));
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= n; j ++) {
            char c;
            cin >> c;
            if (c == 'B') a[i][j] = 1;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }

    auto get = [&](int x, int y) {
        return s[n][n] * (x / n) * (y / n) + s[x % n][n] * (y / n) + s[x % n][y % n] + s[n][y % n] * (x / n);
    };

    while (q --) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        c ++, d ++;
        cout << get(c, d) + get(a, b) - get(a, d) - get(c, b) << endl;
    }

    return 0;
}

abc 330 D

一个简单的组合问题，但用set存点，取用siz的话，会导致 TLE 两个
O(n^2 log) n == 2000 没过，只能说是玄学，小概率随机事件

abc 329 D

语法题

abc 328 D

刚开始以为是队列，没有看见是连续子序列，后来发现是栈
不过如果是非连续的子序列的话，开三个队列可以解决，队列中存的是对应字母出现的下标

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s = "ABC";

    string str;
    cin >> str;
    int n = str.size();
    vector<int> stack(n);
    int len = -1;

    for (int i = 0; i < n; i ++) {
        int j = (str[i] == 'A' ? 0 : (str[i] == 'B' ? 1 : 2));
        stack[++ len] = j;
        if (j == 2 && len >= 2 && stack[len - 1] == 1 && stack[len - 2] == 0) len -= 3;
    }

    for (int i = 0; i <= len; i ++) {
        int j = stack[i];
        cout << (j ? (j == 1 ? 'B' : 'C') : 'A');
    }

    cout << endl;

    return 0;
}

abc 327 D

一眼带权并查集，但也可以用一些神奇的方法，比如将 a 和 b + n 在一个集合视为两者对立
也可以建一个图，再用 bfs 读取图，也就是染色问题，从每个点开始，沿着边都染一遍，如果这个图矛盾，则是错误的