TJOI2011 卡片

题目描述

桌子上现在有m张蓝色卡片和n张红色卡片,每张卡片上有一个大于1的整数。现在你要从桌子上拿走一些卡片,分若干次拿。每次只能拿走一组卡片:这组卡片颜色不同,并且两张卡片上面的数字的最大公约数大于1。问:最多可以从桌上拿走多少张卡片。

输入输出格式

输入格式:

每个输入文件中包含多组测试数据,每个文件中测试数据的数目不超过100。

文件的第一行读入一个整数T,为数据组数。

每组数据的格式如下:

m n

b1 b2 … bm

r1 r2 … rn

第二行给出每张蓝色卡片上面的数字,第三行给出每张红色卡片上的数字。

输出格式:

对每组测试数据,输出最多可以拿走多少张卡片。

输入输出样例

输入样例#1:

7
4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961

输出样例#1:

3
1
0
4
9
18
85

说明

对100%的数据:1<=t<=100;

1<=m,n<=500;

卡片上的数字大于1,小于10 000 000。

题目分析

全网都搜不到题解,连题面都搜不到,真是一件悲伤的事。
正解是网络流,但模型建的不对可能会导致TLE,虽然数据规模看起来是能过的。
首先我们来想一种比较简单的建模方式,将两边GCD>1的点连一条容量为1的弧,然后去跑Dinic,亲测70分。

70分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# define R register
# define LL long long
# define inf 2000101900

using namespace std;

queue <int> q;
int n,m,s,t,e,a[510],b[510],h[1010],v[1010],ans,T,used[1010];
struct zx{int v,flow,pre;} ed[2000010];

template <typename T> void in(R T& a){
R T x=0,f=1; R char c = getchar();
while(!isdigit(c)){if(c == '-') f=-1; c = getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline int gcd(R int x,R int y){return y==0? x:gcd(y,x%y);}

inline void add(R int x,R int y,R int z){
ed[++e] = (zx){y,z,h[x]};
h[x] = e;
}

inline bool bfs(){
memset(v,0,sizeof(v));
q.push(s);
v[s] = 1;
while(!q.empty()){
R int x = q.front();
q.pop();
for(R int i=h[x]; i!=-1; i=ed[i].pre)
{
R int p = ed[i].v;
if(v[p] || !ed[i].flow) continue;
v[p] = v[x]+1;
q.push(p);
}
}
return v[t];
}

inline int maxflow(R int x,R int want){
if(!want || x == t) return want;
R int flow = 0;
for(R int i=used[x]; i!=-1; i=ed[i].pre)
{
R int p = ed[i].v;
if(v[p] != v[x]+1|| !ed[i].flow) continue;
R int f = maxflow(p,min(ed[i].flow,want));
if(!f) continue;
want -= f;
flow += f;
ed[i].flow -= f;
ed[i^1].flow += f;
}
return flow;
}

int main(){
in(T);
while(T--){
memset(h,-1,sizeof(h));
e=-1,ans=0;
in(m),in(n);
s=0,t=m+n+1;
for(R int i=1; i<=m; ++i) in(a[i]);
for(R int i=1; i<=n; ++i) in(b[i]);
for(R int i=1; i<=m; ++i)
{
add(s,i,1);
add(i,s,0);
}
for(R int i=1; i<=n; ++i)
{
add(i+m,t,1);
add(t,i+m,0);
}
for(R int i=1; i<=m; ++i)
for(R int j=1; j<=n; ++j)
if(gcd(a[i],b[j]) != 1) add(i,j+m,1),add(j+m,i,0);
while(bfs()){
memcpy(used,h,sizeof(h));
ans += maxflow(s,inf);
}
printf("%d\n",ans);
}
return 0;
}

以上就是比较简单的网络流,用二分图也能解出来,但是n^2去建边是导致TLE的直接原因,因此我们就要考虑更换一种建模方式。
我们再来考虑,对于两个数字,如果他们的GCD>1,就意味着他们有至少一个共同的质因子,因此我们可以想,能否借助这个性质来建模呢?
我们可以先将每一个数都质因数分解,然后将所有出现过的质因数都放在一个集合里紧接着,对于每一个数字,我们将它与所有的因子各建一条容量为1的弧(当然,数字颜色不同时弧的方向也是不同的),然后超级源连向一种颜色,超级汇连向另外一种颜色,按照这样的模型再去跑Dinic,就可以通过了。

AC代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# define R register
# define LL long long
# define inf 2000101900

using namespace std;

queue <int> q;
int n,m,s,t,e,h[10010],v[10010],ans,T,used[10010];
int pri[664580],p,phi[1010][1010],pos[664580],cnt,num;
struct zx{int v,flow,pre;} ed[2000010];
bool vis[10000010];

template <typename T> void in(R T& a){
R T x=0,f=1; R char c = getchar();
while(!isdigit(c)){if(c == '-') f=-1; c = getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline void add(R int x,R int y,R int z){
ed[++e] = (zx){y,z,h[x]};
h[x] = e;
}

inline bool bfs(){
memset(v,0,sizeof(v));
q.push(s);
v[s] = 1;
while(!q.empty()){
R int x = q.front();
q.pop();
for(R int i=h[x]; i!=-1; i=ed[i].pre)
{
R int p = ed[i].v;
if(v[p] || !ed[i].flow) continue;
v[p] = v[x]+1;
q.push(p);
}
}
return v[t];
}

inline int maxflow(R int x,R int want){
if(!want || x == t) return want;
R int flow = 0;
for(R int i=used[x]; i!=-1; i=ed[i].pre)
{
R int p = ed[i].v;
if(v[p] != v[x]+1|| !ed[i].flow) continue;
R int f = maxflow(p,min(ed[i].flow,want));
if(!f) continue;
want -= f;
flow += f;
ed[i].flow -= f;
ed[i^1].flow += f;
}
return flow;
}

int main(){
for(R int i=2; i<=10000000; ++i)
{
if(!vis[i]) pri[++p] = i;
for(R int j=1; j<=p&&i*pri[j]<=10000000; ++j)
{
vis[i*pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
in(T);
while(T--){
memset(h,-1,sizeof(h));
e=-1,ans=0;
in(m),in(n);
cnt = 0;
memset(phi,0,sizeof(phi));
for(R int i=1; i<=m+n; ++i)
{
in(num);
for(R int j=1; j<=p&&num>=pri[j]; ++j)
{
if(num%pri[j] == 0) pos[++cnt] = pri[j],phi[i][++phi[i][0]] = pri[j];
while(num%pri[j] == 0) num /= pri[j];
}
}

sort(pos+1,pos+cnt+1);
cnt = unique(pos+1,pos+cnt+1)-pos-1;
s=0,t=m+n+cnt+1;

for(R int i=1; i<=m; ++i)
{
add(s,i,1);
add(i,s,0);
}
for(R int i=m+1; i<=m+n; ++i)
{
add(i,t,1);
add(t,i,0);
}
for(R int i=1; i<=m; ++i)
{
for(R int j=1; j<=phi[i][0]; ++j)
{
R int cs = lower_bound(pos+1,pos+cnt+1,phi[i][j])-pos+n+m;
add(i,cs,1);
add(cs,i,0);
}
}

for(R int i=m+1; i<=m+n; ++i)
{
for(R int j=1; j<=phi[i][0]; ++j)
{
R int cs = lower_bound(pos+1,pos+cnt+1,phi[i][j])-pos+n+m;
add(cs,i,1);
add(i,cs,0);
}
}
while(bfs()){
memcpy(used,h,sizeof(h));
ans += maxflow(s,inf);
}
printf("%d\n",ans);
}
return 0;
}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目描述
  2. 2. 输入输出格式
    1. 2.1. 输入格式:
    2. 2.2. 输出格式:
  3. 3. 输入输出样例
    1. 3.0.1. 输入样例#1:
    2. 3.0.2. 输出样例#1:
  • 4. 说明
  • 5. 题目分析
  • 6. 70分代码
  • 7. AC代码如下:
  • ,