C/C++教程

ARC134

本文主要是介绍ARC134,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

C - The Majority

将a种球放进k个不同的箱子,每种球ni个,第1号球在箱子中球的总数的一半以上问方案总数

因为第1种球的个数在每个箱子站一半以上,故同时去除一个1号球和一个其他球,每个箱子内必剩余有一号球

剩余的一号球个数为 n_1-\sum_{i=2}^{a}n_i

这些球需要放满所有的箱子算出总情况数ans1

然后将剩余的球随意的放入箱子内,总情况数ans2

将两个相乘即可

箱子放球的总结(ans1,ans2的求法已经其他的不同情况

借鉴的是这个博客:排列组合 "n个球放入m个盒子m"问题 总结_qwb的博客-CSDN博客_n个球放入m个盒子定理

1.n个相同球放入m个不同箱子且没有空箱子(ans1)

将n个球分为m段(没有空段),也就是将m-1个隔板插入n-1个空隙中,故答案为

C_{n-1}^{m-1}

/

2.n个相同球放入m个不同箱子且可以有空箱子(ans2)

相当于将m-1个隔板插入n-1个空隙中并且可以同时插入到一个中

就是n-1个物品选m-1次并且选完放回

选m-1次必定放回m-2个,故相当于(n-1+m-2)个物品选m-1次,答案为

C_{n-1+m-2}^{m-1}

/

3.n个不同的球放入m个相同的箱子且没有空箱子

第二类斯特林数

dp[n][m]表示n个球放入m个箱子

对于新加入的一个球,可以在原来箱子已经满的情况下随意放入一个箱子,也可以新开一个箱子放入此球

dp[n][m]=dp[n-1][m]*m+dp[n-1][m-1]

/

4.n个不同的球放入m个相同的箱子且可以空箱

箱子数目随便,故为

\sum_{i=1}^{m}dp[n][i]

/

5.n个不同球放入m个不同的箱子无空箱

每种箱子不一样,答案乘上箱子的全排列,故为

m!*dp[n][m]

/

6.n个不同的球放入m个不同的箱子且可以空箱

将4中的每种情况乘上箱子的全排列即可

\sum_{i=1}^{m}i!*dp[n][i]

或者相当于每个球随便放结果为

n^m

/

E - Modulo Nim

进行一个游戏:每次取出数列中的一个数x,选取一个[1,x]个数并且使序列中每个数对其取模,第一次取出0的人获胜

现在有n个数第i个位ai,构造一个序列b使先手获胜并且ai>=bi

性质1:0的个数对整个序列结果无影响

性质2:相同的数对序列结果无影响

先来判断剩余序列有1,2的情况

{1},{2}先手必败,{1,2}先手必胜(对2取模)

再来判断其他的问题(序列中元素全部大于2)

若序列中有奇数先手必胜(对2取模,剩余为{1})

否则,若序列存在除以4余2的数,先手必胜(对4取模,剩余为{2})

因为只有{1},{2}后手必败,故除数更大时没有其他先手必胜的情况

故序列必败的必要条件是每个数都整除以4

再来判断对3取模的情况

若所有数都余1或都余2,先手必胜

还剩两种情况:余数为{1,2}或余数为0

第一种余数为{1,2}的情况:

要求所有不成立的数量,故集合中每个数需要是4的倍数

可以化简为{12n+4,12k+8}

可以发现,{4,8}是先手必败的

对于n,k中有一个数不为0的情况,可以对其与12取模化为{4,8},故是先手必胜的

还有一种为余数都为0的情况

因为同时为3和4的倍数,故这个数一定是12的倍数

200以内的12的倍数有16个,加上{4,8}一共有18个数,当且仅当出现的数字为这18个数中间的,才有可能是先手必败情况

	memset(id,-1,sizeof(id));
	can.push_back(4),can.push_back(8);
	for(int i=12;i<=200;i+=12) can.push_back(i);
//处理出来所有可能数字
	int gs=can.size();
	for(int i=0;i<gs;i++) id[can[i]]=i;
	win[0]=1;
	for(int x=0;x<(1<<gs);x++){//枚举情况
		now.clear();
		int mx=0;
		for(int i=0;i<gs;i++){
			if(x&(1<<i)) now.push_back(can[i]),mx=max(mx,can[i]);
		}//这种情况使用的数字
		for(int i=1;i<=mx;i++){
			int s1=0,s2=0;
			for(int j=0;j<now.size();j++){
				int res=now[j]%i;
				if(!res) continue;
				if(res==1){
					s1|=(1<<1);continue;
				}
				if(res==2){
					s1|=(1<<2);continue;
				}
				if(id[res]==-1){
					s2=-1;break;
				}
				s2|=(1<<id[res]);
			}
            //先手必胜,意味着后手必败,所以需要找出来对i取模后有没有剩余情况必败
			if(!s2&&(s1==(1<<1)||s1==(1<<2))){//剩余的是1or2
				win[x]=true;
				break;
			}
			if(!s1&&(s2!=-1&&!win[s2])){//剩余的是必败
				win[x]=true;
				break;
			}
		}
	}

用数位dp的方法,先预处理出来这其中的哪些情况先手必败,再做数位dp求出来这种情况出现的总次数,用所有的情况数减去必败的情况数

这是说有数都大于2的情况

对于有数字小于等于2的情况,当且仅当全为1或者全为2时先手必败,特判处理

	dp[0][0]=1;ans=1;
	int cs=1;
	for(int x=1;x<=a;x++){
		ans=1ll*ans*n[x]%mod;
		for(int i=0;i<(1<<gs);i++){
			if(!dp[x-1][i]) continue;
			for(int j=0;j<gs&&can[j]<=n[x];j++){
				dp[x][i|(1<<j)]=(dp[x][i|(1<<j)]+dp[x-1][i])%mod;
			}
		}
		cs=cs*(n[x]>=2?1:0);//
	}//求出每种情况出现总次数
	for(int i=0;i<(1<<gs);i++){
		if(!win[i]) ans=(ans-dp[a][i]+mod)%mod;
	}
    ans-=cs;//全为2
    ans--;//全为1

这篇关于ARC134的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!