題意

題目鏈接
給出一個(gè)頂點(diǎn)帶權(quán)無(wú)向圖。
定義訪(fǎng)問(wèn)操作：訪(fǎng)問(wèn)一個(gè)點(diǎn)，就要把與這個(gè)點(diǎn)相鄰的點(diǎn)的權(quán)值全部都加到答案里去，然后給這個(gè)頂點(diǎn)的權(quán)值/2。現(xiàn)在給出一個(gè)無(wú)窮的訪(fǎng)問(wèn)序列中的一個(gè)循環(huán)節(jié)，求最終答案的極限是多少。
注意：本題是在模意義下。

題解

數(shù)據(jù)范圍 ≤ 100000
我們定義一個(gè)sumsum數(shù)組，其中sum[v]sum[v]表示與vv頂點(diǎn)相鄰的所有頂點(diǎn)的權(quán)值和。
這樣我們掃描一個(gè)循環(huán)節(jié)，只需要把當(dāng)前頂點(diǎn)v的sum[v]sum[v]加入到答案里面去就好了，然后我們要給頂點(diǎn)vv的權(quán)值減半，并且還要更新頂點(diǎn)vv相鄰的所有點(diǎn)的sumsum。
這個(gè)思路看起來(lái)沒(méi)有問(wèn)題，但是問(wèn)題來(lái)了，更新頂點(diǎn)v相鄰的所有點(diǎn)的sumsum值的時(shí)候，如果每個(gè)點(diǎn)相鄰的點(diǎn)都有99999個(gè)這么多。而循環(huán)節(jié)長(zhǎng)度又有100000個(gè)這么長(zhǎng)，時(shí)間復(fù)雜度顯然就會(huì)爆炸了。

我們現(xiàn)在需要一個(gè)O(nn￣√)O(nn)的算法。

我們把頂點(diǎn)進(jìn)行分類(lèi)，按照這個(gè)頂點(diǎn)的度數(shù)進(jìn)行分。
當(dāng)degv>300degv>300的點(diǎn)，我們把它看作是big點(diǎn)，如果某個(gè)點(diǎn)u與big點(diǎn)點(diǎn)相臨，那么這個(gè)u點(diǎn)的sum[u]sum[u]中不應(yīng)該包含big點(diǎn)的權(quán)值，這樣的話(huà)，big點(diǎn)就不需要更新周?chē)c(diǎn)的sum值了。

當(dāng)degv≤300degv≤300的點(diǎn)，我們把它看作是small點(diǎn)，如果某個(gè)點(diǎn)u與small點(diǎn)相鄰，那么這個(gè)u點(diǎn)的sum[u]sum[u]中應(yīng)該包含small點(diǎn)的權(quán)值，并且訪(fǎng)問(wèn)small點(diǎn)時(shí)候，也應(yīng)該從small點(diǎn)出發(fā)更新相鄰點(diǎn)的sumsum值。

這樣的話(huà)，更新操作的時(shí)間復(fù)雜度就變成了O(k?300)O(k?300)
我們繼續(xù)來(lái)看詢(xún)問(wèn)操作，每次到一個(gè)點(diǎn)的時(shí)候，把這個(gè)點(diǎn)的sum[u]sum[u]加到答案里去，并且還要把這個(gè)點(diǎn)相鄰的big點(diǎn)的權(quán)值加到答案里去（因?yàn)榇藭r(shí)sum[u]sum[u]中并不包含big點(diǎn)的權(quán)值）

m是邊數(shù)，最大為100000
每個(gè)點(diǎn)最多有m300=300m300=300個(gè)big點(diǎn)。因此詢(xún)問(wèn)的時(shí)間復(fù)雜度也是O(k?300)O(k?300)
這樣總的時(shí)間復(fù)雜度就是O(k?300)O(k?300)

這道題還沒(méi)有做完

我們剛剛求的只是一輪循環(huán)節(jié)的答案，我們現(xiàn)在需要求極限值。

而第一輪的答案與第二輪的答案沒(méi)有任何比例關(guān)系。

這迫使我們?nèi)ふ医M成第一輪答案的部分與組成第二輪答案的部分之間有沒(méi)有關(guān)系。

我們?cè)O(shè)頂點(diǎn)vv，初始權(quán)值為val[v]val[v],在第一輪中的貢獻(xiàn)為x1x1,那么肯定有x1=p?val[v]x1=p?val[v]，其中p代表一個(gè)比例系數(shù)。

在第一輪以后，vv的權(quán)值變成了val[v]?12cnt[v]val[v]?12cnt[v]，其中cnt[v]cnt[v]表示的是這個(gè)vv點(diǎn)在循環(huán)節(jié)中出現(xiàn)的次數(shù)。

第二輪中vv對(duì)答案的貢獻(xiàn)是x2x2，那么x2=p?val[v]?12cnt[v]x2=p?val[v]?12cnt[v]

這樣推導(dǎo)下去，并對(duì)所有的xx求和得到

sumx=p?val[v]1?2?cnt[v]sumx=p?val[v]1?2?cnt[v]

關(guān)鍵點(diǎn)來(lái)了！！！
注意看sumxsumx與x1x1的形式關(guān)系，發(fā)現(xiàn)就相當(dāng)于用val[v]1?2?cnt[v]val[v]1?2?cnt[v]替換了val[v]val[v]
因此，我們想到了解題方案，就是一開(kāi)始就對(duì)所有點(diǎn)的權(quán)值按照這個(gè)關(guān)系進(jìn)行替換，然后跑一輪循環(huán)節(jié)，得到的答案就是要求的極限。

這道題還沒(méi)有做完
這道題不一定會(huì)有極限，如果沒(méi)有極限，要輸出-1。
怎么判定有沒(méi)有極限呢？
如果一個(gè)點(diǎn)被訪(fǎng)問(wèn)了，那么周?chē)c(diǎn)的權(quán)值都會(huì)被加到答案里面去，所以周?chē)c(diǎn)的權(quán)值必須減少，如果發(fā)現(xiàn)一個(gè)點(diǎn)被訪(fǎng)問(wèn)了，而在循環(huán)節(jié)結(jié)束后，還有一個(gè)周?chē)噜彽狞c(diǎn)的權(quán)值沒(méi)有被減少，那么意味著肯定不會(huì)收斂。

終于講完了，如果覺(jué)得好就點(diǎn)個(gè)贊吧。

代碼

#include <iostream> #include <cstdio> #include <vector> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; #define pr(x) cout<<#x<<':'<<x<<endl const int maxn = 100007; ll n,m,k,val[maxn],s[maxn]; vector<int> G[maxn],heavy[maxn]; int deg[maxn],cnt[maxn],vis[maxn],big[maxn]; ll sum[maxn],ans[maxn]; const ll mod = 1e9+7; long long powmod(long long x, long long p){long long res = 1;while(p > 0){if(p % 2 == 1) res = res * x % mod;x = x * x % mod;p >>= 1;}return res; } ll mi[maxn],inv[maxn]; int main(){inv[0] = mi[0] = 1;for(int i = 1;i < maxn;++i)mi[i] = 2ll*mi[i-1]%mod;inv[1] = powmod(2,mod-2);for(int i = 2;i < maxn;++i)inv[i] = inv[1]*inv[i-1]%mod;scanf("%lld%lld%lld",&n,&m,&k);for(int i = 1;i <= n;++i)scanf("%lld",&val[i]);for(int i = 1;i <= k;++i)scanf("%lld",&s[i]);for(int i = 0;i < m;++i){int a,b;scanf("%d%d",&a,&b);G[a].push_back(b);G[b].push_back(a);deg[a]++;deg[b]++;}for(int i = 1;i <= n;++i)for(int j = 0;j < G[i].size();++j)if(deg[i] > 300) heavy[G[i][j]].push_back(i),big[i] = 1;for(int i = 1;i <= k;++i){cnt[s[i]]++;if(cnt[s[i]] == 1)for(int j = 0;j < G[i].size();++j)vis[G[i][j]] = 1;}for(int i = 1;i <= n;++i){if(vis[i] && !cnt[i] && val[i] > 0)return 0*puts("-1");}for(int i = 1;i <= n;++i){val[i] = val[i]*powmod((1-inv[cnt[i]]+mod)%mod,mod-2)%mod;}for(int i = 1;i <= n;++i){if(big[i]) continue;for(int j = 0;j < G[i].size();++j)sum[G[i][j]] = (sum[G[i][j]] + val[i])%mod;}ll res = 0;for(int i = 1;i <= k;++i){int u = s[i];res = (res + sum[u])%mod;for(int j = 0;j < heavy[u].size();++j){int v = heavy[u][j];res = (res + val[v])%mod;}ll old = val[u];val[u] = old*inv[1]%mod;//val[u] = val[u]*inv[1]%mod;if(!big[u]){for(int j = 0;j < G[u].size();++j){int v = G[u][j];sum[v] = (sum[v] - old + val[u] + mod)%mod;}} }cout<<res<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces gym-101745 C-Infinite Graph Game 分块的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。