Cowpatibility
· 阅读需 2 分钟
首先入手点肯定是在于每个牛冰淇淋数量只有上面,所以我们可以很容易想到容斥
然后现在问题在与怎么寻找对应的状态
然后......
我是
我写一堆的套来存,直接
这里的处理是将组合处理成字符串形式,也能保证一一对应,那么就好做了
时间复杂度:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define QAQ return
const int N=5e4+10;
string a[5];
unordered_map< string,int > mp;
int main()
{
// freopen( "1.in","r",stdin );
// freopen( "1.out","w",stdout );
ios::sync_with_stdio( false );
cin.tie( nullptr ); cout.tie( nullptr );
int n;
cin>>n;
ll ans=1ll*( n-1 )*n>>1;
for( int i=1;i<=n;i++ )
{
for( int j=0;j<5;j++ ) cin>>a[j];
sort( a,a+5 );
for( int state=1, popc=0;state<( 1<<5 );state++ )
{
string s=""; popc=0;
for( int bit=0;bit<5;bit++ ) if( ( state>>bit )&1 )
s+=a[bit]+' ', popc++;//记得加空格
if( popc&1 ) ans-=mp[s];
else ans+=mp[s];
mp[s]++;
}
}
cout<<ans;
QWQ
}
