标签：hash Cowpatibility int ret rm USACO18DEC 奶牛 omega

前言

想想自己做, 一共就两种 \(\rm{trick}\) 还不会?

思路

你发现两个不能和谐共处的奶牛, 当且仅当他们的 \(10\) 个喜好不重
因为要求时间复杂度不能是 \(\mathcal{O} (n^2)\) , 所以肯定要想办法做到不枚举点对

这个时候联想到之前的一道题 [CEOI2010 day2] pin, 我们考虑利用相似的方法 (结果之前那题是水过去的, 又去研究了一遍花费 \(10 \ \rm{min}\))

我们考虑「钦定」当前这只奶牛的 \(k\) 个喜好与其他奶牛相同, 这个时候我们可以轻松的 \(\mathcal{O}(1)\) 统计出有多少只, 仅仅需要使用 \(\rm{hash}\)
其中统计的总时间复杂度是 \(\mathcal{O} (2^{\omega} n)\) , 其中 \(\omega = 5\)

这不无敌了, 你发现令 \(f(k)\) 为「至多」\(k\) 个喜好与其他奶牛不同的对数, 可以快速计算出来 (即「钦定」\(\omega - k\) 个位置相同), 套路的, 令 \(g(k)\) 为「恰好」\(k\) 个喜好与其他奶牛不同的对数

\[f(k) = \sum_{i = 0}^{k} {\omega - i \choose \omega - k} g(i) \iff g(k) = \sum_{i = 0}^{k} (-1)^{k - i} {\omega - i \choose \omega - k} f(i) \]

容易发现

\[ans \gets g(\omega) = \sum_{i = 0}^{\omega} (-1)^{i + 1} f(i) \]

实现

\(\rm{TJ}\) 区并没有这种做法, 只能自己多考虑一下打出来了

框架

首先是计算 \(f\)
我们需要在枚举的过程中, 用二进制枚举的方式处理相同的喜好集合, 然后统计进 \(\rm{hash}\)

6, 注意到不能用 \(\rm{vector}\) , 而应该使用 \(\rm{set}\)

代码

#include <bits/stdc++.h>
#define int long long
const int MAXN = 5e4 + 20;

int n;
int cows[MAXN][5];

std::map<std::set<int>, int> hash; // 映射 hash

int f[6];
/*计算 f(i)*/
void fcalc() {
    for (int i = 1; i <= n; i++) for (int s = 0; s < 32; s++) { // 枚举位置 / 状态
        std::set<int> ret; ret.clear(); for (int j = 0; j < 5; j++) if ((s >> j) & 1) ret.insert(cows[i][j]);
        f[5 - __builtin_popcount(s)] += hash[ret]; hash[ret]++;
    }
}

signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) for (int j = 0; j < 5; j++) scanf("%lld", &cows[i][j]);

    fcalc();
    int ans = 0;
    for (int i = 0; i <= 5; i++) {
        ans += (i % 2 ? 1ll : -1ll) * f[i];
    }
    printf("%lld", ans);

    return 0;
}

总结

很像啊, 基本上逻辑相通

也算是常见 \(\rm{trick}\) , 本质上是观察到用 \(\rm{hash}\) 计算对数可以做到更快, 而且只有 \(\omega = 5\) 方便处理子集

标签：hash,Cowpatibility,int,ret,rm,USACO18DEC,奶牛,omega
From： https://www.cnblogs.com/YzaCsp/p/18648699