hgoi#20190517

muronglin
muronglin 2019年05月17日
  • 在其它设备中阅读本文章

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("%dn",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("%dn",cnt);
    for(int i=1;i<=cnt;i++)printf("%d ",ans[i]);
    return 0;
}