当前位置：网站首页>牛客白月赛5 【题解数学场】

牛客白月赛5 【题解数学场】

2022-04-22 06:58:00 【辉小歌】

数学场
https://ac.nowcoder.com/acm/contest/135#question

无关(relationship)【容斥】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=25;
LL l,r,n,a[N];
LL solve(LL x)
{
    
	LL sum=0;
	for(int i=1;i<(1<<n);i++)
	{
    
		LL temp=x,cnt=-1;
		for(int j=0;j<n;j++)
		{
    
			if((i>>j)&1==1) temp/=a[j],cnt=cnt*(-1);
		}
		sum=sum+cnt*temp;
	}
	return x-sum;
}
int main(void)
{
    
	cin>>l>>r>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	cout<<solve(r)-solve(l-1);
	return 0;
}

范围(range)【不会】

水题(water)【不会】

阶乘(factorial)【思维末尾0的个数】

在这里插入图片描述
2*5==10 2的个数一定大于5的个数。故就是求5的个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL sum,n,cnt;
int main(void)
{
    
	cin>>n;
	for(int i=1;i<=n;i++)
	{
    
		int j=i;
		while(j%5==0) cnt++,j/=5;
		sum+=cnt;
	}
	cout<<sum;
	return 0; 
}

面积(area)【不会】

圆(circle)【n个点将圆分成几部分】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main(void)
{
    
	LL n;
	while(cin>>n)	
	{
    
		LL sum=0;
		if(n>=4) sum+=n*(n-1)*(n-2)*(n-3)/4/3/2;
		if(n>=2) sum+=n*(n-1)/2;
		sum++;
		cout<<sum<<endl;
	}
	return 0; 
}

异或(xor)

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL n;
int main(void)
{
    
	while(scanf("%lld",&n)!=-1) printf("%lld\n",n/3*2+n%3);
	return 0;
}

最大公约数(lcm)

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;}
int main(void)
{
     
	LL a,b; cin>>a>>b;
	cout<<a/gcd(a,b)*b;
	return 0;
}

区间 (interval)【差分】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N=1e6*3+10;
typedef long long int LL;
LL n,m,x,a[N];
void add(int l,int r,int x)
{
    
	a[l]+=x;
	a[r+1]-=x;	
}
int main(void)
{
     
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>x,add(i,i,x);
	while(m--)
	{
    
		LL op,l,r,p; cin>>op>>l>>r>>p;
		if(op!=1) add(l,r,p);
		else add(l,r,-p);
	}
	for(int i=1;i<=n;i++) a[i]+=a[i-1];
	LL sum=0,l,r;
	cin>>l>>r;
	for(int i=l;i<=r;i++) sum+=a[i];
	cout<<sum<<endl;
	return 0;
}

时间(time)【模拟】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
bool check(int x,int y)
{
    
	int a1=x/10,a2=x%10;
	int b2=y/10,b1=y%10;
	if(a1==b1&&a2==b2) return true;
	return false;
}
int main(void)
{
    
	string s; cin>>s;
	int a,b;
	a=stoi(s.substr(0,s.find(':')));
	b=stoi(s.substr(s.find(':')+1));
	int x=0,y=0;
	for(int i=0,j=0;;j++)
	{
    
		if(j==60) j=0,i++;
		if(i==a&&j==b) break;
		if(check(i,j)) x=i,y=j;
	}
	printf("%d:%d\n",x,y);
	x=0,y=0;
	for(int i=a,j=b+1;;j++)
	{
    
		if(j==60) j=0,i++;
        if(i==24) break;
		if(check(i,j)) 
        {
    
            x=i,y=j;
            break;
        }
	}
	printf("%d:%d\n",x,y);
	return 0;
}