0%

CF516E Drazil and His Happy Friends

发表于 更新于 阅读次数： Valine：

题目链接

首先，设 \(d=\gcd(n,m)\)，由简单的数论知识可知，在任意一天一起玩的男生和女生编号在\(\bmod d\) 意义下同余。所以我们可以把所有男生和女生按模 \(d\) 的值分组，然后我们只考虑同一组内的情况，即我们把其他组的人都抽出去，那么若求得 \(r\) 这一组子问题的答案为 \(t\)，那么在原问题中这组的答案即为 \(dt+r\)（当第 \(0\) 天就合法时需要特判）。然后我们只需要对所有组的答案取 \(\max\)。

由裴蜀定理可知，只要一开始有一个人是快乐的，那么最后所有人都会变快乐。由于只有 \(b+g\) 个人快乐，所以当 \(d>b+g\) 时肯定至少有一组初始状态没有人快乐，这样 \(\gcd(n,m)\) 过大时我们直接输出 -1 就好了。

现在我们只需要考虑 \(\gcd(n,m)=1\) 的情况。我们考虑分别算出最后一个男生和最后一个女生的变快乐的时间，然后取 \(\max\)。先考虑女生的情况，男生类似。

我们发现，如果在第 \(i\) 天，第 \(i\bmod m\) 个女生是快乐的，那么第 \(i\) 天结束时，第 \(i\bmod n\) 个男生也一定是快乐的，那么我们考虑过了 \(n\) 天以后，第 \(i\bmod n\) 个男生会让第 \((i+n)\bmod m\) 个女生变快乐。

那么这可以等价于：\(n\) 天以后，第 \(i\bmod m\) 个女生让第 \((i+n)\bmod m\) 个女生变快乐了。所以，如果第 \(i\) 个女生在某一天变快乐了，那么 \(n\) 天后，第 \((i+n)\bmod m\) 个女生也一定会快乐。那么我们把这个建成最短路模型：

  • 对每个女生 \(k\) 我们向第 \((k+n)\bmod m\) 个女生连一条边权为 \(n\) 的边，这相当于某时刻 \(k\) 变得快乐，那么 \(k+n\) 时刻 \((k+n)\bmod m\) 会快乐。

  • 对每个一开始就快乐的女生 \(k\)，从源点 \(S\) 向 \(k\) 连一条边权为 \(k\) 的边。

  • 对每个一开始就快乐的男生 \(k\)，从 \(S\) 向 \(k\bmod m\) 连一条边权为 \(k\) 的边，即时刻 \(k\) 第 \(k\bmod m\) 个女生会因该男生变快乐。

这样跑从 \(S\) 开始的最短路，求每个点的 \(dis\) 的 \(\max\) 就是答案。

但是我们发现点数是 \(10^9\) 级别的，没法跑，我们观察这个图的性质：第一类边把所有除 \(S\) 以外的点练成了一个大环，我们认为 \(S\) 直接连向的点为关键点，那么关键点的 \(dis\) 即为 \(S\) 连向这个点的边权。我们考虑把所有关键点按在环上的顺序排序（可以通过 exgcd 来实现），那么对于连续的两个关键点 \(A,B\)，显然 \(B\) 前面的那个点是 \(AB\) 这一段之间 \(dis\) 最大的，我们对所有连续的点对都做一遍取 \(\max\) 就是答案。

代码：

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,b,g,d,x[100005],y[100005];
typedef long long ll;
ll c[200005];
typedef pair<int,int> pii;
vector<int>V[200005],W[200005];
struct node
{
    ll x,y,z;
};
vector<node>buc;
map<int,int>mp;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void exgcd(int a,int b,int &x,int &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=(a/b)*x;}
bool cmp(node x,node y){return x.z<y.z;}
ll solve(vector<int>v,vector<int>w)
{
    if(w.size()==m)return -1;
    if(v.size()==0&&w.size()==0)return -2;
    ll ans=0;
    mp.clear();
    for(auto i:w)mp[i]=i;
    for(auto i:v)
        if(mp.find(i%m)==mp.end())mp[i%m]=i;
        else mp[i%m]=min(mp[i%m],i);
    buc.clear();
    int t1,t2;
    for(auto i:mp)
    {
        buc.push_back(node{i.first,i.second,0});
        exgcd(n,m,t1,t2);
        long long t=1ll*t1*i.first;
        t+=1ll*m*ceil(1.0*(1-t)/m);
        if(t==m)t-=m;
        buc[buc.size()-1].z=t;
    }
    sort(buc.begin(),buc.end(),cmp);
    for(int i=1;i<buc.size();i++)
        ans=max(ans,buc[i-1].y+1ll*(buc[i].z-buc[i-1].z-1)*n);
    if(buc.size()>1)ans=max(ans,buc[buc.size()-1].y+1ll*(m-buc[buc.size()-1].z+buc[0].z-1)*n);
    else ans=1ll*(m-1)*n+buc[0].y;
    return ans;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    scanf("%lld",&b);
    for(int i=1;i<=b;i++)scanf("%lld",&x[i]);
    scanf("%lld",&g);
    for(int i=1;i<=g;i++)scanf("%lld",&y[i]);
    d=gcd(n,m);
    if(d>b+g){puts("-1");return 0;}
    for(int i=1;i<=b;i++)V[x[i]%d].push_back(x[i]/d);
    for(int i=1;i<=g;i++)W[y[i]%d].push_back(y[i]/d);
    n/=d,m/=d;
    ll ans=0;
    for(int i=0;i<d;i++)
    {
        ll t=solve(V[i],W[i]);
        if(t==-2){puts("-1");return 0;}
        if(t==-1)continue;
        ans=max(ans,t*d+i);
    }
    swap(n,m);
    for(int i=0;i<d;i++)
    {
        ll t=solve(W[i],V[i]);
        if(t==-1)continue;
        ans=max(ans,t*d+i);
    }
    printf("%lld\n",ans);
    return 0;
}