5月10日 “科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

  1. A题:

主要是找规律,另外通过题解学会了一个新函数___gcd()(双下划线)

石子被取走需要满足的条件为代码是a,b最大公约数的倍数,所以只要找出1~中有几个能被取走的石子就行,即n/__gcd(a,b)为可以被取走的石子的数量:

#include<bits/stdc++.h>

using namespace std;

void indata();

int main()

{

  int n,a,b,i,t;

  cin>>t;

  while(t--)

  {

      cin>>n>>a>>b;

      i=__gcd(a,b);

      i=n/i;

      if(i&1)

      {

          cout<<"Yes"<<endl;

      }

      else

      {

          cout<<"No"<<endl;

      }

  }

    return 0;

}

2.B题,我原本想用C++中string类的操作函数实现,但是没有成功。题解是用了C中的字符串操作+指针,确实要灵活许多。

思路:输入字符串,找到第一个‘+‘的位置,如果没有,说明只有一个部分,ans直接加上这一部分就行了,如果找到了,就计算出这一部分的和,然后用指针指向‘+‘后面的字符串,重复上面过程。’另外学会了一个新函数atoi()把字符串转换为整型。

另外学会了完整输出高位浮点数的方法

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

char s[10000];

int f(char *);

int main()

{

    int n,i,j,k;

    cin>>s;

    int len=strlen(s);

    ll ans=0;

    char *p=s;

    while(1)

    {

        char *q=strchr(p,'+');

        if(q==NULL)

        {

            ans+=f(p);

            break;

        }

        else

        {

            *q='';

            ans+=f(p);

            p=q+1;

        }

    }

    cout<<ans/2;

    if(ans&1)

    {

        cout<<".5"<<endl;

    }

    return 0;

}

int f(char *p)

{

    char *u=strchr(p,'d');

    if(u==NULL)

    {

        return atoi(p)*2;

    }

    else

    {

        *u='';

        int num1=atoi(p);

        int num2=atoi(u+1);

        return num1*(1+num2);

    }

}

3.F题:

超时了两次,大体思路正确,但在如何正确计数方面做的不好。通过此题学会了差分的思想。

思路:

计算出数字出现的次数,升序排序,最后从1开始乘以排序后的次数。

排序思想:对于输入的l和r,l和r之间的数(包括l和r)出现次数都+1,所以我们让num[l]++,这样保证了l(包括l)之后的数都+1,num[r+1]--,这样保证了r(不包括r)之后的数不+1。

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int num[200000+8]={0};

int main()

{

    int n,m,i,j,k;

    cin>>n>>m;

    while(m--)

    {

        int l,r;

        scanf("%d%d",&l,&r);

        num[l]++;

        num[r+1]--;

    }

    for(i=1;i<=n;i++)

    {

        num[i]+=num[i-1];

    }

    sort(num+1,num+n+1);

    ll ans=0;

    for(i=1;i<=n;i++)

    {

        ans+=(ll)i*num[i];

    }

    cout<<ans<<endl;

    return 0;

}

原文地址:https://www.cnblogs.com/chengxvzhishen/p/12878458.html