[USACO18DEC]Cowpatibility
发布时间:2020-12-14 04:37:53 所属栏目:大数据 来源:网络整理
导读:Description: Farmer John 的 (N) 头奶牛( (2le Nle 5times 10^4) )各自列举了她们最喜欢的五种冰激凌口味的清单。为使这个清单更加精炼,每种可能的口味用一个不超过 (10^6) 的正整数 (texttt{ID}) 表示。如果两头奶牛的清单上有至少一种共同
Description:Farmer John 的 (N) 头奶牛((2le Nle 5times 10^4))各自列举了她们最喜欢的五种冰激凌口味的清单。为使这个清单更加精炼,每种可能的口味用一个不超过 (10^6) 的正整数 (texttt{ID}) 表示。如果两头奶牛的清单上有至少一种共同的冰激凌口味,那么她们可以和谐共处 Solution:由于只有五种冰激凌,我们可以考虑容斥,对于每头奶牛和它与之前的所有奶牛枚举交集 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=1e5+5,inf=1e9; int n;string a[15],s; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(int &x,int y) {if(x<y) x=y;} inline void chkmin(int &x,int y) {if(x>y) x=y;} map<string,ll > f; int main() { scanf("%d",&n); ll ans=1ll*n*(n-1)/2; for(int i=1;i<=n;++i) { for(int j=1;j<=5;++j) cin>>a[j]; sort(a+1,a+6); ll res=0; for(int j=1;j<32;++j) { int cnt=0; s=""; for(int k=1;k<=5;++k) if(j&(1<<(k-1))) ++cnt,s+="?"+a[k]; if(cnt&1) res+=f[s]; else res-=f[s]; ++f[s]; } ans-=res; } printf("%lld",ans); return 0; } 神奇的暴力: #include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=2e5+5; int n,a[mxn][6]; inline int read() { char c=getchar(); int x=0,int y) {if(x>y) x=y;} map<int,bitset<mxn> > bit; int main() { n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=5;++j) bit[a[i][j]=read()].set(i); int ans=0; bitset<mxn> tp; for(int i=1;i<=n;++i) { tp.reset(); for(int j=1;j<=5;++j) tp|=bit[a[i][j]]; ans+=n-tp.count(); } cout<<ans/2; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |