CF516E Drazil and His Happy Friends

设 \(d=\gcd(n,m)\),得在同一天一起玩的男生女生的编号一定在\(\bmod d\) 的意义下相等,那么男生女生的编号按\(\bmod d\) 的值分组,考虑每一组的答案,取 \(\max\) 即为所求。

由裴蜀定理得,每组只要有一个人快乐,那么最后组内所有人都会快乐。根据抽屉定理,当 \(d>b+g\) 时肯定无解。

每一组的答案为组内最后一个男生快乐的时刻和最后一个女生快乐的时刻取 \(\max\)。先考虑女生对答案的贡献,男生的情况用同样的方法处理即可。

发现在第 \(i\) 天时,第 \(i \bmod m\) 个女生是快乐的,其会通过第 \(i \bmod n\) 个男生在 \(n\) 天后使第 \((i+n) \bmod m\) 个女生快乐。考虑同余最短路,将所有女生看作点,有三种连边情况:

女生 \(i\) 向女生 \((i+n) \bmod m\) 连边权为 \(n\) 的边。

若女生 \(i\) 初始就快乐,则源点 \(S\) 向 \(i\) 连边权为 \(i\) 的边。

若男生 \(i\) 初始就快乐,则源点 \(S\) 向 \(i \bmod m\) 连边权为 \(i\) 的边。

求解最短路后,所有点的距离最大值即为所求。但点数过大,无法直接跑最短路。发现第一种边将整个图连成了一个环,那么所有从源点连向的点再从环上往前一步的点才有可能成为最后的距离最大值的点,因为到达这些点需要绕过更长的距离。将源点连向的点用 \(exgcd\) 重编号后排序即可快速求解。

#include<bits/stdc++.h>
#define maxn 400010
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
ll n,m,b,g,d,ans;
ll id1[maxn],id2[maxn];
vector<ll> v1[maxn],v2[maxn];
map<ll,ll> dis;
struct node
{
    ll val,id;
};
vector<node> ve;
bool cmp(const node &a,const node &b)
{
    return a.id<b.id;
}
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
ll solve(vector<ll> a,vector<ll> b)
{
    if(b.size()==m) return -1;
    ll v=0,x,y,s;
    exgcd(n,m,x,y),x=(x%m+m)%m,dis.clear(),ve.clear();
    for(int i=0;i<b.size();++i) dis[b[i]]=b[i];
    for(int i=0;i<a.size();++i)
    {
        if(dis.count(a[i]%m)) dis[a[i]%m]=min(dis[a[i]%m],a[i]);
        else dis[a[i]%m]=a[i];
    }
    s=(*dis.begin()).first;
    for(map<ll,ll>::iterator it=dis.begin();it!=dis.end();++it)
        ve.push_back({(*it).second,x*((*it).second-s)%m});
    sort(ve.begin(),ve.end(),cmp);
    for(int i=1;i<ve.size();++i) v=max(v,ve[i-1].val+(ve[i].id-ve[i-1].id-1)*n);
    if(ve.size()==1) v=ve[0].val+(m-1)*n;
    else v=max(v,ve[ve.size()-1].val+(m-ve[ve.size()-1].id-1)*n);
    return v;
}
int main()
{
    read(n),read(m);
    read(b);
    for(int i=1;i<=b;++i) read(id1[i]);
    read(g);
    for(int i=1;i<=g;++i) read(id2[i]);
    d=gcd(n,m),n/=d,m/=d;
    if(d>b+g)
    {
        puts("-1");
        return 0;
    }
    for(int i=1;i<=b;++i) v1[id1[i]%d].push_back(id1[i]/d);
    for(int i=1;i<=g;++i) v2[id2[i]%d].push_back(id2[i]/d);
    for(int i=0;i<d;++i)
    {
        if(v1[i].empty()&&v2[i].empty())
        {
            puts("-1");
            return 0;
        }
    }
    for(int i=0;i<d;++i)
    {
        ll v=solve(v1[i],v2[i]);
        if(~v) ans=max(ans,d*v+i);
    }
    swap(n,m);
    for(int i=0;i<d;++i)
    {
        ll v=solve(v2[i],v1[i]);
        if(~v) ans=max(ans,d*v+i);
    }
    printf("%lld",ans);
    return 0;
}
上一篇:shell编程--2


下一篇:shell传递参数