https://loj.ac/problem/526

題目描述

qmqmqm有一個長為?n?的數列?${\mathrm{a1,a2,\dots \dots ,an，你需要選擇集合\{1,2,\dots \dots ,n\}的一個子集，使得這個子集中任意兩個元素?i,j?均滿足條件?gcd(ai,aj)\times gcd(ai+1,aj+1)\ne 1，其中gcd(i,j)表示最大公約數，且這個子集的元素個數是所有滿足上述條件的子集中最多的。輸出這個子集的元素個數。}}^{}$

輸入格式

輸入的第一行包含一個正整數nnn。 隨后nnn行，每行一個正整數aia_ia?i??。

輸出格式

輸出一個整數代表符合條件的元素最多的子集的元素個數。

樣例

樣例輸入1

4 4 6 1 9

樣例輸出1

3

樣例解釋

選擇的子集為{1,2,4}\{1,2,4\}{1,2,4}。

樣例輸入2

41 71 3 5 50 75 2 19 47 88 95 92 110 111 117 58 124 130 57 129 168 161 29 39 206 79 10 142 107 209 210 222 221 223 242 104 264 265 202 279 314 315

樣例輸出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=0; int f=1; char c=getchar();while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }x*=f; } void read(LL &x) {x=0; int f=1; char c=getchar();while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }while(isdigit(c)) { x=x*10+c-'0'; 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=1;i<=b[0];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=1;i<=n;i++){read(x);(x&1 ? a[++a[0]] : b[++b[0]])=x;}for(int i=1;i<=a[0];i++)for(int j=1;j<=b[0];j++)if(gcd(a[i],b[j])==1 && gcd(a[i]+1,b[j]+1)==1) g[i][j]=true;int sum=0;for(int i=1;i<=a[0];i++){fill(vis+1,vis+b[0]+1,0);if(go(i)) sum++;}printf("%d",n-sum); }

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/7468782.html

總結

以上是生活随笔為你收集整理的「LibreOJ β Round #4」子集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。