【图论】【贪心】【搜索】[Atcoder Grand Contest 022]C Remainder Game

题意：

给出一个初始数组A，以及目标数组B，现在要把A的每个值改为B中相应的值，更改的方式如下：
选择一个数x，对任意一个 A中的数$a_i$，可以改为$a_i\space mod\space x$，可以不改，但代价均为$2^x$
求最小代价，或无解输出-1
数组A的大小$n\leq 50$
$a_i\leq 50$

分析：

由于更改方式是取模，所以必然不可能先选择一个小的数，再选择比它大的数，也就是说，选择的数必然是严格递减的，那么很显然一个数不可能被选择多次了。

因为代价为$2^x$，很容易发现$2^0+2^1+2^2+……+2^{x-1}<2^x$，也就是说，如果选择了这个数，就必然满足：选择所有比它小的数都无法得到B数组。

根据这个性质，我们可以贪心地计算了。
初始状态下，所有数都在我们选中的数集$S$中（即包含从2到50所有整数）
对每个点$a_i$，向$a_i\space mod\space S_i$连一条有向边。
判断每个A中的数，是否能够到达相应的B中的数即可，判断方式可以暴搜。

然后，在S中删去当前最大的数，重新建图，判断是否能够满足，如果可以，则删去最大的数，否则把它加回来。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#define SF scanf
#define PF printf
#define MAXN 60
using namespace std;
typedef long long ll;
bool used[MAXN],vis[MAXN];
ll ans;
int A[MAXN],B[MAXN],n;
bool w[MAXN][MAXN];
void build(){for(int i=1;i<=50;i++)if(used[i]==1){for(int j=0;j<=50;j++)w[j][j%i]=1;}
}
void dfs(int x){vis[x]=1;for(int i=0;i<=50;i++)if(w[x][i]==1&&vis[i]==0)dfs(i);
}
bool check(){for(int i=0;i<n;i++){memset(vis,0,sizeof vis);dfs(A[i]);if(vis[B[i]]==0)return 0;}return 1;
}
int main(){SF("%d",&n);for(int i=0;i<n;i++)SF("%d",&A[i]);for(int i=0;i<n;i++)SF("%d",&B[i]);for(int i=1;i<=50;i++)used[i]=1;build();if(check()==0){PF("-1\n");return 0;}for(int i=50;i>=0;i--){memset(w,0,sizeof w);used[i]=0;build();if(check()==0){used[i]=1;ans+=(1ll<<i);}}PF("%lld",ans);
}