【题解】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;
    }
全部评论

相关推荐

榕城小榕树:1200单休,我去干点啥别的不好
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 14:10
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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