【hackerrank】Week of Code 26-白红宇

【hackerrank】Week of Code 26

阅读量：6073 次

发布时间：2019-06-20

本文共 3941 字，大约阅读时间需要 13 分钟。

在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
      
        2  2 #include
       
         3  3 #include
        
          4  4 #include
         
           5  5 #include
          
            6  6 #include
           
             7 7 #include
            
              8 8 #include
              9 9 #define LL long long 10 10 #define maxn 100010011 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

View Code

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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #define maxn 1000100using namespace std;int n,len,hmin,hmax,i,num[maxn];queue
              
                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; }

View Code

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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define maxn 301020#define LL long longusing namespace std;int num[maxn],prime[maxn],p[maxn],tot=0;vector
               
                 d[maxn];int n;void atfirst(){ int i,j,l; LL k; for (i=2;i

View Code

Hard Homework

给一个n（3*10^6)，求一组x+y+z=n使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
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
              9 #define exp 0.000000000110 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 }

Hard Homework

Tastes Like Winning

nim问题，n堆，每堆可能取值为（1-2^m-1)，问多少种情况使每堆数量不同且先手胜，n,m<10^9，答案%（10^9+7)，（10^9+7)都是神题

解法：不会写，看不懂，

转载于:https://www.cnblogs.com/Macaulish/p/6135675.html

你可能感兴趣的文章