Znzryb's Blog

CF-1072-D. Unfair Game（记忆化搜索就是要搜索所有可能要转移到这个状态的状态）

Posted on 2026-01-13 Edited on 2026-04-06

题目大意

Bob 想了一个 1 到 n 之间的数字（n = 2^d）。Alice 初始知道这个数字是奇数还是偶数。

Alice 每回合可以选择：

将当前数字除以 2（仅当数字为偶数时）
将当前数字减 1

每次操作后，Bob 会告诉 Alice 一个非负整数 x，表示当前数字 a 能被 2^x 整除，但不能被 2^(x+1) 整除。如果数字变为 0，Alice 获胜。

游戏最多进行 k 回合。求有多少个初始数字（1 到 n）使得 Alice 在最优策略下无法在 k 回合内获胜。

ABC-387-C - Snake Numbers

HDU - 2089- 不要62

思路讲解

在题目要求下，一个数字要删多少次有规律吗？其实就是 $\text{popcount}(x)+\lfloor\log_{2}(x)\rfloor$

然后问题就来到了这个怎么样快速统计了，这个是这道题目的难点。当然，显然我们应该使用这个数位 dp。

那么我们一般数位 dp 采用的是这个记忆化搜索，我们定义搜索递归函数为 $dfs(len,limit)$ ， $dp_{len,limit,val}$ 表示在 $len $ 长度下， $limit$ 受或不受 $n$ 高位限制的情况下，数字所需消耗次数为 $val$ 的数有几个。

然后我们来想一想，就是这个普通搜索，我们要知道 $dfs(len,limit)$ 的结果，进入到 $dfs(len,limit)$ 之后，我们需要搜什么？显然，我们需要搜索 $dfs(len-1,?)\cdots dfs(l,?)\cdots dfs(0,?)$ ，因为我们要搜索所有可能会转移到这个状态的状态。

从状态 $l\to len$ ，那么会增加多少消耗次数呢？ $\Delta \gets len-l+1$ （长度增加 $len-l$ ，还增加了一个 1）。

⚠️ 注意：从 0 转移过来的特殊情况， $\Delta \gets len-l$ ，如果你像我一样认为 0 的二进制长度为 1 的话（这个是因为，我们虽然认为 0 的二进制长度为 0，但是实际上我们的 $len$ 并没有增加 $len$ 的长度，只增加了 $len-1$ 的长度）。

那么前面讲的有点抽象，举个例子就是， $(1011)_{2}$ 就是从 $(11)_{2}$ 转移过来的，因为我们的状态设计是不包含前导 0 的。当然，如果 $(1011)_{2}$ 就是题目中的 n 的话（即表示二进制长度为 4 的上限限制），除了 $(11)_{2}$ ，还可以从 $(1)_2$ ， $(0)_2$ 转移过来，但是显然不能从 $(100)_2$ 等二进制长度为 3 的状态转移过来。

最后统计答案的时候，需要将这个 $dfs(len,1),dfs(len-1,0),\cdots,dfs(0,0)$ 的状态结果累和得到答案。

AC代码

AC
https://codeforces.com/contest/2184/submission/357806886

源代码

/**
 * Problem: D. Unfair Game
 * Contest: Codeforces Round 1072 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2184/problem/D
 * Created: 2026-01-14 11:06:00
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
template <class T>
constexpr int lg_bw(T x) {
#ifdef LOCAL
    static_assert(std::is_integral_v<T>, "__lg_bw requires integral type");
#endif
    using U = std::make_unsigned_t<T>;
    U u = static_cast<U>(x);

    // 和 g++ 的 __lg 一样：对 0 没有定义。可以选择 assert 或返回 -1
#ifdef LOCAL
    assert(u != 0);
#endif
    // if (u==0) {
    //     return -1;
    // }
    return static_cast<int>(std::bit_width(u)) - 1;
}

void Solve() {
    ll N,K;
    cin >> N >> K;
    vector dp(35,vector(2,vector<ll>(75)));
    vector vis(35,vector<char>(2));
    bitset<35> bin(N);
    auto dfs=[&](auto && self,ll len,bool limit) {
        if (len==0) {
            dp[len][limit][0]=1;
            return;
        }
        if (vis[len][limit]) {
            return;
        }
        vis[len][limit]=true;
        if (limit) {
            int pos_encounter_1=-1;
            for (int l=len-1;l>=0;--l) {
                if (l==0 || bin[l-1]) {
                    pos_encounter_1=max(pos_encounter_1,l);
                }
                // 没有遇到过 1，就没有办法从这些状态转移过来
                if (pos_encounter_1==-1) {
                    continue;
                }
                ll diff=len+1-l;
                if (l==0) {
                    diff=len-l;
                }
                if (pos_encounter_1==l) {
                    // 是第一次遇到 1？那么还是受限制的
                    self(self,l,limit);
                    for (int val=diff;val<=70;++val) {
                        dp[len][limit][val]+=dp[l][limit][val-diff];
                    }
                }else {
                    // 可以从所有不是第一次遇到 1 的位置无条件转移
                    self(self,l,false);

                    for (int val=diff;val<=70;++val) {
                        dp[len][limit][val]+=dp[l][false][val-diff];
                    }
                }
            }
        }else {
            for (int l=len-1;l>=0;--l) {
                ll diff=len+1-l;
                if (l==0) {
                    diff=len-l;
                }
                self(self,l,false);
                for (int val=diff;val<=70;++val) {
                    dp[len][limit][val]+=dp[l][false][val-diff];
                }
            }
        }
    };
    dfs(dfs,lg_bw(N)+1,true);
    dfs(dfs,lg_bw(N),false);
    vector<ll> acc(75);
    for (int val=0;val<=70;++val) {
        for (int len=lg_bw(N);len>=0;--len) {
            acc[val]+=dp[len][false][val];
        }
        acc[val]+=dp[lg_bw(N)+1][true][val];
    }
    ll ans=0;
    for (int i=K+1;i<=70;++i) {
        ans+=acc[i];
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2184/submission/357806886

7
4 1
4 2
4 3
4 4
4 5
16 5
16 1

1
4 3

*/

心路历程（WA，TLE，MLE……）

向左短路 RE 了。

首先，不难发现，在题目要求下，我们只能够在二进制第一个 1 出现位置进行操作，把这个 1 后面出现的所有 0 全部消除。所以说，一个数字要删多少次有规律吗？

首先，不妨定义状态， $dp_i$ 指的是

当然，虽然知道了要使用数位 dp，如何实现也至少是需要想一想的。虽然说数位 dp 一般采用这个自顶向下的记忆化搜索设计方法，但是这道题目没什么限制条件，以计数为主，直接采用这个递推法即可。

$dp_{len,i}$ 表示在该（二进制）长度下， $val=i$ 的这个数字的数量。

dp_{len,i}\gets \sum_{l=0}^{len-1}dp_{l,i+1+len-l}

那么我们一般数位 dp 采用的是这个记忆化搜索，我们就先想搜索吧，搜索 $[0,n]$ 有几个数字的 $val>k$ 。当然这个有点奇怪，我们不妨假设我们是求的这个 $[0,n]$ 下， $val=i$ 的这个数字的数量，即 $dp_i$ 。

那我们要搜索这个东西，需要什么呢？ $dfs(len,ismax)$ 可以吗？我们先试试，我们首先发现，只有 $dp_{i}$ 无法满足这个我们的要求，设置为 $dp_{len,i}$ 更为合适。

CF-1072-C. Huge Pile

Posted on 2026-01-13 Edited on 2026-04-06

这道题目没开出来，这把实在打的太唐了。

总结而言，有三点问题：

第一是这个没看榜，还是要经常看榜，观察这个题目的出题速度，人数变化情况，一旦这个人数超过 5000 以上，或者在比赛未过半的时候达到 3000，那么就说明这道题目就是非常简单，还是能比较简单的可以看出来/猜出来的（就比如说这道题目，这个神秘小性质还是很简单的）。

其实也没有其他问题，div3 的经验我确实比较少，最近打的比较少。

题目大意

给定一个包含 N 个苹果的堆，每次可以将一个堆分成两个堆，如果原堆有 x 个苹果，则分成 ⌊x/2⌋ 和 ⌈x/2⌉ 两个堆，每次分堆需要 1 分钟。

问能否通过若干次分堆操作得到一个恰好包含 K 个苹果的堆？如果可以，求最少需要多少分钟。

输入：

第一行一个整数 t (1 ≤ t ≤ 10⁴)，表示测试用例数量
每个测试用例一行两个整数 n 和 k (1 ≤ n, k ≤ 10⁹)，分别表示初始苹果数和目标苹果数

输出：

对于每个测试用例，如果无法得到恰好 K 个苹果的堆，输出 -1；否则输出最少需要的分钟数。

思路讲解

其实这道题目只需要一个关键结论，就是第 $k$ 步只可能产生 $\lfloor\frac{N}{2^k}\rfloor$ 或者 $\lceil\frac{N}{2^k}\rceil$ （当然这两个可能相等）。因此就猜一下就可以了。

当然，利用这个结论，也可以写一个记忆化 bfs，详细地来说，用一个 set 存一下，搜过的数字就不继续搜了。

while (!q.empty()) {
    auto [x,step]=q.front();
    q.pop();
    if (x==K) {
        cout<<step<<"\n";
        return;
    }
    if (x<K) {
        continue;
    }
    auto res=st.emplace(x/2,step+1);
    bool con=!res.second;
    if (!con) {
        q.emplace(x/2,step+1);
    }
    res=st.emplace((x+1)/2,step+1);
    con=!res.second;
    if (!con){
        q.emplace((x+1)/2,step+1);
    }
}
cout<<-1<<"\n";

AC代码

AC
https://codeforces.com/contest/2184/submission/357642090

源代码

/**
 * Problem: C. Huge Pile
 * Contest: Codeforces Round 1072 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2184/problem/C
 * Created: 2026-01-13 00:11:50
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
struct x_step {
    ll x,step;
    bool operator<(const x_step & o) const {
        if (x!=o.x) return x<o.x;
        return step<o.step;
    }
    x_step(ll x,ll step):x(x),step(step) {

    }
};
void Solve() {
    ll N,K;
    cin >> N >> K;
    queue<x_step> q;
    q.push({N,0});
    set<x_step> st;
    while (!q.empty()) {
        auto [x,step]=q.front();
        q.pop();
        if (x==K) {
            cout<<step<<"\n";
            return;
        }
        if (x<K) {
            continue;
        }
        auto res=st.emplace(x/2,step+1);
        bool con=!res.second;
        if (!con) {
            q.emplace(x/2,step+1);
        }
        res=st.emplace((x+1)/2,step+1);
        con=!res.second;
        if (!con){
            q.emplace((x+1)/2,step+1);
        }
    }
    cout<<-1<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2184/submission/357642090

*/

心路历程（WA，TLE，MLE……）

Starters 212-Beautiful Sum

Posted on 2026-01-09 Edited on 2026-04-06

思路讲解

AC代码

https://www.codechef.com/viewsolution/1209777968

源代码

// by Gospel_rock
// title: Beautiful Sum
// url: https://www.codechef.com/problems/XPS

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;
using ll = long long;

static constexpr int LOG = 21;

// --- 核心数据结构 ---

struct Tag {
    ll xor_val[2]; // [0]:偶深, [1]:奇深
    explicit Tag(ll e=0, ll o=0) { xor_val[0] = e; xor_val[1] = o; }
    void apply(const Tag &t) { xor_val[0] ^= t.xor_val[0]; xor_val[1] ^= t.xor_val[1]; }
    bool empty() const { return xor_val[0] == 0 && xor_val[1] == 0; }
};

struct Info {
    int cnt[2];         // cnt[0]:偶深节点数, cnt[1]:奇深
    int bit_num[2][LOG]; // bit_num[0][i]: 偶深节点第i位为1的个数

    Info() { memset(cnt, 0, sizeof(cnt)); memset(bit_num, 0, sizeof(bit_num)); }

    // 初始化结构（奇偶性）
    static Info make_structure(int depth) {
        Info res;
        res.cnt[depth & 1] = 1;
        return res;
    }

    static Info merge(const Info &l, const Info &r) {
        Info res;
        FOR(p, 0, 1) {
            res.cnt[p] = l.cnt[p] + r.cnt[p];
            FOR(i, 0, LOG-1) res.bit_num[p][i] = l.bit_num[p][i] + r.bit_num[p][i];
        }
        return res;
    }

    void apply(const Tag &t) {
        FOR(p, 0, 1) {
            if (t.xor_val[p] == 0) continue;
            FOR(i, 0, LOG-1) {
                if ((t.xor_val[p] >> i) & 1) bit_num[p][i] = cnt[p] - bit_num[p][i];
            }
        }
    }
    static Info zero() { return Info(); }
};

// --- ZKW 线段树 ---
struct SEG {
    int n, sz, dep;
    vector<Info> info;
    vector<Tag> tag;

    SEG(int n_) {
        n = n_ + 2;
        dep = __lg(n) + 1;
        sz = 1 << dep;
        info.assign(sz * 2 + 5, Info());
        tag.assign(sz * 2 + 5, Tag());
    }

    static void pull(Info &fa, const Info &lc, const Info &rc) {
        fa = Info::merge(lc, rc);
    }
    void apply_one(int o, const Tag &t) {
        info[o].apply(t);
        tag[o].apply(t);
    }
    void pushdown(int o) {
        if (tag[o].empty()) return;
        int l = o << 1, r = l | 1;
        apply_one(l, tag[o]);
        apply_one(r, tag[o]);
        tag[o] = Tag();
    }
    void assign_raw(int i, const Info &v) { info[i + sz] = v; }
    void build() {
        for (int o = sz - 1; o >= 1; --o)
            pull(info[o], info[o << 1], info[o << 1 | 1]);
    }
    void push_path(int l, int r) {
        l = l - 1 + sz; r = r + 1 + sz;
        int i = dep, j = __lg(l ^ r);
        while (i > j) pushdown(l >> i--);
        while (i) { pushdown(l >> i); pushdown(r >> i); --i; }
    }
    Info query(int L, int R) {
        if (L > R) return Info::zero();
        push_path(L, R);
        int l = L - 1 + sz, r = R + 1 + sz;
        Info left = Info::zero(), right = Info::zero();
        for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) left = Info::merge(left, info[l ^ 1]);
            if (r & 1)  right = Info::merge(info[r ^ 1], right);
        }
        return Info::merge(left, right);
    }
    void range_apply(int L, int R, const Tag &t) {
        if (L > R) return;
        push_path(L, R);
        int l = L - 1 + sz, r = R + 1 + sz;
        int L0 = l, R0 = r; 
        for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) apply_one(l ^ 1, t);
            if (r & 1)  apply_one(r ^ 1, t);
        }
        for (L0 >>= 1; L0; L0 >>= 1) pull(info[L0], info[L0 << 1], info[L0 << 1 | 1]);
        for (R0 >>= 1; R0; R0 >>= 1) pull(info[R0], info[R0 << 1], info[R0 << 1 | 1]);
    }
};

// --- HLD ---
struct HLD {
    int n, cur;
    vector<vector<int>> g;
    vector<int> fa, dep, heavy, head, dfn, siz;

    HLD(int n_) : n(n_), cur(0), g(n_ + 1), fa(n_ + 1), dep(n_ + 1), heavy(n_ + 1), head(n_ + 1), dfn(n_ + 1), siz(n_ + 1) {}

    void addEdge(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
    int dfs1(int u, int f) {
        fa[u] = f; dep[u] = dep[f] + 1; siz[u] = 1;
        int maxsz = 0;
        for (int v : g[u]) if (v != f) {
            int sub = dfs1(v, u);
            siz[u] += sub;
            if (sub > maxsz) { maxsz = sub; heavy[u] = v; }
        }
        return siz[u];
    }
    void dfs2(int u, int h) {
        head[u] = h; dfn[u] = ++cur;
        if (heavy[u]) dfs2(heavy[u], h);
        for (int v : g[u]) if (v != fa[u] && v != heavy[u]) dfs2(v, v);
    }
    void build(int root = 1) { cur = 0; dfs1(root, 0); dfs2(root, root); }
    
    int lca(int u, int v) {
        while (head[u] != head[v]) {
            if (dep[head[u]] > dep[head[v]]) u = fa[head[u]];
            else v = fa[head[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    template<class F> void for_subtree(int u, F &&op) { op(dfn[u], dfn[u] + siz[u] - 1); }
    template<class F> void for_path(int u, int v, F &&op) {
        while (head[u] != head[v]) {
            if (dep[head[u]] < dep[head[v]]) swap(u, v);
            op(dfn[head[u]], dfn[u]);
            u = fa[head[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        op(dfn[u], dfn[v]);
    }
};

struct HLDZKW {
    HLD hld;
    SEG seg;

    HLDZKW(int n) : hld(n), seg(n) {}
    void addEdge(int u, int v) { hld.addEdge(u, v); }

    void build() {
        hld.build(1);
        FOR(i, 1, hld.n) seg.assign_raw(hld.dfn[i], Info::make_structure(hld.dep[i]));
        seg.build();
    }

    void applySubtreeNode(int u, const Tag &t) {
        hld.for_subtree(u, [&](int L, int R) { seg.range_apply(L, R, t); });
    }
    void applyPathNode(int u, int v, const Tag &t) {
        hld.for_path(u, v, [&](int L, int R) { seg.range_apply(L, R, t); });
    }
    Info querySubtreeNode(int u) {
        Info res = Info::zero();
        hld.for_subtree(u, [&](int L, int R) { res = Info::merge(res, seg.query(L, R)); });
        return res;
    }
    Info queryPathNode(int u, int v) {
        Info res = Info::zero();
        hld.for_path(u, v, [&](int L, int R) { res = Info::merge(res, seg.query(L, R)); });
        return res;
    }

    // Top-Down Edge 接口
    void applySubtreeEdge(int u, const Tag &t) {
        applySubtreeNode(u, t); 
        int pos = hld.dfn[u];
        seg.range_apply(pos, pos, t); // 撤销 u (u代表u上方的边，不在子树边集中)
    }
};

void Solve(){
    ll N;
    cin >> N;
    vector<array<ll, 3>> edges;
    HLDZKW hld(N);
    
    FOR(i, 1, N - 1) {
        ll u, v, w;
        cin >> u >> v >> w;
        hld.addEdge(u, v);
        edges.push_back({u, v, w});
    }

    hld.build();

    // 初始化
    for (auto [u, v, w] : edges) {
        // 边 (u, v) 挂在儿子上。Node 操作代表子树下所有点路径 +w
        // 这里用 applySubtreeNode 是最自然的
        ll child = (hld.hld.dep[u] < hld.hld.dep[v]) ? v : u;
        hld.applySubtreeNode(child, Tag(w, w));
    }

    ll Q;
    cin >> Q;
    FOR(_, 1, Q) {
        ll opt;
        cin >> opt;
        if (opt == 1) {
            ll u, x;
            cin >> u >> x;
            Tag t;
            if (hld.hld.dep[u] % 2 == 0) t = Tag(0, x);
            else t = Tag(x, 0);
            
            // Q1: 修改子树内的边 -> 使用 Edge 接口 (排除 u)
            hld.applySubtreeEdge(u, t);
        } else {
            ll u;
            cin >> u;
            
            // --- 你的逻辑 ---
            // 1. 查 u 到根的路径异或和 D(u)
            Info u_to_root = hld.queryPathNode(u, u);
            
            ll current_val_u = 0;
            int p = hld.hld.dep[u] & 1;
            FOR(i, 0, LOG-1) if(u_to_root.bit_num[p][i]) current_val_u |= (1LL << i);

            // 2. 构造修正 Tag
            Tag need_apply(current_val_u, current_val_u);
            
            // 3. 查子树信息
            // 【关键修正】：这里必须查 SubtreeNode (包含 u)，因为题目求的是子树内"节点对"的美观度
            // 如果查 SubtreeEdge (排除 u)，就会漏掉所有涉及 u 的点对，导致答案变小。
            Info res = hld.querySubtreeNode(u);
            
            // 4. 应用修正
            res.apply(need_apply);
            
            ll ans = 0;
            ll total = res.cnt[0] + res.cnt[1];
            FOR(i, 0, LOG-1) {
                ll ones = res.bit_num[0][i] + res.bit_num[1][i];
                ans += (ones * (total - ones)) * (1ll << i);
            }
            cout << ans << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll lT; cin >> lT;
    while(lT--) Solve();
    return 0;
}

心路历程（WA，TLE，MLE……）

Good Travels｜缩点模版

Posted on 2026-01-09 Edited on 2026-04-06

思路讲解

AC代码

AC
https://www.spoj.com/status/ns=35103793

源代码

// by Gospel_rock
// title: Good Travels scc
// timeLimit: 1000
// url: https://vjudge.net/problem/SPOJ-GOODA#author=GPT_zh
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT, S, E;

void Solve() {
    cin >> N >> M >> S >> E;
    vector<ll> A(N + 4);
    FOR(i, 1, N) { cin >> A[i]; }
    vector<vector<ll>> g(N + 5);
    FOR(i, 1, M) {
        ll u, v;
        cin >> u >> v;
        g[u].PB(v);
    }
    vector<ll> tin(N + 5), low(N + 5);
    vector<ll> stk;
    vector<char> instk(N + 5);
    vector<ll> scc(N + 5);
    vector<ll> scca(N+5);
    ll idx = 0, sccidx = 0;
    auto dfs1 = [&](auto self, ll u) -> void {
        tin[u] = low[u] = ++idx;
        stk.PB(u);
        instk[u] = 1;
        for (auto v : g[u]) {
            if (!tin[v]) {
                self(self, v);
                low[u] = min(low[u], low[v]);
            } else if (instk[v]) {
                low[u] = min(low[u], low[v]);
            }
        }
        if (tin[u] == low[u]) { // u是 scc 的根
            ++sccidx;
            ll y=0;
            do {
                y = stk.back();
                stk.pop_back();
                instk[y] = 0;
                scc[y] = sccidx;
                scca[sccidx]+=A[y];
            } while (y != u);
        }
    };
    FOR(i,1,N){
        if(!tin[i]){
            dfs1(dfs1,i);
        }
    }
    vector<vector<ll> > scg(sccidx+5);
    vector<ll> dp(sccidx+5,-INF);
    vector<ll> in(sccidx+5);
    FOR(u,1,N){
        for(auto v:g[u]){
            if(scc[u]==scc[v]) continue;
            scg[scc[u]].PB(scc[v]);
            in[scc[v]]++;
        }
    }
    // exit(0);
    queue<ll> q;
    FOR(i,1,sccidx){
        if(in[i]==0){
            q.push(i);
        }
    }
    dp[scc[S]]=scca[scc[S]];
    while(!q.empty()){
        auto u=q.front();q.pop();
        for(auto v:scg[u]){
            dp[v]=max(dp[v],dp[u]+scca[v]);
            in[v]--;
            if(in[v]==0){
                q.push(v);
            }
        }
    }
    ll ans=0;
    // FOR(i,1,sccidx){
    //     ans=max(dp[i],ans);
    // }
    cout<<(ll)dp[scc[E]]<<"\n";


// #ifdef LOCAL
//     debug(sccidx);
//     cerr<<"scc:";
//     FOR(i,1,N){
//         cerr<<scc[i]<<" ";
//     }
//     cerr<<"\n";
//     cerr<<"scca:";
//     FOR(i,1,sccidx){
//         cerr<<scca[i]<<" ";
//     }
//     cerr<<"\n";
//     FOR(i,1,sccidx){
//         cerr<<i<<":";
//         FOR(j,0,SZ(scg[i])-1){
//             cerr<<scg[i][j]<<" ";
//         }
//         cerr<<"\n";
//     }
//     cerr<<"dp:";
//     FOR(i,1,sccidx){
//         cerr<<dp[i]<<" ";
//     }
//     cerr<<"\n";
// #endif
   
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // cin >> lT;
    // while (lT--)
        Solve();
    return 0;
}
/*
AC
https://www.spoj.com/status/ns=35103793

*/

心路历程（WA，TLE，MLE……）

Starters 213-Mean Difference (easy)

Posted on 2026-01-09 Edited on 2026-04-06

思路讲解

AC代码

https://www.codechef.com/viewsolution/1210385010

源代码

// by Gospel_rock
// title: Mean Difference (Easy)
// GROUP_NAME: START213B
// ONLINE_JUDGE_NAME: CodeChef

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);

ll lT;

void Solve(){
	ll N;
	cin>>N;
	vector<ll> A(N+5);
    FOR(i,1,N) {
        cin>>A[i];
    }
    if (N==1) {
        cout<<0<<"\n";
        return;
    }
    sort(A.begin()+1,A.begin()+N+1,greater<>());
    function f=[&](ll need_big) {
        if (need_big>=N) return 0ll;
        ll acc=0;
        FOR(i,1,need_big) {
            acc+=A[i];
        }
        acc+=A[N];
        acc/=(need_big+1);
        return abs(acc-A[N]);
    };
    ll l=0,r=N-1;
    while (r-l>2) {
        ll mid1=l+(r-l)/3;
        ll mid2=r-(r-l)/3;
        if (f(mid1)<=f(mid2)) {
            l=mid1;
        }else {
            r=mid2;
        }
    }
    ll ans=0;
    FOR(i,l,r) ans=max(ans,f(i));
    sort(A.begin()+1,A.begin()+N+1);
    l=0,r=N-1;
    while (r-l>2) {
        ll mid1=l+(r-l)/3;
        ll mid2=r-(r-l)/3;
        if (f(mid1)<=f(mid2)) {
            l=mid1;
        }else {
            r=mid2;
        }
    }
    FOR(i,l,r) ans=max(ans,f(i));
    cout<<ans<<"\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin>>lT;
    while(lT--)
        Solve();
    return 0;
}
/*
AC

*/