Editorial Divide by Zero and Codeforces Round #399 (Div. 1+2, combined) (A~F)

素颜马尾好姑娘i 2022-07-12 11:48 125阅读 0赞

[CF \#399][CF _399]

A题:水题

代码：

#include<bits/stdc++.h>
    using namespace std;
    int a[100010];
    
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++){
    		cin>>a[i];
    		//s.insert(a);
    	}
    	int ans=0;
    	if(n<=2)return 0*printf("%d",0);
    	sort(a,a+n);
    	for(int i=1;i<n-1;i++){
    		if(a[i]>a[0]&&a[i]<a[n-1]){
    		 ans++;
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
    }

B题：二分。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll ans;
    void solve(ll a,ll b,ll l, ll r, ll d)
    {
    	if(a > b || l > r) return;
    	else{
    		ll mid=(a+b)/2;
    		if(r < mid)solve(a,mid-1,l,r,d/2);
    		else if(mid < l)solve(mid+1,b,l,r,d/2);
    		else{
    			ans += d%2;
    			solve(a,mid-1,l,mid-1,d/2);
    			solve(mid+1,b,mid+1,r,d/2);
    		}
    	}
    }
    int main()
    {
    	ll n,l,r,sum=1;
    	cin>>n>>l>>r;
    	ll t=n;
    	while(t>=2)
    	{
    		t/=2;
    		sum=sum*2+1;
    	}
    	solve(1,sum,l,r,n);
    	cout<<ans<<endl;
    	return 0;
    }

C题：模拟，经过若干个操作后其序列会稳定不变。

代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int a[maxn];
    int L[maxn],S[maxn];
    int main()
    {
    	int n,k,x;
    	cin>>n>>k>>x;
    	for(int i=0;i<n;i++)cin>>a[i];
    	sort(a,a+n);
    	for(int i=0;i<k;i++){
    		for(int j=0;j<n;j++){
    			if(j%2==0)
    			a[j]=a[j]^x;
    		}
    		sort(a,a+n);
    		S[i]=a[0];
    		L[i]=a[n-1];
    		//经过若干轮操作就会稳定 
    		if(i>=2)
    		if(S[i]==S[i-1]&&S[i]==S[i-2]&&L[i]==L[i-1]&&L[i]==L[i-2])
    		break;
    		
    	}
    	cout<<a[n-1]<<" "<<a[0]<<endl;
    	return 0;
    }
    /*
    5 1 2
    9 7 11 15 5
    
    13 7
    */

D题：概率DP。

总共有k种物品，每天产生一种物品（等概率）。问至少需要几天才能保证收集齐K种物品的概率超过(p - 1e-7)/2000。

设dp \[ i \]\[ j \] 表示前 i 天总共得到了 j 种物品的概率。

那么转移方程为：dp\[i\]\[j\]=(dp\[i-1\]\[j\] \* j + dp\[i-1\]\[j-1\] \* (k-j+1))/k

详细看代码。

代码：

#include<bits/stdc++.h>
    using namespace std;
    double dp[10005][1005];
    //总共有k种物品，每天产生一种物品（等概率）。
    //问至少需要几天才能保证收集齐K种物品的概率超过(p - 1e-7)/2000
    int main()
    {
    	int k,q;
    	cin>>k>>q;
    	dp[0][0]=1.;
    	for(int i=1;i<=10000;i++){
    		for(int j=1;j<=k;j++)
    		//dp[i][j] 表示前i天总共得到了j种物品的概率
    		dp[i][j]=(dp[i-1][j] * j + dp[i-1][j-1] * (k-j+1))/k;
    	}
    	int p;
    	while(q--){
    		cin>>p;
    		int i=1;
    		int ans=0;
    		while(dp[i][k]*2000 + 1e-7 < p )
    		{
    			i++;
    		}
    		cout<<i<<endl;	
    	}
    	return 0;
    }
    /*
    3 5
    1
    4
    20
    50
    300
    
    3
    3
    3
    3
    3
    */

E题：Nim博弈。

代码：

#include<bits/stdc++.h>
    using namespace std;
    int sg[100010];
    int main()
    {
    	int n;
    	int st=0;
    	cin>>n;
    	for(int i=1;i<=100;i++){
    		for(int j=1;j<=i+1;j++){
    			sg[++st]=i;//状态数：1+2+3+...+n=n(n+1)/2 
    		}
    	}
    	int ans=0;
    	while(n--){
    		cin>>st;//1<=st<=60
    		ans^=sg[st];
    	}
    	if(ans==0)cout<<"YES"<<endl;
    	else cout<<"NO"<<endl;
    	return 0;
    }

F题：组合数学+费马小定理+逆元

详细看代码。

官方题解：

Every arrangement of stacks can expressed in the form of linear arrangement. In this linear arrangement, every contiguous segment of wine barrels are separated by food boxes. For the arrangement to be liked by Jon each of the *f* + 1 partitions created by *f* food boxes must contain either 0 or greater than *h* wine barrels.

Let *u* out of *f* + 1 partitions have non-zero wine barrels then the remaining *r* + 1 - *u* partitions must have 0 wine barrels..

Total number of arrangements with exactly u stacks of wine barrels are ![75e3aa80e8fe1bbb26bbd2ad749af6a87bcfa0a1.png][]  
![ccebfd63f39ea76c07de8b60d7761f3fab44e7a6.png][] is the number of ways of choosing *u* partitions out of *f* + 1 partitions.  
*X* is the number of ways to place *w* wine barrels in these *u* partitions which is equal to the coefficient of *x**w* in \{ *x**h* + 1·(1 + *x* + ...)\}*u*. Finally we sum it up for all *u* from 1 to *f* + 1.

So the time complexity becomes *O*(*w*) with pre-processing of factorials.

***w* = 0 was the corner case for which the answer was 1.  
We did not anticipate it will cause so much trouble. Not placing it in the pretests was a rookie mistake.**

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    const int mod=1e9+7;
    ll fac[maxn],inv[maxn];
    ll q_mod(ll a,ll n)
    {
    	ll res=1;
    	while(n){
    		if(n&1)res=res*a%mod;
    		n>>=1;
    		a=a*a%mod;	
    	}
    	return res;
    }
    ll C(ll n,ll m)//C(n,m)
    {
    	if(n<m)return 0;
    	return fac[n]*inv[m] % mod * inv[n-m] %mod;
    }
    int main()
    {
    	 
    	fac[0]=1;
    	for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod;
    	
    	inv[maxn-1]=q_mod(fac[maxn-1],mod-2);
    	
    	for(int i=maxn-2;i>=0;--i){
    		inv[i]=inv[i+1]*(i+1)%mod;
    	}
    	ll f,w,h;
    	cin>>f>>w>>h;
    	if(w==0)return 0*puts("1");//特判... 
    	ll a=0,b=0;
    	for(int i=1;i<=w;i++){ 
    		b=(b + C(w-1-i*h,i-1) * C(f+1,i) )%mod;//符合要求的情况
    		a=(a + C(w-1,i-1) * C(f+1,i) )%mod;//全部情况 
    	}	
    	//cout<<b<<endl;
    	//cout<<a<<endl;
    	// 概率为：b/a
    	cout<<b * q_mod(a,mod-2)%mod<<endl;
    	return 0;
    }

G题：。。。

不会。。。

[CF _399]: http://codeforces.com/contest/768
[75e3aa80e8fe1bbb26bbd2ad749af6a87bcfa0a1.png]: /images/20220710/ffa7056f86b544069b4e376b46bd0457.png
[ccebfd63f39ea76c07de8b60d7761f3fab44e7a6.png]: /images/20220710/bef95b5cd1624d4fa7380d59dcdd8f43.png