更好的阅读体验

T1-Mike and gcd problem

Mike给定一个n个元素的整数序列,A=[a1,a2,...,an],每次操作可以选择一个i(1≤i<n)，将a[i],a[i+1]变成a[i]-a[i+1]和a[i]+a[i+1]。现在想要的是A序列所有元素的最大公约数大于1，请计算最少的操作次数。

解法

如果一开始就满足要求，直接输出YES 0

如果不满足，一定是把奇数变成偶数

有2种情况：

奇数奇数只需要一次操作

奇数偶数需要两次操作

然后就好了

ac代码

#include<bits/stdc++.h>

using namespace std;

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

int n,a[100010],s,x;

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    s=a[1];

    for(int i=2;i<=n;i++)s=gcd(s,a[i]);

    puts("YES");

    if(s!=1)puts("0");

    else

    {

        s=0;

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

        {

            if(a[i]&1)

            {

                i++;

                if(a[i]&1)s++;

                else s+=2;

            }

        }

        printf("%d\n",s);

    }

    return 0;

}

T2-Mike and distribution

给两个长度为n的数列A,B，要求至多选择n/2+1个下标，使得A数组中选出的数的和的两倍大于sumA，B数组中选出的数的和的两倍大于sumB

解法

按a序列排序，然后2个2个取，注意的是要先取最大的那一个

可以保证都大于一半

ac代码

#include<bits/stdc++.h>

using namespace std;

struct node{int x,y,num;}a[100010];

int n,cnt,ans[100010];

int cmp(node x,node y){return x.x==y.x?x.y>y.y:x.x>y.x;}

int main()

{

	scanf("%d",&n),cnt=0;

	for(int i=1;i<=n;i++)scanf("%d",&a[i].x);

	for(int i=1;i<=n;i++)scanf("%d",&a[i].y);

	for(int i=1;i<=n;i++)a[i].num=i;

	sort(a+1,a+1+n,cmp),ans[++cnt]=a[1].num;

	for(int i=2;i<=n;i+=2)

	{

		if(a[i].y>a[i+1].y)ans[++cnt]=a[i].num;

		else ans[++cnt]=a[i+1].num;

	}

	printf("%d\n",cnt);

	for(int i=1;i<=cnt;i++)printf("%d ",ans[i]);

	return 0;

}

巴特西

hgoi#20190517

更好的阅读体验

T1-Mike and gcd problem

解法

ac代码

T2-Mike and distribution

解法

ac代码

最新文章

热门文章