首页 > 代码库 > 【hackerrank】Week of Code 26
【hackerrank】Week of Code 26
在jxzz上发现的一个做题网站，每周都有训练题，题目质量……前三题比较水，后面好神啊，而且类型差不多，这周似乎是计数专题……
Army Game
然后给出n*m,问需要多少个小红点能全部占领
解法：乘法。。。
Best Divisor
给一个数，问一个数的约数中数字和最大的约数。
解法：直接分解质因数就可以啦。
Twins
孪生质数定义为两个质数之差为2，问n,m之间有多少个孪生质数（n<=m<=10^9,m-n<=10^6)
解法：显然直接判断区间内相邻的两个奇数是否为质数就可以啦。然而n和m比较大，所以判断是否为质数不能直接用sqrt(n)这样去枚举，可以先用线性筛处理出sqrt(n)的质数，判断的时候直接枚举质数表里面的质数就可以啦。
1 1 #include<cstdio> 2 2 #include<cstring> 3 3 #include<cstdlib> 4 4 #include<queue> 5 5 #include<algorithm> 6 6 #include<stack> 7 7 #include<cmath> 8 8 #include<map> 9 9 #define LL long long 10 10 #define maxn 1000100 11 11 12 12 13 13 using namespace std; 14 14 15 15 int n,m,now,sum,prime[maxn],ok[maxn],tot=0; 16 16 void calc() 17 17 { 18 18 int i,k; 19 19 for (i=2;i<maxn;i++) { 20 20 if (!ok[i]) prime[tot++]=i; 21 21 for (LL j=(LL)(i)*prime[k=0];j<maxn;j=i*prime[++k]) { 22 22 // printf("%lld %d\n",j,i); 23 23 ok[j]=1; 24 24 if (!(i%prime[k])) break; 25 25 } 26 26 } 27 27 // for (int i=0;i<tot;i++) printf("\t%d",prime[i]); 28 28 } 29 29 30 30 int check(int x) 31 31 { 32 32 if (x==1) return 0; 33 33 for (int i=0;i<tot && prime[i]<=sqrt(x);i++) 34 34 if (!(x%prime[i])) return 0; 35 35 return 1; 36 36 } 37 37 38 38 int main() 39 39 { 40 40 calc(); 41 41 scanf("%d %d",&n,&m); 42 42 now=0,sum=0; 43 43 if (!(n%2)) n++; 44 44 for (int i=n;i<=m;i=i+2) 45 45 if (check(i)) { 46 46 if (now) ++sum; 47 47 else ++now; 48 48 } 49 49 else 50 50 now=0; 51 51 printf("%d\n",sum); 52 52 return 0; 53 53 }
Music on the Street
给出一些在数轴点（n<10^6)，给出一个长度m(<10^9)，再给一个hmin,hmax,找到一个区间使区间内两个点直接的距离大于hmin小于hmax，头尾两个点离区间端点距离大于hmin小于hmax。
解法：队列模拟一下就可以啦。
如果队头的点和当前的点距离大于m就出队，
同时如果当前点和队尾的点不满足距离大于hmin小于hmax，全部出队。
当前点进队
同时记录一个当前左端允许的最左边界=max(上一个出队的点，当前对头-hmax）
然后计算对头允许的区间+m和队尾的点的大于hmin小于hmax有没有交集（判断方法两个区间左端点最大值小于等于两个区间右端点最小值，一直这里判断错，要么就是复杂了……）
有的话就是一个合法解啦。
然后要注意一些情况，比如m比hmax小……有可能直接就……
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<map> #define maxn 1000100 using namespace std; int n,len,hmin,hmax,i,num[maxn]; queue<int> pp; int calc() { int lnow,i; num[0]=num[1]-hmax-1; lnow=num[0]; num[n+1]=num[n]+hmax+1; pp.push(i=0); while (++i<=n) { int last,l1,l2,l3,l4; while (pp.size() ) { if (num[i]-num[last=pp.front()]+hmin<=len && num[i]-num[pp.back()]<=hmax && num[i]-num[pp.back()]>=hmin ) break; lnow=num[last]; pp.pop(); } pp.push(i); last=pp.front(); lnow=max(lnow,num[last]-hmax); if (num[last]-lnow>=len && len<=hmax) return num[last]-len; if (pp.size()) { l1=max(lnow,num[last]-hmax)+len; l2=num[last]-hmin+len; l3=num[i]+hmin; l4=min(num[i+1],num[i]+hmax); if (max(l1,l3)<=min(l2,l4)) return max(l1,l3)-len; } } return -1; } int main() { scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&num[i]); scanf("%d %d %d",&len,&hmin,&hmax); printf("%d\n",calc()); return 0; }
Satisfactory Pairs
ax+by=n(<3*10^5)，给出n，问多个对点对（a,b)其中a<b。
解法：太弱了不会……潘学姐给思路了还是不会……
贴题解
意思就是先找出所有数的约数（用vector存起来）
然后公式化为ax=n-by，然后第一层循环枚举b，第二层循环枚举y,然后再枚举（n-by）的约数中小于b的，然后y值不用的时候可能有相同的约数导致重复，所以开个数组储存一个当前这个约数被最新更新的b值，每次判断下这个约数是否已经被b求过，没有的话ans++。
复杂度分析是调和数列求和。
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<map> #include<vector> #define maxn 301020 #define LL long long using namespace std; int num[maxn],prime[maxn],p[maxn],tot=0; vector<int> d[maxn]; int n; void atfirst() { int i,j,l; LL k; for (i=2;i<maxn;i++) { if (!p[i]) { p[i]=i; prime[tot++]=i; } for (k=i*prime[j=0];j<tot && k<maxn;k=i*prime[++j]) { p[k]=prime[j]; if (!(i%prime[j])) break; } } d[1].push_back(1); for (i=2;i<maxn;i++) { int x=i,y=1; while (!(x%p[i])) { y++; x/=p[i]; } for (j=0;j<d[x].size();j++) for (k=d[x][j],l=y;l;l--,k*=p[i]) d[i].push_back(k); sort(d[i].begin(),d[i].end()); } } int main() { atfirst(); scanf("%d",&n); memset(num,0,sizeof(num)); int ans=0; for (int b=2;b<n;b++) for (int i=1;i*b<n;i++) { int x=n-i*b; for (int j=0;j<d[x].size() &&d[x][j]<b;j++) if (num[d[x][j]]!=b) { ans++; num[d[x][j]]=b; } } printf("%d\n",ans); return 0; }
Hard Homework
给一个n（3*10^6)，求一组x+y+z使sin(x)+sin(y)+sin(z).
解法，如果是两个数的和，显然很简单，和差化积就变成2*sin((x+y)/2)cos((x-y)/2)，然后只需要知道cos((x-y)/2)的最大值就可以了，这里分情况，和为偶数则最大值显然为cos(0)，如果为奇数，x-y的取值范围是（2，n-2），线性就可以求出。
那现在三个数，枚举第一个数，预处理出cos（（2，n-2）/2）的最大值，然后就可以一直求出后面两个数的最大值啦。
（然而这思路分析也是受潘学姐的启发，学姐好棒）
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<queue> 5 #include<algorithm> 6 #include<stack> 7 #include<cmath> 8 #include<map> 9 #define exp 0.0000000001 10 using namespace std; 11 12 int n; 13 int main() 14 { 15 scanf("%d",&n); 16 double num1=-1,ans=-exp; 17 for (int i=n-2;i;i--) { 18 int now=n-i; 19 double now1; 20 if (now%2) { 21 double now2=cos((now-2)/2.0); 22 if (now2-num1>=exp) num1=now2; 23 now1=sin(i)+2*sin(now/2.0)*num1; 24 } 25 else 26 now1=sin(i)+2*sin((now)/2.0); 27 if (now1-ans>=exp) ans=now1; 28 } 29 printf("%.9lf\n",ans); 30 return 0; 31 }
Tastes Like Winning
nim问题，n堆，每堆可能取值为（1-2^m-1)，问多少种情况使每堆数量不同且先手胜，n,m<10^9，答案%（10^9+7)，（10^9+7)都是神题
解法：不会写，看不懂，
【hackerrank】Week of Code 26