CF516E Drazil and His Happy Friends 题解

作者: xht37 分类: 题解 发布时间: 2019-12-11 20:18

点击数:119

CF516E Drazil and His Happy Friends

题意

  • 有 $n$ 个男生 $m$ 个女生,编号分别为 $0 \sim n – 1$ 和 $0 \sim m – 1$。
  • 有 $b$ 个男生和 $g$ 个女生是快乐的,其他人是不快乐的。
  • 在第 $i$ 天,编号为 $i \bmod n$ 的男生和编号为 $i \bmod m$ 的女生会一起玩。
  • 如果他们俩中有一个人是快乐的,则另一个人也会变快乐。
  • 求至少要多少天所有人都会变快乐,或者判断不可能所有人都变快乐。
  • $n,m \le 10^9$,$b,g \le 10^5$。

题解

首先考虑 $\gcd(n,m) \ne 1$,我们可以按照 $\bmod \gcd(n,m)$ 分组,不同组之间显然互不影响。

那么根据裴蜀定理,有解的充要条件为每组内至少有一个人是快乐的

若有解,将每一组的答案求出来后取 $\max$ 即可。

考虑某一组,此时不妨设 $n > m$,同时有 $\gcd(n,m) = 1$。

首先有一个结论:如果 $n$ 个男生都快乐了,那么除非当前天数小于 $m$,否则所有女生一定也都是快乐的。这是因为往前的 $m$ 天里,由于所有男生都快乐了,因此要么是原本就都快乐,要么是快乐的影响另一个。

那么我们只需要求出最后一个变快乐的男生即可。为了方便,如果女生 $x$ 初始快乐,那么将男生 $x$ 也标记为初始快乐。

对于一个男生 $x$,若它在第 $t$ 天变快乐,那么他就会通过女生 $t \bmod m$ 在第 $t+m$ 天使男生 $(t+m)\bmod n$ 变快乐。

考虑同余最短路,则有连边 $i \stackrel{m}{\longrightarrow} (i+m)\bmod n$。另外,建立一个虚拟源点 $S$,对于初始快乐的男生 $i$,有连边 $S \stackrel{i}{\longrightarrow} i$。

则最后所有点的最短路的最大值就是这一组的答案。

但是这样点数是 $10^9$ 级别的,无法承受。

注意到这样的建图方式实际上会形成一个,因此考虑删掉一些并不重要的点:如果 $i$ 和 $(i+m) \bmod n$ 初始都是不快乐的,那么 $i$ 一定会在 $(i+m) \bmod n$ 之前变快乐,因此 $i$ 就没用了。

那么我们可以只保留 $i$ 或 $(i+m) \bmod n$ 初始快乐的节点,这样点数只有 $10^5$ 级别了。

如何进行连边呢?

设 $i$ 初始快乐的节点为 $A$ 类点,编号为 $A_i$;$(i+m) \bmod n$ 初始快乐的节点为 $B$ 类点,编号为 $B_i$。

我们要连三类边:

  1. $S \stackrel{i}{\longrightarrow} A_i$
  2. $B_i \stackrel{m}{\longrightarrow} A_i$
  3. $A_i \stackrel{xm}{\longrightarrow} B_j$

第 $1,2$ 类边都很容易,问题在第 $3$ 类边上。要求出 $B_j$,求出 $A_j$ 即可,那么此时实际上问题转化为在模 $n$ 意义下以 $m$ 为跨度的有向环上,从每一个 $A_i$ 往后遇到的第一个 $A_j$ 是哪个

我们可以考虑 $i$ 最小的 $A_i$,求出从 $A_i$ 开始分别要经过多少个 $m$ 到达其他 $A$ 类点 $A_j$,即求 $i + xm \equiv j \pmod n$ 的最小非负整数解 $x$,使用 exgcd 即可。注意实现时其实只用求一次 exgcd。

求完后,对所有 $x$ 排序,即可求出环上 $A$ 类点依次被经过的顺序,也就求出了每一个 $A_i$ 往后遇到的第一个 $A_j$ 是哪个

这样第 $3$ 类边也能够连上了。

注意最后还要特判天数小于 $m$ 的情况。

总时间复杂度 $\mathcal O(n \log n)$。

代码

#define Fail return print(-1), 0

const int N = 1e5 + 7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, d, B, G, b[N], g[N];
vi a[N<<1], f[N<<1];
ll ans;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int exgcd(int a, int b, int &x, int &y, int d = 0) { return b ? (d = exgcd(b, a % b, y, x), y -= a / b * x, d) : (x = 1, y = 0, a); }

inline ll solve(vi a, vi b) {
    vi s = a;
    for (ui i = 0; i < b.size(); i++) s.pb(b[i]);
    sort(s.begin(), s.end());
    int k = unique(s.begin(), s.end()) - s.begin(), x, y;
    if (n == k) {
        int c[m];
        memset(c, 0, sizeof(c));
        for (ui i = 0; i < a.size(); i++) if (a[i] < m) ++c[a[i]];
        for (ui i = 0; i < b.size(); i++) if (b[i] < m) ++c[b[i]];
        for (int i = m - 1; ~i; i--) if (c[i] == 1) return i;
        return -1;
    }
    vector< pair< int, ll > > e[2*k+1];
    for (int i = 0; i < k; i++) e[2*k].pb(mp(i, s[i])), e[i+k].pb(mp(i, m));
    exgcd(m, n, x, y), x = (x % n + n) % n;
    pi p[k];
    for (int i = 0; i < k; i++) p[i] = mp(1ll * x * (s[i] - s[0]) % n, i);
    sort(p, p + k);
    for (int i = 0, j = 1 % k; i < k; i++, j = (++j == k) ? 0 : j) e[p[i].se].pb(mp(p[j].se + k, 1ll * m * (p[j].fi - p[i].fi - 1 < 0 ? p[j].fi - p[i].fi - 1 + n : p[j].fi - p[i].fi - 1)));
    map< int, int > h;
    for (int i = 0; i < k; i++) h[s[i]] = i;
    for (int i = 0; i < k; i++)
        if (h.find((s[i] + m) % n) != h.end()) {
            int j = h[(s[i]+m)%n];
            e[i].pb(mp(j + k, 0)), e[j+k].pb(mp(i, 0));
        }
    pq< pair< ll, int > > q;
    int v[2*k+1];
    ll d[2*k+1], now = 0;
    memset(v, 0, sizeof(v));
    memset(d, 0x3f, sizeof(d));
    q.push(mp(0, 2 * k)), d[2*k] = 0;
    while (q.size()) {
        int x = q.top().se;
        q.pop();
        if (v[x]) continue;
        v[x] = 1, now = max(now, d[x]);
        for (ui i = 0; i < e[x].size(); i++) {
            int y = e[x][i].fi;
            ll z = e[x][i].se;
            if (d[y] > d[x] + z) d[y] = d[x] + z, q.push(mp(-d[y], y));
        }
    }
    return now;
}

int main() {
    rd(n), rd(m), rd(B);
    for (int i = 1; i <= B; i++) rd(b[i]);
    rd(G);
    for (int i = 1; i <= G; i++) rd(g[i]);
    if (n < m) swap(n, m), swap(B, G), swap(b, g);
    if ((d = gcd(n, m)) > B + G) Fail;
    n /= d, m /= d;
    for (int i = 1; i <= B; i++) a[b[i]%d].pb(b[i] / d);
    for (int i = 1; i <= G; i++) f[g[i]%d].pb(g[i] / d);
    for (int i = 0; i < d; i++)
        if (!a[i].size() && !f[i].size()) Fail;
    for (int i = 0; i < d; i++) ans = max(ans, solve(a[i], f[i]) * d + i);
    print(ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注