首页 > 其他分享 >P2065 [TJOI2011] 卡片 题解

P2065 [TJOI2011] 卡片 题解

时间:2024-02-28 13:12:54浏览次数:28  
标签:pr 卡片 read 题解 rep P2065 因子 TJOI2011 add

看大家建图时中间都连了质数点,发一个不用质数点的解法。

我们可以先从源点向每一个蓝色卡片对应的点连一条边,再从每一个红色卡片对应的点向汇点连一条边。

如果两张卡片可以一起拿走,那就在它们之间连一条边(蓝色连到红色),这些边的最大流量都是 \(1\)。建好图以后我们就可以直接用 Dinic 求出答案。

但是重点不在这里,如果你直接枚举 \(i\) 和 \(j\) 然后判断 \(\gcd(b_i,r_j)\) 是否大于 \(1\),你只能拿到 70pts

我们可以先用线性筛求出每一个数的最小质因子和这个数除去这个最小质因子的几次方以后对应的数。

具体的,我们可以用 \(pr[i]\) 表示 \(i\) 这个数除去它的最小质因子的几次方以后对应的数,我们用 \(d[i]\) 表示 \(i\) 的最小质因子。

如果 \(d[i]=d[i/d[i]]\),我们就令 \(pr[i]=pr[i/d[i]]\),否则 \(pr[i]=i/d[i]\)。

接下来如果我们要判断两个数 \(x\) 和 \(y\) 是否有公共的质因子,我们可以先判断 \(d[x]\) 是否整除 \(y\),然后再令 \(x=pr[x]\),回到刚刚的操作,重复直到 \(x=1\)。

代码:

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int T,n,m,s,t,l,r,cnt,tot,ans,a[502],b[502],d[1003],q[1003],p[664581],d1[10000002],pr[10000002];
int vr[502000],ed[502000],nx[502000],now[1003],hd[1003];
inline void add(int x,int y,int z){
	vr[++tot]=y,ed[tot]=z,nx[tot]=hd[x],hd[x]=tot;
	vr[++tot]=x,ed[tot]=0,nx[tot]=hd[y],hd[y]=tot;
}
bool bfs(){
	memset(d,0,sizeof(d));
	d[s]=1,now[s]=hd[s];
	l=r=1,q[1]=s;
	while(l<=r){
		int x=q[l++];
		for(int i=hd[x],y;i;i=nx[i])if(ed[i]&&!d[y=vr[i]]){
			d[y]=d[x]+1,now[y]=hd[y];
			if(y==t)return 1;
			q[++r]=y;
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t)return flow;
	int rest=flow,num,i,y;
	for(i=now[x];i;i=nx[i])if(ed[i]&&d[y=vr[i]]==d[x]+1){
		num=dinic(y,min(rest,ed[i]));
		if(num){
			ed[i]-=num,ed[i^1]+=num;
			rest-=num;
			if(!rest)break;
		}else d[y]=0;
	}
	now[x]=i;
	return flow-rest;
}
inline bool check(int x,int y){
	while(x!=1){
		if(y%d1[x]==0)return 1;
		x=pr[x];
	}
	return 0;
}
signed main(){
	rep(i,2,10000000){
		if(!d1[i])d1[i]=i,p[++cnt]=i;
		pr[i]=d1[i]==d1[i/d1[i]]?pr[i/d1[i]]:i/d1[i];
		rep(j,1,cnt){
			if(p[j]>d1[i]||p[j]>10000000/i)break;
			d1[p[j]*i]=p[j];
		}
	}
	T=read();
	while(T--){
		n=read(),m=read();
		s=0,t=n+m+1;
		tot=1;
		memset(hd,0,sizeof(hd));
		rep(i,1,n)a[i]=read();
		rep(i,1,m)b[i]=read(),add(i+n,t,1);
		rep(i,1,n){
			bool fl=0;
			rep(j,1,m)if(check(a[i],b[j]))add(i,j+n,1),fl=1;
			if(fl)add(0,i,1);
		}
		ans=0;
		while(bfs())ans+=dinic(0,0x7fffffff);
		printf("%d\n",ans);
	}
	return 0;
}

标签:pr,卡片,read,题解,rep,P2065,因子,TJOI2011,add
From: https://www.cnblogs.com/zifanoi/p/18039980

相关文章

  • CF111D Petya and Coloring 题解
    很明显这是一道组合题。首先特判一下,当\(m=1\)时,答案就是\(k^n\)。对于\(m>1\)的情况,我们可以得出一个结论:对于沿格子的线穿过的任何垂直线,会将棋盘分成两个非空的部分,这两个部分中的不同颜色的数量相同且总是不变。设这个不同颜色的数量为\(i\),那么左边这部分的颜色一定......
  • [USACO13MAR]Farm Painting S 题解
    看大家好多写的都用了四维偏序,给一个不用偏序的解法。简化一下题目,就是给你\(n\)个矩形,第\(i\)个矩形用\((x1_i,y1_i,x2_i,y2_i)\)表示,问你有多少个\(i\)满足:不存在另一个\(j\)使得\(x1_j\lex1_i\lex2_j\wedgey1_j\ley1_i\ley2_j\)。我们从左到右扫描每一个......
  • CF799D题解
    CF799D这里更容易进入且有翻译题意给定一个长宽为\(a\)和\(b\)的目标矩形、一个宽高为\(h\)和\(w\)的初始矩形及\(n\)个操作\(a_i\)。对于每个操作,可以将初始矩形的宽或高乘以\(a_i\),求使目标矩形能放入初始矩形的最少操作(目标矩形可以旋转90度)。解析这题算是......
  • [ABC303Ex] Constrained Tree Degree 题解
    AtCoder题面洛谷题面如果每个点的度数都知道了,那问题就转化成了P2290[HNOI2004]树的计数,直接求Prufer序列的个数即可,因为一个度数为\(d_i\)的点在Prufer序列中的出现次数是\(d_i-1\),所以答案是:\(\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}\)。可以把\((n-2)!\)放到......
  • [COI2009] PLAHTE 题解
    首先对于每一个矩形,若\(x_2<0\),就将\(x_1,x_2\)均乘上\(-1\)再交换,对于\(y_1,y_2\)也做同样的操作。我们建立一个操作序列a[0~1000],和一个数组\(d\),每一个操作用\((x,y)\)表示,就是在\(d\)内把所有\(0\)到\(x\)的位置加上\(y\)。我们再定义一种新的操作\([x,y......
  • [USACO11NOV]Binary Sudoku G 题解
    定义一个\(3\times3\)的表格\(a\),表示每个小九宫格内1的个数的奇偶状态。再定义两个长为\(9\)的数组\(c0,c1\),表示每行每列上1的个数的奇偶状态。当\(d_{i,j}\)取反时,会将\(a_{[\frac{i}{3}],[\frac{j}{3}]},c0_i,c1_j\)各取反一次。要将\(a_{i,j}\)全部变为0......
  • [ABC286Ex] Don't Swim 题解
    我们首先求出线段与多边形的交点,如果交点个数\(<2\)或者有无数个交点,则可以直接输出\(S\)到\(T\)之间的距离。接下来我们考虑交点个数为\(2\)的情况。为了方便,我们记距离\(S\)最近的那个交点为\(P_1\),远的为\(P_2\)。举个例子:在这个例子中,直线\(ST\)将整个多边......
  • P3577 [POI2014]TUR-Tourism 题解
    考虑在无向图上进行dfs,可以得到很多棵dfs树(因为图不一定连通),这些树形成了一个森林。然后由任意两点间不存在节点数超过\(10\)的简单路径这个限制可以得出这些树的深度都不超过\(10\),然后可以想到树上状压dp。有一个重要的性质,就是无向图dfs树上的非树边,一定是回边,所以......
  • CF516E Drazil and His Happy Friends 题解
    题目传送门记\(d=\gcd(n,m)\),发现只有编号在模\(d\)意义下相同的人之间会产生影响,那么有解当且仅当每个剩余系内有至少一个人是快乐的。所以在\(d>b+g\)时直接输出-1即可。对于剩下的情况,先令\(n\leftarrow\fracnd,m\leftarrow\fracmd\),如果\(n<m\)那么把男女交......
  • [ARC140F] ABS Permutation (Count ver.) 题解
    洛谷题面传送门AT题面传送门发现不太好直接求,考虑将\(P\)映射到\(P^{-1}\)上,这样题目中的条件就变成了\(|P_i-P_{i+M}|=1\)。因此我们可以对模\(M\)的每个剩余系做\(M=1\)的情况,然后最后快速幂合并。考虑\(M=1\)的情况怎么做。记\(f_i\)表示\(K=i\)的方案数,......