「LibreOJ β Round #4」子集

https://loj.ac/problem/526

题目描述

qmqmqm有一个长为 n 的数列 a1,a2,……,an，你需要选择集合{1,2,……,n}的一个子集，使得这个子集中任意两个元素 i,j 均满足条件 gcd(ai,aj)×gcd(ai+1,aj+1)≠1，其中gcd(i,j)表示最大公约数，且这个子集的元素个数是所有满足上述条件的子集中最多的。输出这个子集的元素个数。

输入格式

输入的第一行包含一个正整数nnn。随后nnn行，每行一个正整数aia_iai。

输出格式

输出一个整数代表符合条件的元素最多的子集的元素个数。

样例

样例输入1

样例输出1

样例解释

选择的子集为{1,2,4}\{1,2,4\}{1,2,4}。

样例输入2

样例输出2

22

奇数和奇数、偶数和偶数一定可以选在一起
所以对于不满足条件的奇数和偶数，连边
求最大点独立集
即点数-匹配数

#include<cstdio>

#include<iostream>

#define N 501

using namespace std;

typedef long long LL;

int n;

LL a[N],b[N];

bool g[N][N],vis[N];

int match[N];

void read(int &x)

{

    x=; int f=; char c=getchar();

    while(!isdigit(c)) { if(c=='-') f=-;  c=getchar(); }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

void read(LL &x)

{

    x=; int f=; char c=getchar();

    while(!isdigit(c)) { if(c=='-') f=-;  c=getchar(); }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

inline LL gcd(LL p,LL q) { return !q ? p : gcd(q,p%q); }

bool go(int now)

{

    for(int i=;i<=b[];i++)

    {

        if(vis[i] || !g[now][i]) continue;

        vis[i]=true;

        if(!match[i] || go(match[i]))

        {

            match[i]=now;

            return true;

        }

    }

    return false;

}

int main()

{

    read(n);

    LL x;

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

    {

        read(x);

        (x& ? a[++a[]] : b[++b[]])=x;

    }

    for(int i=;i<=a[];i++)

        for(int j=;j<=b[];j++)

            if(gcd(a[i],b[j])== && gcd(a[i]+,b[j]+)==) g[i][j]=true;

    int sum=;

    for(int i=;i<=a[];i++)

    {

        fill(vis+,vis+b[]+,);

        if(go(i)) sum++;

    }

    printf("%d",n-sum);

}

巴特西