当前位置: 代码迷 >> 综合 >> 【分析】AGC012D Colorful Balls
  详细解决方案

【分析】AGC012D Colorful Balls

热度:61   发布时间:2023-09-27 05:42:56.0

分析:

有点水的分析题。

很显然,对每种颜色而言,其如果能和最小的交换,就一定能和所有能交换的交换。

因此,我们可以把所有wi+wj≤xw_i+w_j\leq xwi?+wj?x(i,j同色),那么wi=min(wi,wj)w_i=min(w_i,w_j)wi?=min(wi?,wj?)

这样搞完之后,再看看异色交换,也是一样的道理,它能和最小的换,就能和所有能换的换。另外,要注意最小颜色和它同色的情况(这种情况只能同色换)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 400010
#define MOD 1000000007
#define INF 0x3FFFFFFF
using namespace std;
typedef long long ll;
ll c[MAXN],w[MAXN],col[MAXN];
ll n,x,y,cnt;
vector<ll> a[MAXN];
ll fac[MAXN],ifac[MAXN];
ll fsp(ll d,ll t){ll res=1;while(t){if(t&1ll)res=res*d%MOD;d=d*d%MOD;t>>=1ll;	}return res;
}
int main(){SF("%lld%lld%lld",&n,&x,&y);ll mminw=INF;int minc;for(ll i=1;i<=n;i++){SF("%lld%lld",&c[i],&w[i]);a[c[i]].push_back(i);if(w[i]<mminw){mminw=w[i];minc=c[i];	}}ll mminw1=INF;for(ll i=1;i<=n;i++){ll minw=INF;for(ll j=0;j<ll(a[i].size());j++)	minw=min(minw,w[a[i][j]]);for(ll j=0;j<ll(a[i].size());j++)if(w[a[i][j]]+minw<=x)w[a[i][j]]=minw;if(minc!=i)mminw1=min(mminw1,minw);}for(ll i=1;i<=n;i++){if(c[i]==minc){if(w[i]+mminw1<=y){col[c[i]]++;cnt++;	}}else if(w[i]+mminw<=y){col[c[i]]++;cnt++;}}fac[0]=1;for(ll i=1;i<=cnt;i++)fac[i]=fac[i-1]*i%MOD;ifac[cnt]=fsp(fac[cnt],MOD-2);for(ll i=cnt;i>=1;i--)ifac[i-1]=ifac[i]*i%MOD;ll ans=fac[cnt];for(ll i=1;i<=n;i++)ans=ans*ifac[col[i]]%MOD;PF("%lld",ans);
}