Topcoder 10880 - Rabbit Problemming

发布时间 2023-04-16 20:13:04作者: jucason_xu

\[兔子,兔子,兔子 \]

首先,我们考虑一只兔子可以达到的最大值 \(mx_i\) 和最小值 \(mn_i\),这个可以很方便的求出来。并且每只兔子的取值是独立的。

然后,如果一个组合能被选中,那么在这个组合内部所有的兔子都取 \(mx_i\),其他的兔子都取 \(mn_i\) 的时候一定也能被选中。我们就钦定所有选的组合都是这种情况。

接下来,我们枚举这个组合内排名最低的兔子,然后把剩下的兔子分成三类,一定比它大的,既可以比它大也可以比它小的,一定比它小的。

第三类就完全不用考虑了,然后枚举在第一类种选多少,在第二类中选多少。选的个数要满足第二类选的个数加上第一类的总个数不超过 \(qualified-1\),否则当前兔子就选不了了。

预处理组合数,乘起来即可。

class RabbitProgramming{
public:
	ll C[55][55],mx[55],mn[55];
	void init(){
		rep(i,0,50){
			C[i][0]=1;
			rep(j,1,i){
				C[i][j]=C[i-1][j]+C[i-1][j-1];
			}
		}
	}
	ll getTeams(vt<int>points,vt<string>standings,int qualified,int selected){
		init();
		int n=points.size(),m=standings.size();
		rd(i,m)rd(j,n)if(standings[i][j]=='Y'){
			if(points[j]>0)mn[i]+=points[j],mx[i]+=points[j];
			else mx[i]-=points[j];
		}
		ll ans=0;
		rd(i,m){
			int a=0,b=0;
			rd(j,m)if(i!=j){
				if(mn[j]>mx[i]||(mn[j]==mx[i]&&j<i))a++;
				else if(mx[j]>mx[i]||(mx[j]==mx[i]&&j<i))b++;
			}
			rep(x,0,a){
				int y=selected-x-1;
				if(y<0)continue;
				if(y+a>=qualified)continue;
				if(y>b)continue;
				ans+=C[a][x]*C[b][y];
			}
		}return ans;
	}
};
//Crayan_r