A题：

https://ac.nowcoder.com/acm/contest/3674/A

题解：

给出m和n，分别对应斐波那契数列的第m项和第n项，求这两项的最大公约数。
注意：(1 ≤m,n ≤ 231 , GCD(m,n) ≤ 45)
对于gcd（m，n）比较小的来说，直接套结论即可。
湖南大学程序设计竞赛新生赛（重现赛） 2020.1.11 随笔

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int t,a,b,f[50];

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

int main(){
    f[0]=0,f[1]=1;
    for(int i=2;i<=50;i++){
        f[i]=f[i-1]+f[i-2];
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&a,&b);
        printf("%d\n",f[gcd(a,b)]);
    }
    return 0;
}







B题：

https://ac.nowcoder.com/acm/contest/3674/B

题解：

这道题答案中的B和C其实是有很多种解的，不要把思维局限到这道题一定有一个唯一解，我们要把这个唯一解求出来。
比如：A=a，B=5a，C=7a就是一种解。注意当a=0时，是无解的，其他情况都是有解的。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
 
ll a,b,c;
 
int main(){
    scanf("%lld",&a);
    if(a==0){//a==1时没有解
        printf("-1");
        return 0;
    }
    a=abs(a);
    printf("%lld %lld",5*a,7*a);
    return 0;
}







C题：

https://ac.nowcoder.com/acm/contest/3674/C

题解：

标准的bfs搜索题，对每个点向四个方向搜索，找出拥有金币数量最大的两块连通块，输出它们之和。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 505
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,m;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//四个方向
char mp[MAX][MAX];//mp表示地图
priority_queue<int> p;

struct node{
    int x,y;
    node(int xx,int yy){
        x=xx;
        y=yy;
    }
};

bool judge(int x,int y){//判断是否越界或者已经走过
    if(x<0||x>n+1||y<0||y>m+1||mp[x][y]=='#'){
        return false;
    }
    return true;
}

int bfs(int i,int j){
    int ans=0;
    queue<node> q;
    node tmp(i,j);
    q.push(tmp);
    while(!q.empty()){
        node d=q.front();
        q.pop();
        int x=d.x,y=d.y;
        if(mp[x][y]=='$') ans++;
        mp[x][y]='#';//标记已经走过
        for(int i=0;i<4;i++){//四个方向
            node next(x+dir[i][0],y+dir[i][1]);
            if(judge(next.x,next.y)){
                q.push(next);
            }
        }
    }
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
    }
    for(int j=0;j<=m+1;j++){//标记周围是可走的
        mp[0][j]=mp[n+1][j]='.';
    }
    for(int i=0;i<=n+1;i++){//标记周围是可走的
        mp[i][0]=mp[i][m+1]='.';
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]!='#'){
                int tmp=bfs(i,j);//求一个连通块的金币数
                p.push(tmp);
            }
        }
    }

    int sum=0;
    sum+=p.top();
    p.pop();
    if(p.size()!=0) sum+=p.top();
    printf("%d",sum);//输出最大金币数量的两块的总金币数
    return 0;
}







F题：

https://ac.nowcoder.com/acm/contest/3674/F

题解：

给出一些气球的x，y坐标，判断它们是否在一条直线上。
注意：气球是很小的，很多气球可能拥有相同的x，y坐标。
n=1或2的情况下，肯定是Yes，n>2时，我们可以先计算出前两个气球连线的斜率k，k=-1说明斜率不存在，并记录下第一个气球的位置。
以后每读入一个气球的位置，都计算出它与第一个气球连线的斜率k1，若k1==k，说明在一条直线上。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 505
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,x,y;

int main(){
    scanf("%d",&n);
    if(n==1||n==2){
        printf("Yes");
        return 0;
    }
    int x1,y1;
    double k;
    bool flag=true,tag=false;
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        if(i==0){x1=x,y1=y;continue;}
        if((x!=x1||y!=y1)&&tag==false){
            if(x==x1){k=-1;}//说明斜率不存在
            else k=(y-y1)/(x-x1);
            tag=true;
            continue;
        }
        if(x!=x1||y!=y1){
            if(x==x1){
                if(k!=-1){flag=false;break;}
            }else{
                if((y-y1)/(x-x1)!=k){flag=false;break;}
            }
        }
    }
    if(flag) printf("Yes");
    else printf("No");
    return 0;
}







G题：

https://ac.nowcoder.com/acm/contest/3674/G

题解：

你有一些钱n，有两种方案，可以买10元3把钥匙或者3元一把钥匙，需要在花光自己所有钱的情况下买最少的钥匙。
不难想到是贪心的原则，尽量多买10元3把的钥匙。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 505
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n;

int main(){
    scanf("%d",&n);
    int num1=n/10;//num1是买10元的次数，num1越大越好
    int res=n-num1*10;//余下的钱
    if(res%3==0){
        int ans=num1*3+res/3;
        printf("%d",ans);
        return 0;
    }
    bool flag=false;
    while(res%3!=0&&num1!=0){//若余下的钱不是3的倍数，就尝试少买一次10元的
        num1--;
        res=n-num1*10;
        if(res%3==0){
            flag=true;
            break;
        }
    }
    if(flag){//若在尝试中满足是3的倍数
        int ans=num1*3+res/3;
        printf("%d",ans);
    }else{
        printf("orz");
    }
    return 0;
}







H题：

https://ac.nowcoder.com/acm/contest/3674/H

题解：

就是计算0.5+0.5*0.5+...+0.5n

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 505
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;


int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        double ans=0.5,res=0.0;
        for(int i=1;i<=n;i++){
            res+=pow(0.5,i);
        }
        printf("%.4lf\n",res);
    }
    return 0;
}







I题：

https://ac.nowcoder.com/acm/contest/3674/I

题解：

其实就是就是全错排问题，不用管输入的数组A[]是什么。注意要用long long，用int是过不了的。
全错排问题链接：全错排问题

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 100005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

ll n,d[MAX],a[MAX],mod=1e9+7;

int main(){
    d[1]=0,d[2]=1;
    for(int i=3;i<=100005;i++){
        d[i]=((i-1)*((d[i-1]+d[i-2])%mod))%mod;
    }
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    ll tot=1;
    for(int i=1;i<=n;i++){
        tot=(tot*i)%mod;
    }
    if(tot<=d[n]){
        printf("%lld",tot+mod-d[n]);
    }else{
        printf("%lld",(tot-d[n])%mod);
    }

    return 0;
}







J题：

https://ac.nowcoder.com/acm/contest/3674/J

题解：

博弈论。规则如下：
有n堆糖果，每堆糖果的数量为ai，谁最后一次取完后没有剩下糖果，那么这个人获胜。
（1）Dada只能从一堆中取走偶数个糖果，并且当所有堆的糖果数都小于2时，Data不能再取糖果，就是相当于空过了一回合
（2）Tutu只能从一堆中取走奇数个糖果
（3）Dada先取
当n=1时，若糖果数为偶数，则Dada可以一次就取完，若为奇数，最后取的人肯定是Tutu
当n>1时，Data必定不可能一次取完所有糖果，那么Tutu只要保证有一堆糖果是奇数个，一直不取这一堆，等到最后再取这一堆是肯定会获胜的
综上：
只有当n=1且糖果数为偶数时，Data获胜，否则Tutu获胜。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 50005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

ll a[MAX];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    if(n==1&&a[0]%2==0){
        printf("DaDa");
    }else{
        printf("TuTu");
    }
    return 0;
}







L题：

https://ac.nowcoder.com/acm/contest/3674/L

题解：

其他就是求区间内素数的个数，注意这道题1也要当作一个素数。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 100005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int l,r;
bool isprime[MAX];

void eratos(){//线性筛素数
    for(int i=0;i<=MAX;i++){
        isprime[i]=true;
    }
    isprime[0]=false,isprime[1]=true;
    for(int i=2;i*i<=MAX;i++){//留下i，删除i的倍数
      if(isprime[i]){
          int j=i+i;
          while(j<=MAX){
              isprime[j]=false;
              j=j+i;
          }
      }
    }
}

int main(){
    eratos();//线性筛素数
    scanf("%d%d",&l,&r);
    int cnt=0;
    for(int i=l;i<=r;i++){
        if(isprime[i]) cnt++;
    }
    printf("%d",cnt);
    return 0;
}







M题：

https://ac.nowcoder.com/acm/contest/3674/M

题解：

求区间的异或和。
从1到n的异或和是有规律的：
n=1 2 3 4 5 6 7 8 9 10
下面是它们的异或和：
1 3 0 4 1 7 0 8 1 11
规律是：
当n%4==0时，和=n；
当n%4==1时，和=1；
当n%4==2时，和=n+1；
当n%4==3时，和=0；
而我们知道，求[l,r]的异或和可以转化为求[1,l-1]和[1,r]的异或和

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<map>
#define MAX 505
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

ll f(ll n){
    if(n%4==0){
        return n;
    }else if(n%4==1){
        return 1;
    }else if(n%4==2){
        return n+1;
    }else if(n%4==3){
        return 0;
    }
}

int main(){
    ll l,r;
    cin>>l>>r;
    cout<<(f(l-1)^f(r))<<endl;
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄