本文主要是介绍牛客小白月赛5 H J I D G A F,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
https://www.nowcoder.com/acm/contest/135#question
以下题目都需要注意会不会爆long long 会不会c++输入输出超时以及 “ ~ ”
H
求a和b的最小公倍数,a*b/gcd(a,b)
#include<bits/stdc++.h>
using namespace std;
long long a[1111111];
unsigned long gcd(unsigned long a,unsigned long b)
{if(b==0)return a;else return gcd(b,a%b);
}
int main(){unsigned long a,b;while(cin>>a>>b){unsigned long c=gcd(max(a,b),min(a,b));unsigned long ans=b/c; //要先除 否则a*b会爆范围ans=ans*a;cout<<ans<<endl;}return 0;
}
J
模拟一下!
#include<bits/stdc++.h>
using namespace std;
int main(){int a,b;char s;while(cin>>a>>s>>b){int hour=a;int mint=b;int ans1;int ans2;int ans3;int ans4;while(1){mint--;if(mint<0){mint=59;hour--;if(hour<0)hour=23;}if(mint/10==hour%10&&mint%10==hour/10){ans1=hour;ans2=mint;break;}}hour=a;mint=b;while(1){mint++;if(mint>=60){mint=0;hour++;if(hour==24){hour=0;}}if(mint/10==hour%10&&mint%10==hour/10){ans3=hour;ans4=mint;break;}}cout<<ans1<<":"<<ans2<<endl<<ans3<<":"<<ans4<<endl;}return 0;
}
I
因为主要求一次和,且操作是给一段区间加上某个数(其实我们可以把减法看成加法)
那么我们可以不动原数组,我们已开始假设都为0,每次在l-r之间加上一个p
我们就可以在这个全是0的数组里的l位置加上p,r+1位置减去p。
最终我们求和的时候,求一下第二个数组的前缀和,这样这个前缀和的数组就是最终对每一个位置的改变量,再加上原来的数即可。
例如 0 0 0 0 0 0 0 0
我们在1-5 加上5 那么我们操作完就是 0 5 0 0 0 0 -5 0 我们再求一个前缀和 就是 0 5 5 5 5 5 0 0 ok!
#include<bits/stdc++.h>
using namespace std;
long long a[1111111];
long long b[1111111];
int main(){int n,m;while(cin>>n>>m){for(int i=1;i<=n;i++)scanf("%lld",&a[i]);memset(b,0,sizeof(b));int op,l,r;long long pp;while(m--){scanf("%d%d%d%lld",&op,&l,&r,&pp);if(op!=1){b[l]+=pp;b[r+1]-=pp;}else {b[l]+=-pp;b[r+1]+=pp;}}for(int i=2;i<=n;i++)b[i]+=b[i-1];scanf("%d%d",&l,&r);long long ans=0;for(int i=l;i<=r;i++)ans+=a[i]+b[i];printf("%lld\n",ans);}
}
D
思路就是将所有的乘数换成若干个质数相乘的形式,输出其中2的数量和5的数量去最小就是末尾0的数量。
当然显然肯定是5的数量比较小。。。。我的代码写烦了。
那么我们可以从5开始枚举到n,每次都加5. 计算其中因子5有多少个 再乘上在s中这个数出现了多少次即可
#include<bits/stdc++.h>
using namespace std;
int main(){long long n;while(cin>>n){long long jler=0;long long jlten=0;long long lss=5;while(lss<=n){long long jl1=0;long long zs=lss;while(zs%5==0){zs/=5;jl1++;}zs=lss;jlten+=jl1*(n-lss+1);lss+=5;}lss=2;while(lss<=n){long long jl1=0;long long zs=lss;while(zs%2==0){zs/=2;jl1++;}zs=lss;jler+=jl1*(n-lss+1);lss+=2;}long long ans=min(jler,jlten);cout<<ans<<endl;}
}
G
找规律,看鱼的数量是斐波那契数列,且偶数个鱼就不能吃
只要找f(1)-f(n)中偶数的数量即可。斐波那契数列 的规律是 奇数 奇数 偶数 奇数 奇数 偶数,2奇数1偶数这么排列。
#include<bits/stdc++.h>
using namespace std;
int main(){long long n;while(~scanf("%lld",&n)){long long ans=n-n/3;printf("%lld\n",ans);}return 0;
}
A
容斥。
若一个集合A内所有的元素都不是正整数N的因数,则称N与集合A无关。
给出一个含有k个元素的集合A={a1,a2,a3,...,ak},求区间[L,R]内与A无关的正整数的个数。
保证A内的元素都是素数。
用a1,a2.。。。。ak分别筛一遍l-r加到答案上
用a1*a2,a1*a3.。。。。。。分别筛一遍l-r 减到答案上。
也就是奇加偶减。。。
用状压 实现
#include<bits/stdc++.h>
using namespace std;
long long le,ri;
int n;
long long zs[22];
long long find(long long x)
{if(x<0)return 0;long long st=ri-ri%x;if(st<le)return 0;long long sm;if((st-le+1)%x==0)sm=(st-le+1)/x;else sm=(st-le+1)/x+1;return sm;
}
int main(){long long n;while(~scanf("%lld%lld%lld",&le,&ri,&n)){for(int i=0;i<n;i++)scanf("%lld",&zs[i]);long long ans=0;bool er[22];for(long long i=0;i<(1<<n);i++){long long lss=i;int js=0;int js1=0;long long cs=1;int f=1;while(lss){if(lss%2==1){cs*=zs[js1];if(cs>ri){f=0;break;}js++;}lss/=2;js1++;}if(f==0)continue;if(js%2==1)ans+=find(cs);else ans-=find(cs);}ans=-ans;printf("%lld\n",ans);}
}
F
将题目给的几个样例输入到某个神奇的求数列规律的网站里,就能得到通项公式了。
#include<bits/stdc++.h>
using namespace std;
int main(){long long n;while(~scanf("%lld",&n)){long long ans=1+n*(n-1)/2+n*(n-1)*(n-2)*(n-3)/24;printf("%lld\n",ans);}
}
这篇关于牛客小白月赛5 H J I D G A F的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!