LightOJ-1356 Prime Independence 质因子分解+二分图最大独立集
感觉这道题挺好的,数论+图论。就是我太菜了,怎么都写不对啊啊啊55555...
先一搜题目,发现这道题用质因子分解+二分图最大独立集,好巧妙啊_(:з」∠)_
二分图最大独立集=顶点数-最大匹配数(用Hopcroft-Carp算法,匈牙利算法会TLE...)
然后自己琢磨出如下思路:(用到了“拆点”)
但是仍然TLE了QAQ...附上TLE的代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define pb push_back
const int INF=0x3f3f3f3f;
const int MAXN=40005;
int n,a[MAXN];
map<int,int>mp;
const int MAX=500005;
int pri[MAX+1];
void getp()//得到MAX内的素数
{
memset(pri,0,sizeof(pri));
for(int i=2;i<MAX;i++)
{
if(!pri[i])
pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<MAX;j++)
{
pri[i*pri[j]]=1;
if(i%pri[j]==0)
break;
}
}
}
vector<int>g[MAXN];
int un;
int mx[MAXN],my[MAXN];
int dx[MAXN],dy[MAXN];
int dis;
bool used[MAXN];
bool SearchP()
{
queue<int>Q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=0;i<un;i++)
if(mx[i]==-1)
{
Q.push(i);
dx[i]=0;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(dx[u]>dis)
break;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(dy[v]==-1)
{
dy[v]=dx[u]+1;
if(my[v]==-1)
dis=dy[v];
else
{
dx[my[v]]=dy[v]+1;
Q.push(my[v]);
}
}
}
}
return dis!=INF;
}
bool dfs(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!used[v]&&dy[v]==dx[u]+1)
{
used[v]=true;
if(my[v]!=-1&&dy[v]==dis)
continue;
if(my[v]==-1||dfs(my[v]))
{
my[v]=u;
mx[u]=v;
return true;
}
}
}
return false;
}
int MaxMatch()
{
int res=0;
un=n;
memset(mx,-1,sizeof(mx));
memset(my,-1,sizeof(my));
while(SearchP())
{
memset(used,false,sizeof(used));
for(int i=0;i<un;i++)
if(mx[i]==-1&&dfs(i))
res++;
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
getp();
for(int tt=1;tt<=t;tt++)
{
scanf("%d",&n);
for(int i=0;i<=n;i++)
g[i].clear();
int ma=-1;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
ma=max(ma,a[i]);
}
for(int i=0;i<ma;i++)//注意不是到n!到ma!
mp[i]=-1;//因为下标从0开始
for(int i=0;i<n;i++)
mp[a[i]]=i;
//建图
for(int i=0;i<n;i++)
{
for(int j=1;j<=pri[0];j++)
{
if(pri[j]>a[i])
break;
if(a[i]%pri[j]==0)
{
int k=a[i]/pri[j];
//cout<<"i="<<i<<" a[i]="<<a[i]<<" pri[j]="<<pri[j]<<" k="<<k<<" mp[k]="<<mp[k]<<endl;
if(mp[k]==-1)
continue;
g[i].pb(mp[k]);
g[mp[k]].pb(i);
}
}
}
int res=MaxMatch();
//cout<<"res="<<res<<endl;
int ans=(n*2-res)/2;
printf("Case %d: %d\n",tt,ans);
}
return 0;
}
后来想想应该是建图部分复杂度有点高了,于是进行优化,只搜到sqrt(a[i])。以sqrt(a[i])为界,分为质数×合数、质数×质数、合数×质数三种情况,然后注意特判1。另外加上了一个判断MAX内的数字是否为素数的函数和数组。附上部分改后的代码:
bool isp[MAX];
void init()//判断是否为素数
{
memset(isp,true,sizeof(isp));
isp[0]=isp[1]=false;
for(int i=2;i<MAX;i++)
{
if(isp[i])
for(int j=i+i;j<MAX;j+=i)
isp[j]=false;
}
}
//建图
for(int i=0;i<n;i++)
{
for(int j=1;j<=pri[0];j++)
{
if(pri[j]>sqrt(1.0*a[i]))
break;
if(a[i]%pri[j]==0)
{
int k=a[i]/pri[j];
if(mp[k]!=-1)
{
g[i].pb(mp[k]);
g[mp[k]].pb(i);
}
if(k*pri[j]==a[i])
break;
if(isp[k]&&mp[pri[j]]!=-1)//如果k为质数才加边
{
g[i].pb(mp[pri[j]]);
g[mp[pri[j]]].pb(i);
}
}
}
//解决4,97,388这种情况
for(int k=4;k<=sqrt(1.0*a[i]);k++)
{
if(mp[k]==-1)
continue;
if(isp[k])//上边扫过了
continue;
if(a[i]%k)
continue;
if(isp[a[i]/k])
{
g[i].pb(mp[k]);
g[mp[k]].pb(i);
}
}
}
if(mp[1]!=-1)//特判1
for(int i=0;i<n;i++)
if(isp[a[i]])
{
g[mp[1]].pb(i);
g[i].pb(mp[1]);
}
但最后还是TLE了55555...没办法去搜网上的题解,发现大部分都说用“奇偶性建图”,好神奇的操作_(:з」∠)_ 但是我不会啊QAQ...好不容易找到了拆点建图的题解,附上大佬博客Orz:
http://www.cnblogs.com/xiuwenli/p/9520421.html
发现其实就是自己质因子分解弄复杂了。。用到Pollard Rho算法,附上讲解博客Orz:
https://www.cnblogs.com/vipchenwei/p/7123217.html
改了改,就过了。。另外这次我把点集的起始下标改为从1开始了(方便map初始化)。
附上AC代码:(真不容易啊QAQ...我好菜啊啊啊55555...)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define pb push_back
const int INF=0x3f3f3f3f;
const int MAXN=40005;
int n,a[MAXN];
map<int,int>mp;
const int MAX=500005;
int pri[MAX+1];
void getp()//得到MAX内的素数
{
memset(pri,0,sizeof(pri));
for(int i=2;i<MAX;i++)
{
if(!pri[i])
pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<MAX;j++)
{
pri[i*pri[j]]=1;
if(i%pri[j]==0)
break;
}
}
}
vector<int>g[MAXN];
int un;
int mx[MAXN],my[MAXN];
int dx[MAXN],dy[MAXN];
int dis;
bool used[MAXN];
bool SearchP()
{
queue<int>Q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=1;i<=un;i++)
if(mx[i]==-1)
{
Q.push(i);
dx[i]=0;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(dx[u]>dis)
break;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(dy[v]==-1)
{
dy[v]=dx[u]+1;
if(my[v]==-1)
dis=dy[v];
else
{
dx[my[v]]=dy[v]+1;
Q.push(my[v]);
}
}
}
}
return dis!=INF;
}
bool dfs(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!used[v]&&dy[v]==dx[u]+1)
{
used[v]=true;
if(my[v]!=-1&&dy[v]==dis)
continue;
if(my[v]==-1||dfs(my[v]))
{
my[v]=u;
mx[u]=v;
return true;
}
}
}
return false;
}
int MaxMatch()
{
int res=0;
un=n;
memset(mx,-1,sizeof(mx));
memset(my,-1,sizeof(my));
while(SearchP())
{
memset(used,false,sizeof(used));
for(int i=1;i<=un;i++)
if(mx[i]==-1&&dfs(i))
res++;
}
return res;
}
int fac[MAXN];
void addedge(int num,int id)
{
int tmp=num;
int tot=0;
for(int j=1;j<=pri[0];j++)
{
if(pri[j]*pri[j]>tmp)
break;
if(tmp%pri[j]==0)
{
fac[tot++]=pri[j];
while(tmp%pri[j]==0)
tmp/=pri[j];
}
}
if(tmp>1)//最后一个质因数
fac[tot++]=tmp;
for(int i=0;i<tot;i++)
{
int x=num/fac[i];
//cout<<"i="<<i<<" fac="<<fac[i]<<" x="<<x<<endl;
if(mp[x])
{
g[id].pb(mp[x]);
g[mp[x]].pb(id);
}
}
}
int main()
{
int t;
scanf("%d",&t);
getp();
for(int tt=1;tt<=t;tt++)
{
scanf("%d",&n);
for(int i=0;i<=n;i++)
g[i].clear();
mp.clear();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
mp[a[i]]=i;
}
for(int i=1;i<=n;i++)
addedge(a[i],i);
int res=MaxMatch();
//cout<<"res="<<res<<endl;
int ans=(n*2-res)/2;
printf("Case %d: %d\n",tt,ans);
}
return 0;
}