c++

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

四道水题

Posted by ethan-zhou on September 2, 2018

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

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

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

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

题目:

输入 2 个正整数x0,y0,求出满足下列条件的 P,Q 的个数 条件: P,Q 是正整数 要求: P,Q 以 x0 为最大公约数,以 y0 为最小公倍数. 试求:满足条件的所有可能的 2 个正整数的个数.

思路:

1.枚举a/y0的值

代码:

#include<bits/stdc++.h>
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<<count;
        return 0;
}

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<bits/stdc++.h>
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<<s1<<""<<s2;
       return 0;
}

易错点:

双重循环中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<bits/stdc++.h>
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<<a<<" "<<a+n-1<<endl; 
            }
        }

        return 0;
}

易错点:

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

P1865 A%B problem

题目:

输入一行两个整数 询问次数n,范围m 接下来n行,每行两个整数l,r表示区间 对于每次询问输出区间内质数个数t,如l或r∉[1,m]输出Crossing the line

思路1:

对范围内所有数暴力试除,用布尔数组记录数字是否为质数。 最后再检测输入的范围内有多少个质数。 代码如下:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
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<i;i1++)
            {
                if(i%i1==0) 
                {
                    count++;
                    break;
                }
            }
            if(count==0)
            {
                list[i]=true;
            }
        }

        for(int l=1;l<=n;l++)
        {
            cin>>a>>b;

            if(a<1 || b>m)
            {
                cout<<"Crossing theline"<<endl;
                continue;
            }

            int count=0;
            for(int i=a;i<=b;i++)
            {
                if(list[i]==true)
                {
                    count++;
                }
            }
            cout<<count<<endl;
        }
        return 0;
}

结果你知道的——超时!

思路2:

另一种选出质数的方法——删掉合数,筛质数! 在布尔列表分别把 2的2倍,3倍,4倍……设为false; 再找到下一个为true的数M,把 M的 2倍,3倍,4倍……设为false; …

代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
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"<<endl;
                continue;
            }

            int count=0;
            for(int i=a;i<=b;i++)
            {
                if(list[i]==true)
                {
                    count++;
                }
            }
            cout<<count<<endl;
        }
        return 0;
}

终于没超时!!

易错点:

1.这题很容易超时,要多试几种找质数的方法。


作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接