problem

洛谷鏈接

solution

記 $\gcd (n,m)=d$，則快樂只會在同余 $d$ 的關系中傳遞。

$i+xn\equiv i+xs?d\equiv i(\mathrm{m}\mathrm{o}\mathrm{d}d),i+ym\equiv i+yt?d\equiv i(\mathrm{m}\mathrm{o}\mathrm{d}d)$。

所以我們將所有男生 $0～n?1$ 和女生 $0～m?1$ 按編號取模 $d$ 的結果分組 $[0,d)$。

因為每一類的快樂只能在組內傳遞，所以無解的情況就是某個組內沒有一個人初始是快樂的。

答案顯然是取所有人獲得快樂的最早時間的最大值。

我們分組計算答案，考慮任意一組內的答案如何計算？

假設這里面有個男生 $i$ 一開始就是快樂的，那么他會在第 $i$ 天將快樂傳遞給 $i\mathrm{m}\mathrm{o}\mathrm{d}m$ 女生。

再過 $n$ 天，這個男生又把自己的快樂傳遞給了 $(i+n)\mathrm{m}\mathrm{o}\mathrm{d}m$ 女生。

那我們能否看成是 $i\mathrm{m}\mathrm{o}\mathrm{d}m$ 女生經過 $n$ 天將快樂傳遞給 $(i+n)\mathrm{m}\mathrm{o}\mathrm{d}m$ 女生的呢？——答案是肯定的。

于是我們就又有了將同組的男女生分開計算的想法。

不妨以女孩子為例。（女孩紙就是香香的），將初始快樂的男生 $i$ 信息附屬在女生 $i\mathrm{m}\mathrm{o}\mathrm{d}m$ 身上，即把她當成初始就快樂的人。

考慮如何組內每個女孩紙最早獲得快樂的時間？

我們將這個快樂傳遞當成邊，時間就是邊權。你會發現每條邊的邊權都是 $n$ 。

跑個最短路就行了？——太遺憾了，點可能會很多。

我們關注到初始快樂的女生總數不會超過 $1e5$，很容易想到能否通過這些關鍵女生計算出每個女生獲得快樂的時間？

在這里還獲得了一個粗略判無解的條件，那就是分的組數 $d>2e5$，每組只放個男生或女生都不能讓每組里有初始即快樂的人。

將本組所有女生編號處理出來，并將邊連出來，肯定能剛好連出一個環來。

讓所有女生都多加一個屬性——環的重編號。

則任意兩個女生快樂傳遞時間就是環上編號差 $\times n$（注意環頭和環尾的特殊計算方式）。

現在將組內所有女生按環的重編號遞增排列，則相鄰兩個女生間快樂傳遞時間均為 $n$。

繼續考慮重新排列后，連續兩個關鍵女生中夾著的一些普通女生。

設 $di{s}_i:i$ 最早獲得快樂的時間，且對于所有關鍵女生 $k$ 初始化 $di{s}_k=k$。

我們沒有必要去算這中間每個女生的時間，因為最后答案只取最大值。

所有這段女生中時間最大值肯定是編號最大的，即重編號的連續兩個關鍵女生 $x,y$，$y?1$ 女生時間一定最大。

那我們只用算這一段的這一個特殊的普通女生時間即可。

然后將每一段的答案取較大值。

線性掃一遍關鍵女生即可求解。

需要注意的是，初始就快樂的女生真正獲得快樂的時間是 $0$ 而不是 $di{s}_i$。（所以不能選這些女生的時間比最大值）

還有我們把某些男生快樂的信息放在了某些女生身上，讓她們成為關鍵女生，但這是虛假的關鍵女生，所以這些女生的 $di{s}_i$ 又是需要計算的。

男生同理，交換一下 $n,m$ 等信息即可。

最后在每組的女生/男生最大值中再取最大值。

code

#include <bits/stdc++.h> using namespace std; #define inf 1e18 #define int long long #define maxn 200005 vector < int > b[maxn], g[maxn]; int n, m, B, G; int d[maxn], id[maxn], s[maxn];int exgcd( int a, int b, int &x, int &y ) {if( ! b ) { x = 1, y = 0; return a; }else { int d = exgcd( b, a % b, y, x ); y -= a / b * x; return d; } }int solve( int gcd, int n, int m, vector < int > g, vector < int > b ) {//每組的男女生個數就是 n/gcd,m/gcdif( m == g.size() ) return -1; //要是return 0外層還要+i有可能還是被誤判成最大值int cnt = 0, ans = 0, dis = inf;/*對于每一組，我們怎么將男生 $i\mod n$ 的快樂移加到女生 $i\mod m$ 的快樂上呢？我們按 $i\mod d$ 分組的時候，扔的關鍵男女生編號就直接是 $\lfloor\frac id\rfloor$。那么將所有組內編號再都 $\times d\pmod m$ 取出來。相當于是把模 $d$ 相同的數移到 $d$ 的整數倍，$r+id\rightarrow id$。然后再一一對應到模 $m$ 的位置上。離散化的趕腳 因為編號太大不可能直接以編號為下標做*/for( int i : g ) s[++ cnt] = i * gcd % m, d[cnt] = i, id[cnt] = cnt;//真的關鍵女生點for( int i : b ) s[++ cnt] = i * gcd % m, d[cnt] = i, id[cnt] = cnt;//假的關鍵女生點sort( id + 1, id + cnt + 1, []( int x, int y ) { return s[x] < s[y]; } );s[id[0] = 0] = s[id[cnt]] - m, s[id[cnt + 1] = cnt + 1] = s[id[1]] + m;//把環拆成鏈for( int i = 1;i <= cnt;i ++ )dis = min( d[id[i]], dis + ( s[id[i]] - s[id[i - 1]] ) * n );for( int i = 1;i <= cnt;i ++ ) {dis = min( d[id[i]], dis + ( s[id[i]] - s[id[i - 1]] ) * n );if( s[id[i]] == s[id[i + 1]] ) continue;if( s[id[i]] + 1 == s[id[i + 1]] and id[i] <= g.size() ) continue;//不是虛假特殊女生才能跳過ans = max( ans, dis + ( s[id[i + 1]] - s[id[i]] - 1 ) * n );}return ans; }signed main() {scanf( "%lld %lld", &n, &m );int x, y, w, gcd = exgcd( n, m, x, y );if( gcd > 2e5 ) return ! puts("-1");scanf( "%lld", &B );for( int i = 1;i <= B;i ++ ) scanf( "%lld", &w ), b[w % gcd].push_back( w / gcd );scanf( "%lld", &G );for( int i = 1;i <= G;i ++ ) scanf( "%lld", &w ), g[w % gcd].push_back( w / gcd );int ans = 0;( x += m ) %= m, ( y += n ) %= n;for( int i = 0;i < gcd;i ++ ) {//第i天才會開始第i組信息的傳遞if( g[i].empty() and b[i].empty() ) { puts("-1"); return 0; }ans = max( ans, solve( x, n / gcd, m / gcd, g[i], b[i] ) * gcd + i );ans = max( ans, solve( y, m / gcd, n / gcd, b[i], g[i] ) * gcd + i );}printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的CodeForces 516E Drazil and His Happy Friends（数学+最短路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。