首页 > 其他分享 >Topcoder 10880 - Rabbit Problemming

Topcoder 10880 - Rabbit Problemming

时间:2023-04-16 20:25:12浏览次数:45  
标签:55 mn 兔子 mx rd points 10880 Topcoder Problemming

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

首先,我们考虑一只兔子可以达到的最大值 \(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

标签:55,mn,兔子,mx,rd,points,10880,Topcoder,Problemming
From: https://www.cnblogs.com/jucason-xu/p/17323953.html

相关文章

  • Topcoder 10880 - Functional Equation
    首先分析一下这个鬼畜的函数,我们考虑\(f(x)+2C\)\(=f(2f(x)-x+1)+C\)\(=f(2f(2f(x)-x+1)-(2f(x)-x+1)+1)\)\(=f(2(f(x)+C)-2f(x)+x-1+1)\)\(=f(x+2C)\)也就是\(f(x)=f(x\bmod2C)+2C\lfloor\dfrac{x}{2C}\rfloor\)也就是,只要决定了\(f(x)\),\(f(x+2mC)\)也就被确定了。......
  • 题解 Topcoder SRM789 FollowingNim
    题目链接题意给定\(n\)堆石子\(a_1,a_2,\cdots,a_n\)和一个集合\(S\),两名玩家轮流行动,每次可以在某堆石子中取走\(x\)个(不能不取)。特殊地,如果\(x\inS\),那么下......
  • TopCoder14563 DerangementsStrikeBack
    使用类似传统的错排公式\(D(n)=(n-1)\times(D(n-1)+D(n-2))\)的推导过程。首先,\(D_i\)整体除了一个\(n!\),代表后\(n\)个球整体相同。局面设定为求\(......