Znzryb's Blog

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——M. Web Delivery（采用 naive if else方法，应用不同状态压缩方法，解决该问题）（枚举一个 S 的子集的子集方法）（利用乘积约束）

Posted on 2026-03-05 Edited on 2026-03-07

题目大意

题目描述
Gagamboy 需要购买 $r$ 种不同的化学物质，每种需要 1kg。电商平台上共有 $c$ 个卖家。
给定一个 $r \times c$ 的价格矩阵 $A$ ，其中 $a_{i,j}$ 表示从卖家 $j$ 处购买 1kg 化学物质 $i$ 的价格。
此外，对于每个卖家 $j$ ，只要从该卖家处购买了任何数量的化学物质（哪怕只有一种），都需要额外支付一笔固定的配送费 $d_j$ 。
请计算购买到所有 $r$ 种化学物质（每种至少 1kg）所需的最小总花费。本题包含多组独立测试数据。

输入格式
第一行包含一个整数 $T$ （ $1 \le T \le 10$ ），表示测试数据的组数。
对于每组测试数据：
第一行包含两个由空格分隔的整数 $r$ 和 $c$ （ $1 \le r, c$ ，且 $r \times c \le 250$ ）。
接下来 $r$ 行，每行包含 $c$ 个由空格分隔的整数，第 $i$ 行的第 $j$ 个数为 $a_{i,j}$ （ $1 \le a_{i,j} \le 10^{15}$ ）。
最后一行包含 $c$ 个由空格分隔的整数 $d_1, d_2, \dots, d_c$ （ $1 \le d_j \le 10^{15}$ ），表示每个卖家的配送费。

输出格式
对于每组测试数据，输出一行一个整数，表示完成购买所需的最小总花费。

样例输入

样例输出

1
2

11
11

样例解释
对于第一组样例：
一种最优的购买方案如下：

向卖家 2 购买化学物质 1 和 3。它们的价格分别为 $a_{1,2} = 3$ 和 $a_{3,2} = 1$ 。支付这笔订单所需的配送费为 $d_2 = 3$ 。
向卖家 4 购买化学物质 2。它的价格为 $a_{2,4} = 1$ 。支付这笔订单所需的配送费为 $d_4 = 3$ 。
总花费为： $((3 + 1) + 3) + (1 + 3) = 11$ 。

对于第二组样例：
最优方案能达到的最小花费同样为 11。

思路讲解

这道题目的做法，首先，需要想到：绷不住了，这道题目，观察到 chem * sell <= 250，那么，chem，sell 理论上来说，应该不会同时超过 16，因为 16*16=256，这样子，chem 小，就对 chem 进行状态压缩，sell 小，就对 sell 进行状态压缩。

确实是感觉到，如果不进行状态压缩，那么这道题目非常难做。

如果进行状态压缩的话，状态压缩 seller 非常好做。枚举的是给哪些 seller 付了这个运费。

给哪些 seller 付了这个运费，就只能从这些 seller 这里购买化学品。

ll ans=INF;
// 枚举的是给哪些 seller 付了这个运费
for (int s=1;s<(1<<M_j_sell);++s) {
    vector<ll> mn_price(N_i_chem+2,INF);
    ll offset_j=1;
    ll price=0;
    // 给哪些 seller 付了这个运费，就只能从这些 seller 这里购买化学品
    for (int j=0;j<M_j_sell;++j) {
        if (s>>j&1) {
            price+=D_j_sell[j+offset_j];
            for (int i=1;i<=N_i_chem;++i) {
                mn_price[i]=min(mn_price[i],A[i][offset_j+j]);
            }
        }
    }
    for (int i=1;i<=N_i_chem;++i) {
        price+=mn_price[i];
    }
    ans=min(ans,price);
    // dp[s]=price;
}
cout<<ans<<"\n";

我们来看，状态压缩 chem，我们怎么做？这个会难一点。

我们不难观察到，一个子集 S 的最优解，一定是这样的：把一部分子集交给一个买家，把另一部分子集交给一个买家，把又一部分子集交给又一买家……。

在状态压缩化学品的时候，我们需要学习一种写法，即枚举 mask 的子集。

for (int S = 0; S < (1 << r); S++) {
    for (int T = S; T > 0; T = (T - 1) & S) {
        // T 是 S 的非空子集
        dp[S] = min(dp[S], dp[S ^ T] + best[T]);
    }
}

枚举 mask 的所有子集，是 $O(3^n)$ 。

如果说枚举 seller，允许你去这个枚举子集，是不是会简单一点？

预处理：对每个非空子集 $T$ ，预先算好从所有卖家中买 $T$ 的最小花费：best（T）的意思就是在包括这个运费的情况下，该 chem 子集 T，从哪一个买家那里采购，所需花费最低？

\text{best}(T) = \min_{j=1}^{c} \left(d_j + \sum_{i \in T} a_{i,j}\right)

具体而言就是：

ll offset_i=1;
vector<ll> best((1<<N_i_chem)+2);
for (int s=1;s<(1<<N_i_chem);++s) {
    ll lans=INF;
    for (int j=1;j<=M_j_sell;++j) {
        ll price=D_j_sell[j];
        for (int i=0;i<N_i_chem;++i) {
            if (s>>i&1) {
                price+=A[offset_i+i][j];
            }
        }
        lans=min(lans,price);
    }
    best[s]=lans;
}

转移方程如下，容易写出：

dp[S] = \min_{\emptyset \neq T \subseteq S} \left(dp[S \setminus T] + \text{best}(T)\right)

你可能会有疑问，这个运费会不会重复算？答案是是的，但是我们肯定不会采用运费重复算的组合。

vector<ll> dp((1<<N_i_chem)+2);
// for (int j=1;j<=M_j_sell;++j) {
//     dp[0][j]=0;
// }
// for (int s=1;s<(1<<N_i_chem);++s) {}
ll offset_i=1;
vector<ll> best((1<<N_i_chem)+2);
for (int s=1;s<(1<<N_i_chem);++s) {
    ll lans=INF;
    for (int j=1;j<=M_j_sell;++j) {
        ll price=D_j_sell[j];
        for (int i=0;i<N_i_chem;++i) {
            if (s>>i&1) {
                price+=A[offset_i+i][j];
            }
        }
        lans=min(lans,price);
    }
    best[s]=lans;
}
for (int s=1;s<(1<<N_i_chem);++s) {
    ll lans=INF;
    for (int t=s;t>0;t=(t-1)&s) {
        lans=min(lans,dp[s^t]+best[t]);
    }
    dp[s]=lans;
}
cout<<dp[(1<<N_i_chem)-1]<<"\n";

AC代码

AC
https://codeforces.com/gym/106262/submission/365538444

源代码

/**
 * Problem: M. Web Delivery
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/M
 * Created: 2026-03-05 14:02:59
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */

void Solve() {
    ll N_i_chem,M_j_sell;
    cin >> N_i_chem >> M_j_sell;
    vector<vector<ll>> A(N_i_chem+2,vector<ll>(M_j_sell+2));
    for (int i=1;i<=N_i_chem;++i) {
        for (int j=1;j<=M_j_sell;++j) {
            cin>>A[i][j];
        }
    }
    vector<ll> D_j_sell(M_j_sell+2);
    for (int j=1;j<=M_j_sell;++j) {
        cin>>D_j_sell[j];
    }
    // 绷不住了，这道题目，观察到 chem * sell <= 250
    // 那么，chem，sell 理论上来说，应该不会同时超过 16，因为 16*16=256
    // 这样子，chem 小，就对 chem 进行状态压缩
    // sell 小，就对 sell 进行状态压缩

    if (N_i_chem<=M_j_sell) {
        vector<ll> dp((1<<N_i_chem)+2);
        // for (int j=1;j<=M_j_sell;++j) {
        //     dp[0][j]=0;
        // }
        // for (int s=1;s<(1<<N_i_chem);++s) {}
        ll offset_i=1;
        vector<ll> best((1<<N_i_chem)+2);
        for (int s=1;s<(1<<N_i_chem);++s) {
            ll lans=INF;
            for (int j=1;j<=M_j_sell;++j) {
                ll price=D_j_sell[j];
                for (int i=0;i<N_i_chem;++i) {
                    if (s>>i&1) {
                        price+=A[offset_i+i][j];
                    }
                }
                lans=min(lans,price);
            }
            best[s]=lans;
        }
        for (int s=1;s<(1<<N_i_chem);++s) {
            ll lans=INF;
            for (int t=s;t>0;t=(t-1)&s) {
                lans=min(lans,dp[s^t]+best[t]);
            }
            dp[s]=lans;
        }
        cout<<dp[(1<<N_i_chem)-1]<<"\n";
    }else {
        // vector<ll> dp((1<<M_j_sell)+2);
        ll ans=INF;
        for (int s=1;s<(1<<M_j_sell);++s) {
            vector<ll> mn_price(N_i_chem+2,INF);
            ll offset_j=1;
            ll price=0;
            for (int j=0;j<M_j_sell;++j) {
                if (s>>j&1) {
                    price+=D_j_sell[j+offset_j];
                    for (int i=1;i<=N_i_chem;++i) {
                        mn_price[i]=min(mn_price[i],A[i][offset_j+j]);
                    }
                }
            }
            for (int i=1;i<=N_i_chem;++i) {
                price+=mn_price[i];
            }
            ans=min(ans,price);
            // dp[s]=price;
        }
        cout<<ans<<"\n";
    }

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365538444

*/

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

2025 CCPC 郑州——G. Plus Xor（ n 方复杂度，要想到记忆化 bfs 搜索）（记忆化 bfs 最重要的就是确定状态）（异或 b 只能改变 __lg(b)+1 位）（采用塞入的时候确定答案的，应该采用一 check/is_find_ans 函数，确保初始塞入情况和中途塞入情况采用同样的判断逻辑）

Posted on 2026-03-04 Edited on 2026-03-05

题目大意

题目描述
给定三个整数 $a, b, c$ ，每次可以选择执行以下两种操作之一：

$a \leftarrow a + b$
$a \leftarrow a \oplus b$ （ $\oplus$ 为按位异或运算）

你可以执行任意次上述操作。请判断最终是否能将 $a$ 变为 $c$ 。

输入格式
第一行为测试数据组数 $T$ （ $1 \le T \le 10^3$ ）。
接下来 $T$ 行，每组数据包含三个整数 $a, b, c$ （ $0 \le a, c \le 10^{18}$ ， $1 \le b \le 1000$ ）。
保证在一个测试点内 $\sum b^2 \le 10^6$ 。

输出格式
对于每组数据，如果最终能将 $a$ 变为 $c$ ，输出 YES，否则输出 NO。

样例数据

输入:
5
1 6 7
7 5 13
8 3 16
7 6 17
2 7 8

输出:
YES
NO
YES
YES
NO

样例解释

第一组数据 1 6 7：初始 $a=1$ ，执行一次加法操作 $1 + 6 = 7$ ，即可得到 $c=7$ ，输出 YES。
第二组数据 7 5 13：无法通过进行 $+5$ 或 $\oplus 5$ 操作从 $7$ 得到 $13$ ，输出 NO。
第三组数据 8 3 16：初始 $a=8$ ，执行路线可为：
$8 \xrightarrow{\oplus 3} 11 \xrightarrow{+3} 14 \xrightarrow{\oplus 3} 13 \xrightarrow{+3} 16$ ，最终得到 $c=16$ ，输出 YES。
第四组数据 7 6 17：初始 $a=7$ ，执行路线可为：
$7 \xrightarrow{+6} 13 \xrightarrow{\oplus 6} 11 \xrightarrow{+6} 17$ ，最终得到 $c=17$ ，输出 YES。
第五组数据 2 7 8：无法通过操作从 $2$ 得到 $8$ ，输出 NO。

思路讲解

2025 ICPC Asia Manila Regional（2025 ICPC 马尼拉）——vp 中通过题目总结（把题目对取模的要求用注释写在末尾）

收到这场比赛的题目 E. Long Distance Examination（远程操作克隆机器人，两人在不同迷宫中，B 尽力复刻 A 的所有操作）的启发，我们决定重新把这道题目给再盘一盘。

其实说白了，这道题目也很简单，虽然说数字可能很大，但是，我们可以只关注在 $\equiv\pmod b$ 的值，我们以这个为状态，进行记忆化 bfs，自然是非常少的（状态数）。

记忆化 bfs 最重要的就是确定状态**。**

当然，光有一个目前 mod b 的值是不够的，我们还需要再确定一个状态。

注意到，mod b 的值，是和这个 +b 相关的一个状态，这个提示我们，要采用一个和异或 b 相关的这个值，作为这个状态的组成部分。

注意到，异或 b 只能改变后 __lg(b)+1 位。

因此，最后 __lg(b)+1 位，确定了异或 b 操作能够增长（或减小的值）。再加上 mod b 的值，就唯一确定了这个状态。因为起点确定了，增长的值也确定了，那就什么都确定了。（这个是因为异或具有不可重复操作性，操作偶数次等于不操作，操作奇数次等于操作一次）

struct ModB_Low_bit {
    ll mod_b,low_bit,origin;
    bool operator<(const ModB_Low_bit &o) const {
        if (o.mod_b!=mod_b) return mod_b<o.mod_b;
        return low_bit<o.low_bit;
    }
};

AC代码

https://qoj.ac/submission/1787588

源代码


// https://qoj.ac/contest/2643/problem/15307
// https://qoj.ac/contest/2643
// by Gospel_rock
// title: ${PROBLEM_NAME}
// GROUP_NAME: ${PROBLEM_GROUP_NAME}
// ONLINE_JUDGE_NAME: ${ONLINE_JUDGE_NAME}

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#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;
struct Con {
    ll val;
    int needXor;
};
void Solve(){
	ll A,B,C;
    cin>>A>>B>>C;
    queue<Con> q;
    if (A==C) {
        cout<<"YES\n";
        return;
    }
    q.push({A,true});
    auto check=[&](ll x) {
        if (x<=C) {
            if ((C-x)%B==0) {
                return true;
            }
        }
        return false;
    };
    unordered_set<ll> vis;
    ll timer=0;
    while (!q.empty()) {
        auto [val,needXor]=q.front();
        ++timer;
        if (timer>B*B+1000) {
            break;
        }
        q.pop();
        if (needXor==false) {
            if (check(val+B)) {
                cout<<"YES\n";
                return;
            }
            if (vis.contains(val+B)) {
                continue;
            }
            vis.insert(val+B);
            q.push({val+B,true});
        }else {
            if (check(val+B)) {
                cout<<"YES\n";
                return;
            }
            if (vis.contains(val+B)) {

            }else {
                vis.insert(val+B);
                q.push({val+B,true});
            }
            if (check(val^B)) {
                cout<<"YES\n";
                return;
            }
            if (vis.contains(val^B)) {
                continue;
            }
            vis.insert(val^B);
            q.push({(val^B),false});
        }


    }
    cout<<"NO\n";
}

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

    cin>>lT;
    while(lT--)
        Solve();
    return 0;
}
/*
1
1 6 7

1
7 5 13

AC
https://qoj.ac/submission/1787521

*/

https://qoj.ac/submission/2095935

源代码（又重新写了一个这个严格的记忆化 bfs）

/**
 * Problem: Plus Xor
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-15307
 * Created: 2026-03-05 13:03:25
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */
struct ModB_Low_bit {
    ll mod_b,low_bit,origin;
    bool operator<(const ModB_Low_bit &o) const {
        if (o.mod_b!=mod_b) return mod_b<o.mod_b;
        return low_bit<o.low_bit;
    }
};
void Solve() {
    ll A,B,C;
    cin >> A >> B >> C;
    do {
        queue<ModB_Low_bit> q;
        const ll mask=(1<<(__lg(B)+1))-1;
        ll cmodb=C%B;
        if (A%B==cmodb && A<=C) {
            cout<<"YES\n";
            return;
        }
        q.push({A%B,mask&A,A});
        set<ModB_Low_bit> memo={{A%B,mask&A,A}};
        while (!q.empty()) {
            ModB_Low_bit t=q.front();
            q.pop();
            for (int i=1;i<=2;++i) {
                if (i==1) {
                    ModB_Low_bit to=t;
                    to.origin^=B;
                    to.mod_b=to.origin%B;
                    to.low_bit=mask&to.origin;
                    if (to.origin>C && (to.origin^B)>C) {
                        continue;
                    }
                    if (memo.contains(to)) {
                        continue;
                    }
                    if (to.mod_b==cmodb && to.origin<=C) {
                        cout<<"YES\n";
                        return;
                    }
                    q.push(to);
                    memo.insert(to);
                }else if (i==2) {
                    ModB_Low_bit to=t;
                    to.origin+=B;
                    to.mod_b=to.origin%B;
                    to.low_bit=mask&to.origin;
                    if (to.origin>C && (to.origin^B)>C) {
                        continue;
                    }
                    if (memo.contains(to)) {
                        continue;
                    }
                    if (to.mod_b==cmodb && to.origin<=C) {
                        cout<<"YES\n";
                        return;
                    }
                    q.push(to);
                    memo.insert(to);
                }
            }
        }
        cout<<"NO\n";
        return;
    }while (false);
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2095935

*/

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

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——vp 中通过题目总结（把题目对取模的要求用注释写在末尾）

Posted on 2026-03-04 Edited on 2026-03-05

题目 H. Prime Topology

https://codeforces.com/gym/106262/problem/H

题目描述
定义集合 $U_n = \{1, 2, 3, \dots, n\}$ 。
如果 $U_n$ 的一个子集 $S$ 满足：对于 $S$ 中任意两个不同的元素 $a$ 和 $b$ ，它们的绝对差 $|a - b|$ 都是素数，则称该子集 $S$ 为素数间距的（prime-spaced）。
给定正整数 $n$ 和 $k$ ，求在 $U_n$ 中，大小为 $k$ 的素数间距子集的数量。
由于答案可能很大，请输出其对 104206969 取模后的结果。
本题包含多组独立测试数据。

输入格式
第一行包含一个整数 $T$ （ $1 \le T \le 2 \times 10^5$ ），表示测试数据的组数。
接下来 $T$ 行，每行包含两个由空格分隔的整数 $n$ 和 $k$ （ $1 \le k \le n \le 10^7$ ）。

输出格式
对于每组测试数据，输出一行，表示大小为 $k$ 的素数间距子集的数量对 104206969 取模的值。

样例输入

3
5 2
6 3
10000000 10000000

样例输出

1
2
3

5
2
0

样例解释
对于第一组样例 $n=5, k=2$ ：
$U_5 = \{1, 2, 3, 4, 5\}$ ，要求找出大小为 2 且元素差值的绝对值为素数的子集。
差值为 2（素数）的子集有： $\{1, 3\}, \{2, 4\}, \{3, 5\}$
差值为 3（素数）的子集有： $\{1, 4\}, \{2, 5\}$
总共有 5 个满足条件的子集，故输出 5。

对于第二组样例 $n=6, k=3$ ：
$U_6 = \{1, 2, 3, 4, 5, 6\}$ ，要求找出大小为 3 且任意两个元素差值的绝对值均为素数的子集。
满足条件的子集仅有以下 2 个：

$\{1, 3, 6\}$ ：任意两元素差值分别为 $|1-3|=2$ ， $|3-6|=3$ ， $|1-6|=5$ ，均为素数。
$\{1, 4, 6\}$ ：任意两元素差值分别为 $|1-4|=3$ ， $|4-6|=2$ ， $|1-6|=5$ ，均为素数。
总共有 2 个满足条件的子集，故输出 2。

对于第三组样例 $n=10000000, k=10000000$ ：
要求选出大小等于全集的子集，即只能选择集合本身。显然该集合中包含了差值为 1 的元素对（如 1 和 2，且 1 不是素数），因此不存在满足条件的子集，故输出 0。

首先要注意到，除了 2 以外所有的素数都是奇数，奇数+奇数就是偶数一定是可以被除的。所以说只能是 2+另一素数+2。

注意，这道题目的这个询问量特别高，因此要把东西都处理出来。

if (K==1) {
    cout<<N<<"\n";
    return;
}
ll ans=0;
// 除了 2 以外所有的素数都是奇数，奇数+奇数就是偶数一定是可以被除的
if (K==2) {
    ans=N*cnt_prime[N]-pre_sum[N];
    ans%=mod;
    if (ans<0) {
        ans+=mod;
    }
    cout<<ans<<"\n";
    return;
}
if (K==3) {
    ans=N*cnt_prime_add2[N-2]*2-pre_sum_add2[N-2];
    ans%=mod;
    if (ans<0) {
        ans+=mod;
    }
    cout<<ans<<"\n";
    return;
}
if (K==4) {
    // 只有一个数，就是 3。
    for (auto p:p_add4_is_p) {
        ll len=p+2+2;
        if (len>=N) {
            break;
        }
        // if (minp[p+2+2]==p+2+2 && minp[p+2]==p+2) {
            ans+=(N-len);
            ans%=mod;
        // }
    }
    cout<<ans<<"\n";
    return;
}
if (K>=5) {
    cout<<0<<"\n";
    return;
}

AC
https://codeforces.com/gym/106262/submission/365350177

源代码

/**
 * Problem: H. Prime Topology
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/H
 * Created: 2026-03-04 19:32:02
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e7+100/*, INF = (1ll<<61)-1*/;
static constexpr ll mod = 104206969;
// static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
// ll minp[MAXN+100];
vector<ll> minp,primes,p_add4_is_p={3};
vector<ll> pre_sum,pre_sum_add2,cnt_prime,cnt_prime_add2;
void sieve(ll n){
    minp.resize(n+5);
    pre_sum.resize(n+5);
    pre_sum_add2.resize(n+5);
    cnt_prime.resize(n+5);
    cnt_prime_add2.resize(n+5);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    for(int i=2;i<=n;++i){
        if(minp[i]==0){		// 是素数
            minp[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(i*p>n){	// 超范围了
                break;
            }
            minp[i*p]=p;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
    for (int i=2;i<=n;++i) {
        pre_sum[i]=pre_sum[i-1];
        cnt_prime[i]=cnt_prime[i-1];
        pre_sum_add2[i]=pre_sum_add2[i-1];
        cnt_prime_add2[i]=cnt_prime_add2[i-1];
        if (minp[i]==i) {
            pre_sum[i]+=i;
            pre_sum[i]%=mod;
            cnt_prime[i]++;
            if (minp[i+2]==i+2) {
                pre_sum_add2[i]+=(i+2)*2;
                pre_sum_add2[i]%=mod;
                cnt_prime_add2[i]++;
            }
        }
    }
    // for (auto p:primes) {
    //     if (minp[p+2]==p+2) {
    //         p_add2_is_p.push_back(p);
    //         if (minp[p+4]==p+4) {
    //             p_add4_is_p.push_back(p);
    //         }
    //     }
    // }
}

void Solve() {
    ll N,K;
    cin >> N >> K;
    if (K==1) {
        cout<<N<<"\n";
        return;
    }
    ll ans=0;
    // 除了 2 以外所有的素数都是奇数，奇数+奇数就是偶数一定是可以被除的
    if (K==2) {
        // for (auto p:primes) {
        //     if (p>=N) {
        //         break;
        //     }
        //     ans+=N-p;
        //     ans%=mod;
        // }
        ans=N*cnt_prime[N]-pre_sum[N];
        ans%=mod;
        if (ans<0) {
            ans+=mod;
        }
        cout<<ans<<"\n";
        return;
    }
    if (K==3) {
        // for (auto p:p_add2_is_p) {
        //     ll len=p+2;
        //     if (len>=N) {
        //         break;
        //     }
        //     // if (minp[p+2]==p+2) {
        //         ans+=(N-len)*2;
        //         ans%=mod;
        //     // }
        // }
        ans=N*cnt_prime_add2[N-2]*2-pre_sum_add2[N-2];
        ans%=mod;
        if (ans<0) {
            ans+=mod;
        }
        cout<<ans<<"\n";
        return;
    }
    if (K==4) {
        // 只有一个数，就是 3。
        for (auto p:p_add4_is_p) {
            ll len=p+2+2;
            if (len>=N) {
                break;
            }
            // if (minp[p+2+2]==p+2+2 && minp[p+2]==p+2) {
                ans+=(N-len);
                ans%=mod;
            // }
        }
        cout<<ans<<"\n";
        return;
    }
    if (K>=5) {
        cout<<0<<"\n";
        return;
    }
    // modulo 104206969
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    sieve(MAXN);
    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365350177


_______________[ Stress test, testcase 18 INPUT ]_______________
1
10 4

_______________[ Stress test, testcase 18 OUTPUT]_______________
9

expected:3

*/

题目 E. Long Distance Examination（远程操作克隆机器人，两人在不同迷宫中，B 尽力复刻 A 的所有操作）

https://codeforces.com/gym/106262/problem/E

题目描述
Hero A 在网格 A 中，他正在远程控制位于网格 B 中的克隆人 Clone B 走迷宫。
两个网格的大小均为 $r \times c$ 。网格中包含空地（.）、障碍物（X）、起点（S）和终点（D）。起点 S 在两个网格中各出现一次，分别表示 Hero A 和 Clone B 的初始位置；终点 D 只在网格 B 中出现一次，表示 Clone B 需要到达的目的地。

Hero A 可以向上下左右四个方向移动，每次一步。他每尝试向某个方向移动一步，Clone B 也会尝试向相同的方向移动一步。移动规则如下：

如果 Hero A 的移动方向被障碍物或网格边界阻挡，那么 Hero A 无法移动，此时 Hero A 和 Clone B 都不会移动。
如果 Hero A 可以移动，但 Clone B 的移动方向被障碍物或边界阻挡，则 Hero A 会正常移动一步，而 Clone B 会停留在原地。
如果两者前方均无阻挡，则两人都正常向该方向移动一步。

求使得 Clone B 到达终点 D，Hero A 最少需要移动的步数。如果无法到达，输出 -1。

输入格式
第一行包含一个整数 $T$ （ $1 \le T \le 10$ ），表示测试数据的组数。
对于每组测试数据：
第一行包含两个由空格分隔的正整数 $r$ 和 $c$ （ $1 \le r, c \le 100, 2 \le r \times c \le 1000$ ）。
接下来 $r$ 行，每行包含一个长度为 $c$ 的字符串，表示网格 A 的状态。
再接下来 $r$ 行，每行包含一个长度为 $c$ 的字符串，表示网格 B 的状态。
字符仅包含 .、X、S 和 D。

输出格式
对于每组测试数据，输出一行，包含一个整数，表示最少需要的步数。如果不可达，则输出 -1。

样例输入

2
5 5
S....
.....
.....
.....
.....
....S
.....
.....
.....
....D
7 5
XXXXX
XXXXX
XS..X
X.X.X
X...X
XXXXX
XXXXX
XXXXX
XS..X
XXX.X
X...X
XXX.X
XD..X
XXXXX

样例输出

1
2

4
14

样例解释
对于第一组样例：
网格 A 的起点在左上角，网格 B 的起点在右上角，终点在右下角。尽管 Hero A 和 Clone B 的起点不同，由于两个网格中间都没有障碍物，Hero A 只需要一直向下走 4 步，Clone B 也会无阻挡地同时向下走 4 步到达终点。最少步数为 4。

对于第二组样例：
Hero A 位于网格 A 的 (3, 2)，而 Clone B 位于网格 B 的 (2, 2)。由于网格 B 中有较多障碍物阻挡了直接向下走向终点的路径，Hero A 可以利用“自己移动而 Clone B 被墙挡住留在原地”的机制来调整两者之间的相对位置。
最优解是 Hero A 在网格 A 中顺时针绕行：

Hero A 走一圈（右右下下左左上上，共 8 步）回到原点，此时 Clone B 会在跟随移动的过程中被障碍物卡住，最终停留在网格 B 的 (4, 2) 位置。
随后 Hero A 继续走第二圈（右右下下左左，走 6 步时），Clone B 会顺势移动到 (6, 2) 的终点 D。
总共花费 $8 + 6 = 14$ 步，使得 Clone B 到达终到达终点。

比较像这道题目 2025 CCPC 郑州的这道题目。

https://qoj.ac/contest/2661/problem/15307

2025 CCPC 郑州——G. Plus Xor（ n 方复杂度，要想到记忆化 bfs 搜索）（记忆化 bfs 最重要的就是确定状态）（异或 b 只能改变 __lg(b)+1 位）（采用塞入的时候确定答案的，应该采用一 check/is_find_ans 函数，确保初始塞入情况和中途塞入情况采用同样的判断逻辑）

这道题目比这个 G 简单，比较容易发现：

struct XY_AB{
    ll xa,ya,xb,yb;
    bool operator<(const XY_AB &o) const {
        if (xa!=o.xa) return xa<o.xa;
        if (ya!=o.ya) return ya<o.ya;
        if (xb!=o.xb) return xb<o.xb;
        return yb<o.yb;
    }
};

一个完整状态由 A 的位置和这个 B 的位置确定，我们只需要对这一状态进行记忆化 bfs 即可。

AC
https://codeforces.com/gym/106262/submission/365338227

源代码

/**
 * Problem: E. Long Distance Examination
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/E
 * Created: 2026-03-04 18:35:58
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */
struct XY_AB_STEP{
    ll xa,ya,xb,yb,step;
};
struct XY_AB{
    ll xa,ya,xb,yb;
    bool operator<(const XY_AB &o) const {
        if (xa!=o.xa) return xa<o.xa;
        if (ya!=o.ya) return ya<o.ya;
        if (xb!=o.xb) return xb<o.xb;
        return yb<o.yb;
    }
};
/* -> (Right, Down, Left, Up)
  |  |
   <-
*/
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
ll N_i,M_j;
bool check(vector<vector<char>> &A,ll i,ll j) {
    if (i<1 || i>N_i) {
        return false;
    }
    if (j<1 || j>M_j) {
        return false;
    }
    if (A[i][j]=='X') {
        return false;
    }
    return true;
}
void Solve() {
    cin >> N_i >> M_j;
    vector<vector<char>> A(N_i+2,vector<char>(M_j+2)),B(N_i+2,vector<char>(M_j+2));
    ll sax,say,sbx,sby,ebx,eby;
    for (int i=1;i<=N_i;++i) {
        for (int j=1;j<=M_j;++j) {
            cin>>A[i][j];
            if (A[i][j]=='S') {
                tie(sax,say)=tuple(i,j);
            }
        }
    }
    for (int i=1;i<=N_i;++i) {
        for (int j=1;j<=M_j;++j) {
            cin>>B[i][j];
            if (B[i][j]=='S') {
                tie(sbx,sby)=tuple(i,j);
            }else if (B[i][j]=='D') {
                tie(ebx,eby)=tuple(i,j);
            }
        }
    }
    // bfs
    do {
        queue<XY_AB_STEP> q;
        q.push({sax,say,sbx,sby,0});
        set<XY_AB> memo;
        ll idx=0;
        while (!q.empty()) {
            auto [ax,ay,bx,by,step]=q.front();
            memo.insert({ax,ay,bx,by});
            // ++idx;
            // if (idx>M_j*N_i*M_j*N_i) {
            //     cout<<-1<<"\n";
            //     return;
            // }
            q.pop();
            for (int i=0;i<4;++i) {
                ll to_ax=ax+dx[i],to_ay=ay+dy[i],to_bx=bx+dx[i],to_by=by+dy[i];
                if (!check(A,to_ax,to_ay)) {
                    continue;
                }
                if (check(B,to_bx,to_by)) {
                    if (to_bx==ebx && to_by==eby) {
                        cout<<step+1<<"\n";
                        return;
                    }
                    if (memo.contains({to_ax,to_ay,to_bx,to_by})) {
                        continue;
                    }
                    memo.insert({to_ax,to_ay,to_bx,to_by});
                    q.push({to_ax,to_ay,to_bx,to_by,step+1});
                }else {
                    if (memo.contains({to_ax,to_ay,bx,by})) {
                        continue;
                    }
                    memo.insert({to_ax,to_ay,bx,by});
                    q.push({to_ax,to_ay,bx,by,step+1});
                }
            }
        }
        cout<<-1<<"\n";
        return;
    }while (false);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365338227

*/

题目3

源代码

题目4

源代码

题目5

源代码

遇到一道题目没有思路的时候的多种解决方法

Posted on 2026-03-03 Edited on 2026-03-04

一、减少约束条件 / 从特殊情况入手（对于明显堆砌约束条件的题目较为有效）

Codeforces Round 1083 (Div. 2)——CF-2205-F. Simons and Reconstructing His Roads（遇到一道题目没有思路，可以先降低约束试一试）（±±，需要想到差分）（对割的理解以及使用）（格林公式的应用）

像这道题目，对于重建的这个约束太多。

Consider the case without any “accidents”, i.e., when there are no additional restrictions on the reconstructed streets.

不过，悲观地而言，只应用这一技巧想把这道题目做出来没什么用啊。

二、整体化为局部（格林公式，最优子结构，贪心）

Codeforces Round 1083 (Div. 2)——CF-2205-F. Simons and Reconstructing His Roads（遇到一道题目没有思路，可以先降低约束试一试）（+-+-，需要想到差分）（对割的理解以及使用）（格林公式的应用）

Posted on 2026-03-03 Edited on 2026-03-04

题目大意

题目大意

给定一个 $n \times m$ 的网格图，包含交汇点 $(1,1)$ 到 $(n,m)$ 。网格中的相邻交汇点之间存在道路：

点 $(i,j)$ 与 $(i+1,j)$ 之间为垂直道路，其权值为 $w_{i,j}$ 。
点 $(i,j)$ 与 $(i,j+1)$ 之间为水平道路，其权值为 $v_{i,j}$ 。

由于一些事故，部分道路无法被重建（由输入状态 $0$ 表示），其余道路可选择是否重建（由输入状态 $1$ 表示）。

对于网格中的任意一个交汇点，如果与其相连且最终被重建的道路数量为偶数，则称该交汇点是“优雅的”。
如果所有的交汇点都是“优雅的”，则称当前的整个道路重建方案是“完美的”。

美丽值计算方式

对于一个“完美的”重建方案，其“美丽值”的计算方式如下：

初始美丽值为 $0$ 。
对于每一行 $i$ ( $1 \le i \le n-1$ )，找出所有在这一行向下延伸（即连接 $(i,j)$ 与 $(i+1,j)$ ）且被重建的垂直道路。设它们所在的列号从小到大依次为 $c_1 < c_2 < c_3 < \dots$ ，则将 $w_{i,c_1} - w_{i,c_2} + w_{i,c_3} - w_{i,c_4} + \dots$ 累加到美丽值中。
对于每一列 $j$ ( $1 \le j \le m-1$ )，找出所有在这一列向右延伸（即连接 $(i,j)$ 与 $(i,j+1)$ ）且被重建的水平道路。设它们所在的行号从小到大依次为 $r_1 < r_2 < r_3 < \dots$ ，则将 $v_{r_1,j} - v_{r_2,j} + v_{r_3,j} - v_{r_4,j} + \dots$ 累加到美丽值中。
（简单来说，就是分别对“每行向下的重建道路”和“每列向右的重建道路”按坐标顺序交替加减其权值）

目标：在所有“完美的”重建方案中，求出最大的“美丽值”。

输入格式

第一行包含测试用例数 $t$ ( $1 \le t \le 5 \cdot 10^4$ )。
每个测试用例的第一行包含 $n$ 和 $m$ ( $2 \le n, m \le 2 \cdot 10^5, \sum n \cdot m \le 4 \cdot 10^5$ )。
接下来 $n-1$ 行，每行 $m$ 个整数，表示垂直道路的权值 $w_{i,j}$ 。
接下来 $n$ 行，每行 $m-1$ 个整数，表示水平道路的权值 $v_{i,j}$ 。
接下来 $n-1$ 行，每行一个长度为 $m$ 的 01 字符串，表示各条垂直道路是否可以被重建。
接下来 $n$ 行，每行一个长度为 $m-1$ 的 01 字符串，表示各条水平道路是否可以被重建。

输出格式

对于每个测试用例，输出一个整数，表示在所有完美重建方案中能获得的最大美丽值。

样例数据

样例解释

以第一个测试用例为例（ $n=3, m=4$ ，且所有道路均允许重建），在使得所有交汇点相连重建道路数均为偶数的前提下，取得最大美丽值的方案如下：

垂直道路（向下的边）的选择：

第 1 行向下重建位于列 1、列 3 的道路，权值分别为 $2, -2$ ，贡献值为： $2 - (-2)$
第 2 行向下重建位于列 2、列 4 的道路，权值分别为 $9, -4$ ，贡献值为： $9 - (-4)$

水平道路（向右的边）的选择：

第 1 列向右重建位于行 1、行 2 的道路，权值分别为 $3, -9$ ，贡献值为： $3 - (-9)$
第 2 列向右重建位于行 1、行 3 的道路，权值分别为 $4, -1$ ，贡献值为： $4 - (-1)$
第 3 列向右重建位于行 2、行 3 的道路，权值分别为 $1, -3$ ，贡献值为： $1 - (-3)$

该方案不仅满足所有交汇点度数皆为偶数，且其总美丽值为：
$(2 - (-2)) + (9 - (-4)) + (3 - (-9)) + (4 - (-1)) + (1 - (-3))$
$= 4 + 13 + 12 + 5 + 4 = 38$ 。

在第二个测试用例中，受限于无法重建的道路限制，唯一的完美重建方案是“不重建任何道路”，因此最大美丽值为 $0$ 。

思路讲解

像这道题目，对于重建的这个约束太多。

Consider the case without any “accidents”, i.e., when there are no additional restrictions on the reconstructed streets.

我们可以先把所有对于重建边操作的限制，就是有一些边不能进行重建操作，给删除，我们会做了吗？（注意这里不能够把这个偶数条边的这个结果也给删了）

其实也没有那么简单，你首先要注意到，对于一维问题，成对的±，相当于一系列差分的和。那么，还需要特意去选吗？直接选全部为正的差分值不就好了？（连续选了两个或更多差分值，有重叠也没关系，可以使用我们下图的逆运算）

但是这个只能解决成对的 ± 问题呀，要是 ±+，以 + 结尾的不成对串如何解决呢？

来，我们仔细看看。只需要在末尾加一个 0，然后采用同样的贪心即可。

好，下面我们要正式解决这个问题了。

问题来到了 2D，我们发现有一个这个约束，就是，点的偶数边重建约束，这个还是有点烦的，怎么样去解决这个问题？

不难想到，如果一个点的边是否重建受到约束，我们能不能找到一个东西，其无论怎么样取，都符合约束呢？这样无论是贪心还是 dp，都会好解决的多。

Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody

Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）

通过这些题目，我们知道，如果说所有的点的度数都是偶数，组成的一定是一个欧拉回路（在无向联通图中）。

那么在这道题目中，题目所给我们的图，实际上是一个对偶图（就是边不相交的平面图，显然，网格图是对偶图），欧拉回路在对偶图中，实际上是一个割（这个是不难得出的，说白了，你在平面上一笔画出一条回路，当然能把平面划分为两部分，特别还要求你的这个路径是不会自相交的，因为所有边都互不相交）。注意，可以确定的是，这些欧拉回路

那既然是一个割，把一个面分割成了两部分，我们就想到了黑白染色。

这个时候求解为什么能想到小的单位面元？从更高的观点来看，其实这个是离散型二维格林公式。

格林公式与这道题目的关系

没问题。这就把格林公式的灵魂，在这道离散的网格题目中扒得干干净净。这才是这道题最深层的物理/数学本质。

一、格林公式（Green’s Theorem）的核心灵魂是什么？

在高等数学里，格林公式极其优美，它建立了一个桥梁：

\oint_C (P dx + Q dy) = \iint_D \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) dx dy

别被公式吓到，它的灵魂用人话说就是：
“沿着一个闭合边界（外轮廓 $C$ ）转一圈的累积量，完全等于这个边界所包围的区域（内部面 $D$ ）里，每一个‘无穷小面元’的某种内在属性（旋度）的总和。”
为什么会这样？
因为如果你把区域 $D$ 切成无数个相邻的“小方格”，当你把所有小方格的“环量”加起来时，相邻方格的公共边界，一个是从左往右走，另一个是从右往左走，互相抵消了！最后没被抵消的，就只剩下最外面的那一圈大边界 $C$ 。

二、题目中的“线积分”在哪？

题目定义的“美丽值”计算方式非常奇怪：
“在每一行 $i$ 中，选中的列 $c_1, c_2, c_3, c_4 \dots$ 交替加减： $+w_{i, c_1} - w_{i, c_2} + w_{i, c_3} \dots$ ”
我们用几何的眼光来看这个式子。
题目要求所有十字路口的联边数必须是偶数。在图论里，这意味着选出来的边，必定构成若干个闭合的环（多边形）。
假设我们选出了一个大矩形环（左边界在 $c_1$ ，右边界在 $c_2$ ，上边界在 $r_1$ ，下边界在 $r_2$ ）。
按照题目的计算规则：

对于位于 $c_1$ 的左垂直边，它排在第 1 个（奇数），前面是正号 $\rightarrow$ $+w$ 。
对于位于 $c_2$ 的右垂直边，它排在第 2 个（偶数），前面是负号 $\rightarrow$ $-w$ 。
同理，上方的水平边排第一 $\rightarrow$ $+v$ 。
下方的水平边排第二 $\rightarrow$ $-v$ 。
发现了吗？
这个交替加减的规则，本质上就是定义了一个有向的线积分规则：
对于任何一个闭合形状，它的左边界贡献正，右边界贡献负，上边界贡献正，下边界贡献负。
这就是格林公式等式左边的那个 $\oint_C (\dots)$ ！也就是“沿着外围边界的环量”！

三、把格林公式用在离散网格上（微元化）

既然题目的美丽值求的是一个大环的“线积分（环量）”。
那么根据格林公式的思想，我们完全可以把这个大环，撕碎成无数个 $1 \times 1$ 的“无穷小面元（Basis / 小方块）”！
我们取网格中第 $i$ 行、第 $j$ 列的那个 $1 \times 1$ 的小方块。
如果我们把题目的线积分规则（左+，右-，上+，下-）强制套用到这个最微小的方块上，它就会产生一个属于它自己的“旋度”（也就是内在权值）：

Weight_{i,j} = \underbrace{w_{i,j}}{\text{左边界 (+) }} \quad \underbrace{- \quad w{i, j+1}}{\text{右边界 (-) }} \quad \underbrace{+ \quad v{i,j}}{\text{上边界 (+) }} \quad \underbrace{- \quad v{i+1,j}}_{\text{下边界 (-) }}

这就是那个 Basis 权值的确切由来！它就是离散版本的 $\left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right)$ ！

四、完美闭环：局部加和 = 全局边界

现在，我们见证格林公式在离散网格上发威的瞬间。
如果我们选定了某几个连续的小方块（构成了一个区域 $D$ ）。
我们直接把这几个小方块的 $Weight$ （旋度）全部加起来。
会发生什么？
比如方块 $(i,j)$ 和右边的方块 $(i, j+1)$ 被同时选中。

$(i,j)$ 的旋度里有一项是 $- w_{i, j+1}$ （它是右边界，取负）。
$(i, j+1)$ 的旋度里有一项是 $+ w_{i, j+1}$ （它是左边界，取正）。
当这两个方块加在一起时，中间这条公共边 $w_{i, j+1}$ 直接抵消为 0！
这在数学上绝对成立，没有任何例外：
只要你把一堆小方块的权值加起来，它们内部所有共享的边必定全部互相抵消。最后加出来的总和，绝对等于这堆小方块构成的外轮廓边界，按照题目“左+右-上+下-”规则算出来的值！

$\iint_D (\text{小方块权值}) = \oint_{\partial D} (\text{题目要求的美丽值交替求和})$

结语

格林公式告诉我们：算复杂的边界太难了，算简单的内部面元再相加就容易了。
题目要求我们在无数种复杂的“偶数闭合边界”中找最大值，这极其困难，因为边界的形状千变万化，且互相牵制。
但格林公式赋予了我们降维打击的武器：
我们根本不去管什么边界和交替相加！我们直接算好每一个 $1 \times 1$ 小方块的固定内在权值（旋度），然后只要权值是正的，我就把它拿走（贪心选这个面元）。
你拿走的这堆正权值面元，它们的外边缘自然而然就生成了题目要求的最优闭合边界，且美丽值自动最大化！
这就是这道算法题背后最深沉、最优美的数学灵魂。

具体而言，如下图所示：

现在问题在于如何处理这个有些边不能进行重建操作？

那么上图已经讲的很清楚了，不能重建的边，就像是胶水，直接把这两块给粘起来，这条边就不会再操作了。唯一一个特殊点就是最边上的边就是和外部联通了，这里我们需要设置一个外部节点 out_node，把他和 out 连接在一起即可。

AC代码

AC
https://codeforces.com/contest/2205/submission/365321534

源代码

/**
 * Problem: F. Simons and Reconstructing His Roads
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/F
 * Created: 2026-03-03 15:33:08
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */
struct X_Y {
    ll x,y;
    bool operator<(const X_Y &o) const {
        if (x!=o.x) {
            return x<o.x;
        }
        return y<o.y;
    }
    bool operator==(const X_Y &o) const {
        return o.x==x && o.y==y;
    };
};
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<ll>> w_i(N+2,vector<ll>(M+2));
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M;++j) {
            cin>>w_i[i][j];
        }
    }
    vector<vector<ll>> w_j(N+2,vector<ll>(M+2));
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=M-1;++j) {
            cin>>w_j[i][j];
        }
    }
    vector<vector<char>> valid_i(N+2,vector<char>(M+2));
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M;++j) {
            cin>>valid_i[i][j];
            valid_i[i][j]-='0';
        }
    }
    vector<vector<char>> valid_j(N+2,vector<char>(M+2));
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=M-1;++j) {
            cin>>valid_j[i][j];
            valid_j[i][j]-='0';
        }
    }
    map<X_Y,X_Y> fa;
    map<X_Y,ll> node_val;
    // 我们采用左上角标号来指定小方块
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M-1;++j) {
            node_val[{i,j}]=w_i[i][j]+w_j[i][j]-w_i[i][j+1]-w_j[i+1][j];
        }
    }
    auto find=[&](auto && self,X_Y x) -> X_Y {
        auto it=fa.find(x);
        if (it==fa.end()) {
            return x;
        }
        // if (it->second==x) {
        //     return x;
        // }
        return fa[x]=self(self,fa[x]);
    };
    auto merge=[&](X_Y u,X_Y v) -> void {
        auto fau=find(find,u),fav=find(find,v);
        if (fau==fav) {
            return;
        }
        fa[fau]=fav;
        node_val[fav]+=node_val[fau];
    };
    X_Y out_node={N+2,M+2};
    node_val[out_node]=-INF;
    // 我们采用左上角标号来指定小方块
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M;++j) {
            // cin>>valid_i[i][j];
            // valid_i[i][j]-='0';
            // （i，j） （i+1，j）
            if (!valid_i[i][j]) {
                if (j==1) {
                    // node_val[{i,j}]=-INF;
                    merge({i,j},out_node);
                    continue;
                }
                if (j==M) {
                    // node_val[{i,j-1}]=-INF;
                    merge({i,j-1},out_node);
                    continue;
                }
                merge({i,j-1},{i,j});
            }
        }
    }
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=M-1;++j) {
            // cin>>valid_i[i][j];
            // valid_i[i][j]-='0';
            // （i，j） （i+1，j）
            if (!valid_j[i][j]) {
                if (i==1) {
                    // node_val[{i,j}]=-INF;
                    merge({i,j},out_node);
                    continue;
                }
                if (i==N) {
                    // node_val[{i-1,j}]=-INF;
                    merge({i-1,j},out_node);
                    continue;
                }
                merge({i-1,j},{i,j});
            }
        }
    }
    ll ans=0;
    for (auto [node,v]:node_val) {
        if (node!=find(find,node)) {
            continue;
        }
        // 必须要是根，才能继续操作
        if (v>0) {
            ans+=v;
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2205/submission/365321534

1
2 4
4 23 1 35
6 12 -17
-14 1 -40
0100
000
101




*/

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

在并查集中，直接改动节点的值是非常幼稚的，因为你不知道他是不是根节点，当然你可以 find 后改根节点。

https://codeforces.com/contest/2205/submission/365204709

AI 代码确实是没什么问题。

题目大意

思路讲解

AC代码

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

题目大意

思路讲解

AC代码

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

题目 H. Prime Topology

题目 E. Long Distance Examination（远程操作克隆机器人，两人在不同迷宫中，B 尽力复刻 A 的所有操作）

题目3

题目4

题目5

一、减少约束条件 / 从特殊情况入手（对于明显堆砌约束条件的题目较为有效）

二、整体化为局部（格林公式，最优子结构，贪心）

题目大意

思路讲解

没问题。这就把格林公式的灵魂，在这道离散的网格题目中扒得干干净净。这才是这道题最深层的物理/数学本质。

一、 格林公式（Green’s Theorem）的核心灵魂是什么？

二、 题目中的“线积分”在哪？

三、 把格林公式用在离散网格上（微元化）

这就是那个 Basis 权值的确切由来！它就是离散版本的 (∂Q∂x−∂P∂y)\left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right)(∂x∂Q​−∂y∂P​)！

四、 完美闭环：局部加和 = 全局边界

结语

AC代码

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

一、格林公式（Green’s Theorem）的核心灵魂是什么？

二、题目中的“线积分”在哪？

三、把格林公式用在离散网格上（微元化）

这就是那个 Basis 权值的确切由来！它就是离散版本的 $\left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right)$ ！

四、完美闭环：局部加和 = 全局边界