CF516E Drazil and His Happy Friends 题解

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$ 。

我们要连三类边：

$S \stackrel{i}{\longrightarrow} A_i$
$B_i \stackrel{m}{\longrightarrow} A_i$
$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;
}

题意

题解

代码

评论