$loj526\ [LibreOJ\ \beta\ Round\ \#4]$ 子集 图论

正解:图论

解题报告:

传送门$QwQ$

发现最大团不好求,于是考虑求最大独立集.也就把所有$gcd(i,j)\cdot gcd(i+1,j+1)=1$的点之间连边,然后求最大独立集.

发现依然不可做,不妨猜结论:这张图一定是张二分图.

其实猜到了证明还是挺$easy$的$QwQ$

发现连边的点之间的奇偶性一定不同,因为若相同,$gcd$必定为2的倍数

所以这是张二分图

于是就跑个匈牙利求最大匹配数,答案就$n-$最大匹配数鸭,$over$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define int long long
#define ri register int
#define rc register char
#define rb register bool
#define lowbit(x) (x&(-x))
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=400+10,inf=1e9;
int n,match[N];
bool vis[N];
vector<int>to[N],V[2];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
int gcd(ri x,ri y){return y?gcd(y,x%y):x;}
int dfs(ri x)
{
    vis[x]=1;
    for(auto t:to[x]){if(~match[t])if(vis[match[t]] || !dfs(match[t]))continue;match[t]=x;return 1;}
    return 0;
}

signed main()
{
    n=read();rp(i,1,n){ri x=read();V[x&1].push_back(x);}ri sz0=V[0].size(),sz1=V[1].size();
    rp(i,0,sz0-1)rp(j,0,sz1-1)if(gcd(V[0][i],V[1][j])*gcd(V[0][i]+1,V[1][j]+1)==1)to[i].push_back(j);
    memset(match,-1,sizeof(match));rp(i,0,sz0-1){memset(vis,0,sizeof(vis));n-=dfs(i);}printf("%lld\n",n);
    return 0;
}

随机推荐

1. Laravel中利用队列发送邮件的方法示例

   https://www.jb51.net/article/121647.htm 本文主要给大家介绍了关于Laravel中队列发送邮件的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的 ...

2. Oracle基础学习4--Oracle权限传递

   版权声明:本文为博主原创文章.未经博主同意不得转载. https://blog.****.net/wang379275614/article/details/32215325 以下将用一个实例来解说: ...

3. oracle函数 LPAD(c1,n[,c2])

   [功能]在字符串c1的左边用字符串c2填充,直到长度为n时为止 [参数]C1 字符串 n 追加后字符总长度 c2 追加字符串,默认为空格 [返回]字符型 [说明]如果c1长度大于n,则返回c1左边n个 ...

4. @bzoj - 3749@ [POI2015] Łasuchy

   目录 @description@ @solution@ @version - 1@ @version - 2@ @accepted code@ @version - 1@ @version - 2@ ...

5. 阿里云CDN技术掌舵人文景：相爱相杀一路狂奔的这十年

   导读:提到阿里云CDN,不得不提技术掌舵人姚伟斌(文景),虽然他不是团队中最“老”的同学,但他却历经了淘宝业务发展最为飞速的几年,见证了从最初服务淘宝和集团内部的CDN,到如今国内服务客户最多的云CD ...

6. js实现开关灯游戏

   需求: 点击三个按钮,页面出现不同数量的“灯” 所有的灯有相同的点击效果.点击一个灯的时候,this和他的上下左右都会变成另一种背景色. 代码在这里~~~ 文章地址 https://www.cnblo ...

7. Bi-LSTM-CRF for Sequence Labeling

   做了一段时间的Sequence Labeling的工作,发现在NER任务上面,很多论文都采用LSTM-CRFs的结构.CRF在最后一层应用进来可以考虑到概率最大的最优label路径,可以提高指标. 一 ...

8. java分配内存空间

   分配内存空间 数组名=new 数据类型[数组长度]: new关键字用来实现为数组或对象分配内存 (堆内存) 数组具有固定的长度.获取数组的长度: 数组名.length 定义数组+分配内存空间 数据类型 ...

9. laravel 是怎么做到运行 composer dump-autoload 不清空 classmap 映射关系的呢？

   我看 laravel 的 composer.json 文件 autoload 也没配置 vendor/autoload_classmap.php 里的映射关系,正常来说,如果没有配置,执行 compo ...

10. [C++] 烦人的error LNK2019和error LNK2001

    常见原因: 没有正确的设置引用的lib,新手常犯这个错误,这是最容易解决的问题. extern "C"的问题.如果C++写的dll要给C程序用,那么就要注意extern &quot ...