和小哥哥一起刷洛谷(1)-白红宇

和小哥哥一起刷洛谷(1)

阅读量：6234 次

发布时间：2019-06-21

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

小哥我是编程爱好者，正在学习摸索中，此文就是我最近编的代码以及编程中的思路，易错点等心得体会。

今天小哥我作为cpp党就来带大家刷几道很有意思的题目。

由于微信不支持插入代码，只能用markdown写文章，markdown的排版功能尚不熟悉，小试一下。

P1029最大公约数和最小公倍数问题

题目：

输入 2 个正整数x0,y0,求出满足下列条件的 P,Q 的个数

条件：

P,Q 是正整数

要求：

P,Q 以 x0 为最大公约数,以 y0 为最小公倍数.

试求:满足条件的所有可能的 2 个正整数的个数.

思路：

1.枚举a/y0的值

代码：

#include
    
     using namespace std;int main(){        int x,y,a,factors,count=0;        cin>>x>>y;        a=y/x;        for(int i=1;i<=y;i++)        {            if(a%i==0)            {   factors=0;                for(inti2=2;i2<=min(i,a/i);i2++)                {                    if(i%i2==0 &&(a/i)%i2==0)                    factors++;                }                if(factors==0)                    count++;            }        }        cout<

P2118比例简化

题目：

在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为 1498:902 。

不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。

现给出支持人数A，反对人数 B ，以及一个上限 L，请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均不大于 L 且 A’和 B’互质（两个整数的最大公约数是 1 ）的前提下， A’/B’ ≥ A/B且 A’/B’ - A/B的值尽可能小。

思路：

枚举每个小于l的A和B，看哪个即大于又最接近A/B；

代码：

#include
    
     using namespace std;int main(){       int a,b,c;       double s=10000,s1,s2;       cin>>a>>b>>c;       s1=1;s2=1;       for(int i1=1;i1<=c;i1++)       {           for(int i2=1;i2<=c;i2++)           {              if((double)i1/i2<(double)a/b)continue;              int m=i1;              int n=i2;              while(n!=0)              {                  int yu=m%n;                  m=n;                  n=yu;              }              if(m!=1) continue;              if(s!=min(s,(double)i1/i2))              {                  s=(double)i1/i2;                  s1=i1;s2=i2;              }           }       }       cout<
     
      <<""<

易错点：

双重循环中if语句太多，小哥我其中有一个if语句第一次写时只套了一条语句，偷懒，没有写花括号；结果后来又加了一条语句结果忘记补上花括号，导致程序错乱，检查了好久才检查出来。

P1147 连续自然数和

题目：

对一个给定的自然数 M ，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为 M 。

例子： 1998+1999+2000+2001+2002= 10000 ，所以从 1998 到 2002 的一个自然数段为 M=10000 的一个解。

思路：

利用等差数列公式，枚举项数n，判断2m是否能被n整除以及(2num/n+1-n)整除2，并且(2num/n+1-n)/2>0。若符合，则输出首项和末项。

代码：

#include
    
     using namespace std;int main(){        cin>>num;        for(n=num;n>1;n--)        {            if(2*num%n==0 &&(2*num/n+1-n)%2==0 && (2*num/n+1-n)/2>0)            {                a=(2*num/n+1-n)/2;                cout<
     <<" "<
      
       <

易错点：

1.题目要求输出的两个数之间用空格隔开，但是是英文空格！英文空格！英文空格！小哥我就在这里错了！！！

P1865 A%B problem

题目：

输入一行两个整数询问次数n，范围m

接下来n行，每行两个整数l,r表示区间

对于每次询问输出区间内质数个数t,如l或r∉[1,m]输出Crossing the line

思路1：

对范围内所有数暴力试除，用布尔数组记录数字是否为质数。

最后再检测输入的范围内有多少个质数。

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int main(){ int n,m,a,b; cin>>n>>m; bool list[m+1]; memset(list,false,sizeof(list)); for(int i=2;i<=m;i++) { int count=0; for(int i1=2;i1
          
           >a>>b; if(a<1 || b>m) { cout<<"Crossing theline"<

结果你知道的——超时！

思路2：

另一种选出质数的方法——删掉合数，筛质数！

在布尔列表分别把

2的2倍，3倍，4倍……设为false；

再找到下一个为true的数M，把

M的 2倍，3倍，4倍……设为false；

…

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int main(){ int n,m,a,b; cin>>n>>m; bool list[m+1]; memset(list,true,sizeof(list)); list[1]=false; for(int i=2;i<=m;i++) { if(list[i]==true) { for(int i2=2*i;i2<=m;i2+=i) list[i2]=false ; } } for(int l=1;l<=n;l++) { cin>>a>>b; if(a<1 || b>m) { cout<<"Crossing the line"<