题解：P11393 [JOI Open 2019] 汇款 / Remittance

jycjycjyc · 2026-07-23 13:17:39 · 题解

对于这个题，一个比较关键的观察是：从任意一点流出的流量都只会流 \log V 次．

然后我们考虑一下其他的东西：

若对于 i，有 (a_i-b_i) \bmod 2 = 0，则我们可以无脑将 (a_i-b_i) 的流量流出去．这个是显然正确的．

若 (a_i-b_i) \bmod 2 \neq 0，则有两种情况：将 a_i 流成 (b_i-1) 或流成 (b_i+1)．无论是哪种情况，我们所希望的都是前面的某个数再流一点给到 a_i．故我们希望选择将 a_i 流成 (b_i-1)，这样后面留的更多，而又是环，所以后面就是前面，所以前面流回来的可能性更大．

不过若 b_i=0 那只能流成 (b_i+1)．你不可能流成负的．

然后直接硬模拟就行了，最多会流 n+ \log V 次．

:::success[AC code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 1e6+1;
int n,a[N],b[N];
inline int calc(int x){
    int cnt = 0;
    while(x){
        ++cnt;
        x>>=1;
    }
    return cnt;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    int maxn = 0;
    for(int i = 1;i<=n;++i){
        cin >> a[i] >> b[i];
        maxn = max(maxn,a[i]);
    }
    int tot = calc(maxn);
    tot+=n;
    int flow = 0;
    for(int cnt = 1,i = 1;cnt<=tot;++cnt){
        flow>>=1;
        a[i]+=flow;
        flow = 0;
        if(a[i]>b[i]){
            if((a[i]-b[i])&1){
                if(b[i]){
                    flow+=a[i]-(b[i]-1);
                    a[i] = b[i]-1;
                }else{
                    flow+=a[i]-(b[i]+1);
                    a[i] = b[i]+1;
                }
            }else{
                flow+=a[i]-b[i];
                a[i] = b[i];
            }
        }
        ++i;
        if(i == n+1){
            i = 1;
        }
    }
    for(int i = 1;i<=n;++i){
        if(a[i]!=b[i]){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

:::