【题解】gcd游戏

题意

给一个长度为的数组,每次可以选择一个,让。问操作多少次,最终得到的数组

题解

最简单的一个方法就是让数组总的,那只要让所有的数变为偶数即可。那么我们可以考虑相连两个数的不同情况。$

  1. 都为偶数,那么不需要进行操作。
  2. 都为奇数,对于操作来说就是两个奇数进行加减,两个奇数的加减得到的都是偶数,所以只需要操作一次就可以了。
  3. 为奇数为偶数,奇数减偶数为奇数,偶数加奇数变为奇数。所以操作一次都变为奇数,再操作一次可以都变为偶数。
  4. 为偶数为奇数,由于要求操作次数最少,那么不与进行操作,优先进行判断,若,那么只能进行两次变化变为偶数。

    复杂度

    时间复杂度

    代码

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+5;
    int a[N];
    int main()
    {
    int n;
    scanf("%d",&n);
    scanf("%d",&a[1]);
    int g = a[1];
    for(int i = 2;i <= n;i++)
    {
        scanf("%d",&a[i]);
        g = __gcd(g,a[i]);
    }
    if(g > 1)
    {
        printf("0\n");
        return 0;
    }
    int ans = 0;
    for(int i = 1;i < n;i++)
    {
        if(a[i]%2 && a[i+1]%2 == 0)
        {
            ans += 2;
        }
        else if(a[i]%2 && a[i+1]%2)
        {
            ans++;
            a[i+1]++;
        }
    }
    if(a[n]%2)  ans += 2;
    printf("%d",ans);
    return 0;
    }
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:13
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务