P9589 「PFLOI R1」PFL 除法
题目背景
有必要把所有比赛题的背景连在一起。
就这样，新世界的大门向它们敞开了……
“喵！”一只可爱的花猫向它们问好。
“你们刚来到这？”
“嗯。”
“我带你们去转转吧，谁叫我这么可爱呢！”
“……” 花猫突然止住，打量一番手中的序列，俶尔又微笑着说：
“但你们要先答出我的问题哦。”
题目描述
花猫有一个长度为
n
n
n 的序列
A
A
A 和另一个长度为
m
m
m 的序列
B
B
B。你可以进行若干次以下操作：
- 选择两个整数
i
i
i 和j
j
j，满足1
≤
i
≤
n
1\\le i\\le n
1≤i≤n，1
≤
j
≤
m
1\\le j\\le m
1≤j≤m 且B
j
∣
A
i
B_j \\mid A_i
Bj∣Ai，然后将A
i
A_i
Ai 变为A
i
B
j
\\frac{A_i}{B_j}
BjAi。
注意：
A
A
A 和
B
B
B 中的每个元素都可以选择并被操作多次。
最终要使得
A
A
A 中的元素都相等，请求出最少的操作次数；若无解，输出 -1。
输入格式
第一行两个正整数
n
n
n 和
m
m
m。
第二行
n
n
n 个正整数表示序列
A
A
A。
第三行
m
m
m 个正整数表示序列
B
B
B。
输出格式
输出一个整数表示最少的操作次数；若无解，输出 -1。
输入输出样例 #1
输入 #1
4 5
16 24 28 36
11 4 7 3 2
输出 #1
6
输入输出样例 #2
输入 #2
2 3
11 13
13 1 11
输出 #2
2
输入输出样例 #3
输入 #3
2 2
2 3
4 5
输出 #3
-1
说明/提示
本题采用捆绑测试。
|
1 1 1 |
A A A 中所有元素相等 |
5 5 5 |
|
2 2 2 |
n = 2 n=2 n=2 |
15 15 15 |
|
3 3 3 |
n , m ≤ 10 3 n,m\\le10^3 n,m≤103 |
20 20 20 |
|
4 4 4 |
n , m ≤ 10 4 n,m\\le10^4 n,m≤104 |
20 20 20 |
|
5 5 5 |
无 |
40 40 40 |
对于所有数据，
1
≤
n
,
m
≤
5
×
10
5
1\\le n,m\\le5\\times10^5
1≤n,m≤5×105，
1
≤
A
i
,
B
i
≤
5
×
10
5
1\\le A_i,B_i\\le5\\times10^5
1≤Ai,Bi≤5×105。
C++实现
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e5+5;
int n,m,ans=inf,a[N],b[N],V,dp[N];
inline int get(int x){
int s=0;
for(int i=1;i<=n;++i){
if(a[i]%x)
return inf;
if(dp[a[i]/x]==inf)
return inf;
s+=dp[a[i]/x];
}
return s;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i],V=max(V,a[i]);
for(int i=1;i<=m;++i)
cin>>b[i],V=max(V,b[i]);
sort(a+1,a+n+1);
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)–b–1;
memset(dp,inf,sizeof(dp)),dp[1]=0;
for(int i=1;i<=m;++i)
for(int s=b[i];s<=V;s+=b[i])
dp[s]=min(dp[s],dp[s/b[i]]+1);
for(int i=1;i<=a[1]/i;++i)
if(a[1]%i==0)
ans=min({ans,get(i),get(a[1]/i)});
if(ans==inf)
ans=–1;
cout<<ans<<endl;
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
