题解：P14745 [ICPC 2021 Seoul R] Trio

· · 题解

感觉最多是一道黄，代码不难，思路也简单。

题意

很简单。不再赘述。

思路

最朴素的方法：三重循环，显然时间是崩了的。

由于每一位要么相同，要么不同，所以如果遍历一个数字，就可以之便利一些数组。简单来说，就是物以类聚。

我们可以通过一个四维数组来统计这一类的数字有几个。

然后，我们只用去遍历两个数字，看它们的每一位是相同还是不相同，从而判断第三个数字的可能性。

这样，时间复杂度就成功降到了 \mathcal{O}(n^2)，也就可以接受了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, ans, a[3005][5], cnt[11][11][11][11], h[5];
string s;
inline int find(int c, int x[], int y[], int z[]) { //按位查询，inline减少花销
    int sum = 0;
    if (c == 4) {
        sum += cnt[z[0]][z[1]][z[2]][z[3]]; //查到第四位了，果断终结
    } else if (x[c] == y[c]) { //一样
        z[c] = x[c];
        sum += find(c + 1, x, y, z);
    } else { //搜索找
        z[c] = 0;
        sum += find(c + 1, x, y, z);
        z[c] = x[c];
        sum -= find(c + 1, x, y, z);
        z[c] = y[c];
        sum -= find(c + 1, x, y, z);
    }
    return sum;
}
signed main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> s;
        for (int j = 0; j < 4; j++) { //转为数字串
            a[i][j] = s[j] - '0';
        }
        for (int j1 = 0; j1 < 2; j1++) { //遍历每一位，统计一样不一样的个数
            for (int j2 = 0; j2 < 2; j2++) {
                for (int j3 = 0; j3 < 2; j3++) {
                    for (int j4 = 0; j4 < 2; j4++) {
                        cnt[j1*a[i][0]][j2*a[i][1]][j3*a[i][2]][j4*a[i][3]]++;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= t; i++) { //对于每一个字符串，处理它的三元组
        for (int j = i + 1; j <= t; j++) {
            ans += find(0, a[i], a[j], h); //一位一位查询
        }
    }
    cout << ans / 3; //处理重复
    return 0;
}

后记

由于蒟蒻码力不在线，参考了另外两篇题解的代码，再次表示感谢。