赞
踩
A:华华听月月唱歌
https://ac.nowcoder.com/acm/contest/392/A
分析:给出m个[begin,end]区间,求最少需要几段,用贪心的思想,先将区间按begin先后排序,用到了STLpair<int,int>
而且sort默认以first排序。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int N=100005; pair<int,int> pr[N]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++) cin>>pr[i].first>>pr[i].second; sort(pr+1,pr+m+1);//默认排序 int k=1,begin=1,num=0; while(begin<=n){//位置小于n int res=0; while(begin>=pr[k].first&&k<=m) res=max(res,pr[k].second),k++; if(res>=begin) begin=res+1,num++;更新了,就需要加一 else{ num=-1; break; } } cout<<num<<endl; return 0; }
B.华华教月月做数学
https://ac.nowcoder.com/acm/contest/392/B
分析:看似是一个简单的快速幂,但是a,b,p的数据范围过大,相乘时会有溺出的情况,所以在快速幂里面算乘法的时候转化为二进制加法时间复杂度为log(n)
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; ll poww(ll a,ll b,ll p){//算乘法,不然会溺出 ll res=0; while(b){ if(b&1) res=(res+a)%p; a=a*2%p; b>>=1; } return res; } ll pow_quick(ll x,ll y,ll mod){//快速幂 ll res=1,base=x%mod; while(y){ if(y&1) res=poww(res,base,mod); base=poww(base,base,mod); y>>=1; } return res%mod; } int main(){ int t; ll a,b,p; cin>>t; while(t--){ cin>>a>>b>>p; cout<<pow_quick(a,b,p)<<endl; } return 0; }
E.华华给月月准备礼物
https://ac.nowcoder.com/acm/contest/392/E
分析:二分答案模板题,先用sum对a[i]求总和,然后除以需要的K段,即完美情况下的最大值
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int N = 200005; typedef long long ll; ll n, k; ll a[N]; ll check(ll x){ ll cnt = 0; for (int i = 1; i <= n; i++) cnt += a[i] / x;//一根木棍能用几根 return cnt; } int main(){ cin >> n >> k; ll sum = 0, ans = 0; for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i]; sum /= k;//最大的长度 ll L = 1, R = sum; while (L<=R){//二分 ll mid = (L + R) >> 1; if (check(mid) >= k){ L = mid + 1; ans = mid; } else R = mid-1; } cout << ans << endl; return 0; }
G.华华对月月的忠诚
https://ac.nowcoder.com/acm/contest/392/G
分析:题目给出A,B的范围以及N的范围2都过大,显然是规律题,
其实对于同一组数据来说不管求第几项的gcd同理都是求A,B的gcd
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y){
return y==0?x:gcd(y,x%y);
}
int main(){
ll a,b,n;
cin>>a>>b>>n;
cout<<gcd(a,b);
return 0;
}
J.月月查华华的手机
https://ac.nowcoder.com/acm/contest/392/J
分析:查找字串的题,因为字串的累加和才1e6的数据,所以直接暴力过,注意如果找到子串就直接break。
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<cstdio> using namespace std; int main(){ string a,b; int n; cin>>a>>n; while(n--){ cin>>b; int k=0; for(int i=0;i<a.size();i++){ if(a[i]==b[k]) k++; if(k>=b.size()) break; } if(k>=b.size()) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。