区域赛铜牌题题单寒假纪

amiracle2026-02-012026-02-10

前言

刷刷某大佬整理的区域赛铜牌题题单 (十分之感谢!)

记录一下知识，顺便梳理思路

BA - BZ

BA - The Only Way to the Destination

难度: 2.5

问，任意两方块是否有唯一的简单路径。

思路

首先特判 n = 1 的情况，一定满足，一开始忘判了

n >= 2，发现存在 2 × 2 的方格就不能满足条件，而由于墙的列数不会很多(k ≤ 1e5)，所以 m ≤ 1e9 其实是诈骗，m > 3k 就肯定会有并列的两个空行，一定无法满足条件。此外，可以想象，若存在某个墙组成的连通块不和边界相连，则一定是因为某个路径将其包围，形成了一个环，这种情况一定不满足。

若合法，则一定有 m < 3k，于是我们可以枚举列，判断是否存在 2 × 2 的情况。判断墙是否和边界连通，可以对墙建图后 dfs

整体感觉不是很好写，比较考验码力

另外还要注意，墙是 8 连通而不是 4 连通

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int inf = 0x3f3f3f3f;

void solve(){
    int n, m, k;
    cin >> n >> m >> k;

// 边界
    if(n == 1){
        int x; while(cin>>x);
        cout << "YES" << '\n';
        return;
    }
    if(m > 3*k){
        int x; while(cin>>x);
        cout << "NO" << '\n';
        return;
    }

    vector<vector<pii>> col(m + 2);
    for(int i=1; i<=k; i++){
        int l, r, y;
        cin >> l >> r >> y;
        col[y].push_back({l, r});
    }
    col[0].push_back({1, n});
    col[m+1].push_back({1, n});
    for(int i=0; i<=m+1; i++){
        col[i].push_back({0, 0});
        col[i].push_back({n+1, n+1});
        sort(col[i].begin(), col[i].end());
    }
    bool ok = true;
    for(int i=1; i<=m; i++){
        int p1 = 1, p2 = 1;
        while(p1 < col[i-1].size()){ // (l, r) 左右都开, 边界需要处理一下
            while(p2 < col[i].size()-1 && col[i-1][p1-1].second+1 > col[i][p2].first-1) p2++;
            while(p2 < col[i].size() && col[i-1][p1].first-1 >= col[i][p2-1].second+1){
                int l = max(col[i-1][p1-1].second+1, col[i][p2-1].second+1);
                int r = min(col[i-1][p1].first-1, col[i][p2].first-1);
                if(r - l + 1 > 1) ok = false;
                p2++;
            }
            p2--;
            p1++;
        }
    }

    // 连通性判的不对 , 还是不对 , 墙是八连通
    map<pii, int> idx; // {i, p}
    vector<vector<int>> gra(k + 1);
    int tot = 0;
    for(int i=1; i<=m; i++){
        for(int j=1; j<col[i].size()-1; j++){
            idx[{i, j}] = ++tot;
        }
    }
    for(int i=2; i<=m; i++){
        int p = 1;
        for(int j=1; j<col[i].size()-1; j++){
            auto [l, r] = col[i][j];
            while(col[i-1][p].second+1 < l) p++;
            while(p < col[i-1].size()-1 && col[i-1][p].first-1 <= r){
                int u = idx[{i, j}], v = idx[{i-1, p}];
                // cout << u << ' ' << v << endl; // 
                gra[u].push_back(v);
                gra[v].push_back(u);
                p++;
            }
            p--;
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=2; j<col[i].size()-1; j++){
            if(col[i][j-1].second+1 == col[i][j].first){
                int u = idx[{i, j}], v = idx[{i, j-1}];
                gra[u].push_back(v);
                gra[v].push_back(u);
            }
        }
    }
    vector<bool> vis(k + 1);
    auto dfs = [&](auto&& self, int u) ->void {
        if(vis[u]) return;
        vis[u] = true;
        for(int v : gra[u]){
            self(self, v);
        }
    };
    vector<int> a;
    for(int i=1; i<col[1].size()-1; i++) a.push_back(idx[{1, i}]);
    for(int i=1; i<col[m].size()-1; i++) a.push_back(idx[{m, i}]);
    for(int i=1; i<=m; i++){
        for(int j=1; j<col[i].size()-1; j++){
            auto[l, r] = col[i][j];
            if(l == 1 || r == n){
                a.push_back({idx[{i, j}]});
            }
        }
    }
    for(auto u : a){
        dfs(dfs, u);
    }
    // cout << count(vis.begin()+1, vis.end(), true) << endl;
    ok &= (count(vis.begin()+1, vis.end(), true) == k);    
    cout << (ok? "YES":"NO") << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BB - Gene

怎么说呢，完全没思路，直接看答案了

难度: ?

q 次询问, 每次给你字符串 t，若 x 为 si 和 t 字符不相同的位置个数，问有几个 s 满足 x ≤ k

(1 ≤ N, Q ≤ 300, 1 ≤ M ≤ 60, 000,1 ≤ K ≤ 10) x

思路

思路还是很好懂的，就是对字母二进制化后用 bitset/ull 进行优化。具体来说是每个字母用 5 位二进制表示 (2⁵ > 26)，5 位全相等则这个字符相等，每次可以判断 64 个字符

也可以进行剪枝优化，因为 k 很小，比较容易超过

时间复杂度

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr int inf = 0x3f3f3f3f;

// bitset/ull 优化
// 26 - 5bit
void solve(){
    int n, q, m, k;
    cin >> n >> q >> m >> k;

    int z = (m+63) / 64;
    // 第 i 个字符串 , 第 j 位 , 第 k 个字符
    vector<vector<vector<ull>>> bit(n, vector<vector<ull>>(5, vector<ull>(z)));
    for(int i=0; i<n; i++){
        string s; cin >> s;
        int p = 0;
        while(p < m){
            int mask = s[p] - 'a';
            for(int j=0; j<5; j++){
                bit[i][j][p/64] |= (ull)(mask>>j&1) << (p%64);
            }
            p++;
        }
    }
    for(int qq=0; qq<q; qq++){
        string t; cin >> t;
        vector<vector<ull>> cur(5, vector<ull>(z));
        int p = 0;
        while(p < m){
            int mask = t[p] - 'a';
            for(int j=0; j<5; j++){
                cur[j][p/64] |= (ull)(mask>>j&1) << (p%64);
            }
            p++;
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            auto& vec = bit[i];
            int x = 0;
            for(int j=0; j<z; j++){
                ull mask = 0;
                for(int p=0; p<5; p++){
                    mask |= (vec[p][j] ^ cur[p][j]);
                }
                x += __builtin_popcountll(mask);
                // cout << x << endl;
                if(x > k) break;
            }
            if(x > k) continue;
            ans++;
        }
        cout << ans << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BC - Indeterminate Equation

难度: 2.5

问 a^k − b^k = n 有几个解

(T ≤ 10, n ≤ 1e18, 3 ≤ k ≤ 64)

思路

分类讨论，可以算出 k = 4 时，大概 a = 5e7 时就有 a^k − (a − 1)^k > 1e18，k > 4 时只会更少，所以可以暴力枚举 b，然后直接计算 a

当 k = 3 时，直接枚举 b 不可行。由 (a − b)³ = a³ − b³ + 3ab² − 3a²b 可以得到，(a − b)³ = n + 3ab² − 3a²b，可以发现 a-b 的值是可以枚举的，最多也不会超过 2e6 的级别。令 Δ = a − b 化简可得一元二次方程，。对称轴两边分别二分即可解出一元二次方程的两根。

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using i128 = __int128;

constexpr int inf = 0x3f3f3f3f;

void solve(){
    ll n; int k;
    cin >> n >> k;
    int ans = 0;
    if(k == 3){
        for(i128 i = 1; i * i * i < n; i++){
            if((n - i*i*i) % (3*i)) continue;
            double t = i / (-2);
            auto f = [&](auto x){
                return x*x + i*x - (n-i*i*i) / (3*i);
            };
            bool ok = false;
            {
                double lo = -1e15, hi = t;
                while(hi - lo > 1e-5){
                    double mid = (lo + hi) / 2;
                    if(f(mid) >= 0) lo = mid;
                    else hi = mid; 
                }
                ok |= (f((i128)lo)==0);
            }
            {
                double lo = t, hi = 1e15;
                while(hi - lo > 1e-5){
                    double mid = (lo + hi) / 2;
                    if(f(mid) >= 0) hi = mid;
                    else hi = mid;
                }
                ok |= (f((i128)hi)==0);
            }
            ans += ok;
        }
    }
    else if(k > 3){
        // b = 1
        int x = 2;
        while( 1 ){
            i128 a = 1;
            for(int i=0; i<k; i++){
                if(a > n+1) break;
                a *= x;
            }
            if(a > n+1) break;
            if(a == n+1) ans++;
            x++;
        }
        
        auto check = [&](int base, auto aim){
            i128 a = 1;
            for(int z=0; z<k; z++){
                a *= base;
                if(a >= aim) return true;
            }
            return false;
        };

        // b >= 2
        x = 2;
        {
            int lo = 1, hi = 7e5;
            while(lo + 1 != hi){
                int mid = lo + hi >> 1;
                if(check(mid, n)) hi = mid;
                else lo = mid;
            }
            x = lo;
        }
        i128 a = 1, lst = 1;
        for(int z=0; z<k; z++) a*=x;
        lst = a;
        for(int i=2; i<=700000; i++){
            i128 b = 1;
            for(int z=0; z<k; z++) b*=i;
            while(a < b+n){
                lst = a;
                x++;
                a = 1;
                for(int z=0; z<k; z++) a*=x;
            }
            if(a - lst > n) break;
            ans += (a-b==n);
        }
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; cin >> t;
    while(t--) solve();
    
    return 0;
}

BD - Rooted Tree

难度: 3

一开始只有一个节点，深度为 0，每次等概率的选一个叶子节点，给这个叶子节点新添 m 个节点，问 k 次操作后所有节点的深度和期望是什么

(k ≤ 1e7)

思路

错误思路:

可以设不同深度的节点个数分别为 x₀, x₁, x₂...，可以发现这样每次推下一层都是 O(n) 的，且式子很难优化，设法不是很好

正解:

首先可以发现每次操作后叶子节点个数是可算的，令 l_i 为第 i 次操作后的叶子个数

然后令 f_i 为叶子节点的深度和 (也就是不需要把每个深度的叶子个数都设出来)，可以得到递推式

其中为第 i 次操作后的平均叶子深度

答案就为

tip：此题求逆元可以前缀积优化到线性

具体来说

只需求出 pre_k 即可线性逆推

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr int inf = 0x3f3f3f3f;
constexpr int mo = 1e9 + 9;

ll qpow(ll a, ll x){
    ll ans = 1;
    while(x){
        if(x & 1) ans *= a;
        a *= a;
        x >>= 1;
        ans %= mo;
        a %= mo;
    }
    return ans;
}
int inv(int x){
    return qpow(x, mo-2);
}

void solve(){
    int m, k;
    cin >> m >> k;
    int ans = 0;
    int l = 1, f = 0; // 叶子数 , 叶子期望和
    vector<int> pre(k, 1);
    for(int i=1; i<k; i++){
        pre[i] = 1 + i*(m-1);
        pre[i] = 1ll * pre[i-1] * pre[i] % mo;
    }
    int invp = inv(pre[k-1]);
    vector<int> in(k + 1, 1);
    for(int i=k-1; i>=1; i--){
        in[i] = 1ll * invp * pre[i-1] % mo;
        invp = 1ll * invp * (1 + (-1+m)*i) % mo;
    }
    
    for(int i=0; i<k; i++){
        ans += 1ll * m * (1ll * f * in[i] % mo + 1) % mo;
        ans %= mo;
        f = f + 1ll * f * in[i] % mo * (m - 1) % mo + m;
        f %= mo;
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BE - Tavern Chess

难度: 2

炉石，每次最左攻击次数最少的随从开始发起攻击，等概率攻击对方随从，两人交替发起攻击，问 Alice 赢，输，平的概率分别是多少

(n, m ≤ 7)

思路

每次攻击至少有一个随从死亡且 n, m 很小，直接 dfs 暴力模拟即可

MYCODE

#include <bits/stdc++.h>
using namespace std;

constexpr int inf = 0x3f3f3f3f;

void solve(){
    int on, om;
    cin >> on >> om;
    vector<int> oa(on), ob(om);
    for(auto& x : oa) cin >> x;
    for(auto& x : ob) cin >> x;
    vector<array<int, 3>> ta(on), tb(om); // hp atk cnt
    for(int i=0; i<on; i++) ta[i] = {oa[i], oa[i], 0};
    for(int i=0; i<om; i++) tb[i] = {ob[i], ob[i], 0};
    double ans1 = 0, ans2 = 0, ans3 = 0;
    auto dfs = [&](auto&& self, auto a, auto b, double p, bool flg) ->void {
        if(a.empty() && b.empty()) ans3 += p;
        else if(a.empty()) ans2 += p;
        else if(b.empty()) ans1 += p;
        if(a.empty() || b.empty()) return;
        int n = a.size(), m = b.size();
        // a atk cnt
        if(flg){
            // 找 cnt mi
            int idx = 0, mi = inf;
            for(int i=0; i<n; i++){
                if(a[i][2] < mi){
                    idx = i;
                    mi = a[i][2];
                }
            }
            // 
            for(int i=0; i<m; i++){
                auto na = a, nb = b;
                na[idx][2]++;
                na[idx][0] -= nb[i][1];
                nb[i][0] -= na[idx][1];
                if(na[idx][0] <= 0) na.erase(na.begin()+idx);
                if(nb[i][0] <= 0) nb.erase(nb.begin()+i);
                self(self, na, nb, p/m, flg^1);                
            }
        }
        else{
            int idx = 0, mi = inf;
            for(int i=0; i<m; i++){
                if(b[i][2] < mi){
                    idx = i;
                    mi = b[i][2];
                }
            }
            for(int i=0; i<n; i++){
                auto na = a, nb = b;
                nb[idx][2]++;
                nb[idx][0] -= na[i][1];
                na[i][0] -= nb[idx][1];
                if(nb[idx][0] <= 0) nb.erase(nb.begin()+idx);
                if(na[i][0] <= 0) na.erase(na.begin()+i);
                self(self, na, nb, p/n, flg^1);                
            }
        }
    };
    if(on == om){
        dfs(dfs, ta, tb, 0.5, true);
        dfs(dfs, ta, tb, 0.5, false);
    }
    else dfs(dfs, ta, tb, 1, on>om);
    cout << fixed << setprecision(15) << ans1 << ' ' << ans2 << ' ' << ans3 << '\n';

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BG - Find Maximum

难度：2.5

找规律&数学，是个好题，要仔细思考

思路

先鸽一会儿

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int inf = 0x3f3f3f3f;

void solve(){
    ll l, r;
    cin >> l >> r;
    auto calc = [&](auto self, ll x) ->int {
        if(x == 0) return 1;
        if(x % 3 == 0) return 1 + self(self, x/3);
        return x%3 + self(self, x-x%3);
    };
    int ans = 0;
    ans = max(ans, calc(calc, r));
    if(r-1>=l) ans = max(ans, calc(calc, r-1));
    if(r-2>=l) ans = max(ans, calc(calc, r-2));
    // 上层
    {
        ll x = 1;
        while(x <= r) x *= 3;
        x /= 3; // 和 r 同层第一个数
        if(l <= x-1 && x-1 <= r) ans = max(ans, calc(calc, x-1));    
    }
    // 同层
    {
        ll x = 3;
        while(x <= r){
            ll t = r;
            t /= x, t *= x;
            t--;
            if(t < l) break;
            ans = max(ans, calc(calc, t));
            x *= 3;
        }
    }
    
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; cin >> t;
    while(t--) solve();
    
    return 0;
}

BH

难度: 2

很久以前在机房写的

思路

若只考虑第一种集合，可以发现所需集合数就是叶子节点个数。然后我们此时考虑第二种集合，最优肯定是删掉最下面的一层叶子。枚举删了几层叶子即可。

MYCODE

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
using ll = long long;
const int N=1e5+9; 
const int inf=3e18+9;

void run(){
    int n;
    cin >> n;
    vector<int> p(n + 1);
    vector<vector<int>> gra(n + 1);
    for(int i=2; i<=n; i++){
        int x;
        cin >> x;
        gra[x].push_back(i);
        p[i] = x;
    }
    
    int ans = inf;
    vector<int> del(n + 1);
    vector<int> leaf;
    for(int i=1; i<=n; i++){
        if(gra[i].size() == 0){
            leaf.push_back(i);
        }
    }
    ans = leaf.size();
    
    int cost = 0; 
    while(!leaf.empty()){
        vector<int> nxt;
        for(int x : leaf){
            del[p[x]]++;
            if(p[x] && del[p[x]] == gra[p[x]].size()){
                nxt.push_back(p[x]);
            }
        }
        leaf = nxt;
        cost++;
        ans = min(ans, cost + (ll)leaf.size());	
    }
    cout << ans << '\n';
    
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    for(;t;t--) run();
}

BI

给你 n 个数，要求变成全相等。有三种操作，+1,-1,/2，花费都是 1，求最小花费

难度: 2.5

思路：

注意到了一定是先除2，若不考虑除2操作，则是仓库选址的问题。若已经进行了若干次除2操作，最终的目标数是确定的，是中位数。注意到这个可能的中位数只有 nlog 个，我们可以枚举这个可能的中位数作为目标数，然后枚举计算每个元素变成目标数的最小花费，去掉 m 个较大的即可

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int inf = 0x3f3f3f3f;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for(int i=1; i<=n; i++) cin >> a[i];
    ll ans = inf;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=31; j++){
            vector<int> cost;
            for(int k=1; k<=n; k++){
                int mi = inf;
                for(int l=0; l<=31; l++){
                    mi = min(mi, l + abs((a[i] >> j) - (a[k] >> l)));
                }
                cost.push_back(mi);
            }
            ll sum = 0;
            sort(cost.begin(), cost.end());
            for(int k=0; k<n-m; k++){
                sum += cost[k];
            }
            ans = min(ans, sum);
        }
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; cin >> t;
    while(t--) solve();
    
    return 0;
}

BJ - Frozen Scoreboard

难度: 2

思路

题面略长，思路简单，只需要考虑 ? 的情况，m ≤ 13 可以状压枚举某道题过没过，然后贪心计算即可

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int inf = 0x3f3f3f3f;

void solve(){
    int n, m;
    cin >> n >> m;
    for(int nn=0; nn<n; nn++){
        int sol, tot;
        cin >> sol >> tot;
        vector<string> ans(m);
        vector<pii> a(m);
        int S = 0;
        for(int i=0; i<m; i++){
            char tp; cin >> tp;
            if(tp == '+'){
                string s; cin >> s;
                ans[i] = "+ " + s;
                // cout << *(find(s.begin(), s.end(), '/')) << endl; // 
                int x = stoi(string(s.begin(), find(s.begin(), s.end(), '/')));
                int y = stoi(string(find(s.begin(), s.end(), '/')+1, s.end()));
                tot -= (x - 1) * 20;
                tot -= y;
                sol--;
            }
            if(tp == '-'){
                int x; cin >> x;
                ans[i] = "- " + to_string(x);
            }
            if(tp == '?'){
                int x, y;
                cin >> x >> y;
                a[i] = {x, y};
                S += (1 << i);
            }
            if(tp == '.') ans[i] = ".";
        }
        // cout << tot << endl; //
        if(tot < 0){
            cout << "No" << '\n';
            continue;
        }
        if(sol == 0 && tot == 0){ // 封榜后没过题
            for(int p=0; p<m; p++) if(S >> p & 1) {
                auto [x, y] = a[p]; // x/y
                ans[p] = "- " + to_string(y);
            }
            cout << "Yes" << '\n';
            for(string s : ans) cout << s << '\n';
            continue;
        }

        bool ok = false;
        for(int T=S; T; T=(T-1)&S){ // 封榜后至少过 1 题
            if(__builtin_popcount(T) != sol) continue;
            int tm = tot;
            for(int p=0; p<m; p++){
                auto [x, y] = a[p]; // x/y
                if(S >> p & 1) ans[p] = "- " + to_string(y);
                if(!(T >> p & 1)) continue;
                tm -= (y-x) * 20;
                tm -= 240;
            }
            if(tm < 0) continue;
            for(int p=0; p<m; p++){
                if(!(T >> p & 1)) continue;
                auto [x, y] = a[p]; // x/y
                int cnt = 0; // 用了几次罚时
                int fn = 240; // 过题时间
                {
                    int z = min(tm / 20, x-1);
                    tm -= 20*z, cnt += z;
                }
                {
                    int z = min(tm, 59);
                    tm -= z, fn += z;
                }
                ans[p] = "+ " + to_string(y-x + cnt + 1) + "/" + to_string(fn);
            }
            if(tm != 0) continue;
            ok = true;
            cout << "Yes" << '\n';
            for(string s : ans) cout << s << '\n';
            break;
        }
        if(!ok) cout << "No" << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BK - Modulo Ruins the Legend

难度: 2.5

数学，线性同余方程，裴蜀定理，exgcd

线性同余方程。

x ∈ [0, m) 时， $有种，间隔，每个有个解，间隔$ 。另外还有 g|b

逆元。qpow(x, mod-2) 仅能求质数模数逆元，exgcd 可求任意模数逆元。另外逆元存在的前提条件是 gcd(x, mod) = 1

exgcd 可以求出 ax + by = g 的一组特解，若 a = k₁g, b = k₂g，则 ax, by 之间的最小调整量是 k₁k₂g

思路

题目求，即求 min{ax + by + c}

令 g = gcd(a, b), exgcd 求出 ax + by = g 的一组特解 x₀, y₀

转化成 min{gx + c}，由于 gx 的值域是 k ⋅ gcd(g, m) mod m，所以最小值

解出，设解为 f，则的解为 fx₀, fy₀

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int inf = 0x3f3f3f3f;
int p = -1;

void exgcd(int a, int b, int& x, int& y){
    if(b == 0){
        x = 1, y = 0;
        return;
    }
    int x1, y1;
    exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
}

// p任意 , gcd(a, p) != 1 则无解
ll inv(int a, int mod){
    int x, y;
    exgcd(a, mod, x, y);
    int g = a*x + mod*y;
    return g == 1 ? (x % mod + mod) % mod : -1;
}

// 逆元不能 mo-2 求, 因为 p 任意
void solve(){
    int n;
    cin >> n >> p;
    int z = 0;
    for(int i=0; i<n; i++){
        int x; cin >> x;
        z += x;
        z %= p;
    }
    int a = n % p, b = 1ll * n * (n + 1) / 2 % p;
    int x, y;
    exgcd(a, b, x, y);
    // cout << x << ' ' << y << '\n';
    int g = a*x + b*y;
    int cnt = (p - z + gcd(g, p)-1) / gcd(g, p);
    int res = (z + cnt*gcd(g, p)) % p;
    int f = 1ll * cnt * inv(g/gcd(g, p), (p/gcd(g, p))) % (p/gcd(g, p));
    x = (1ll * f * x % p + p) % p, y = (1ll * f * y % p + p) % p;
    cout << res << '\n';
    cout << x << ' ' << y << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BL - No Bug No Game

难度: 2

思路

01背包。最多只有一个物品是部分使用的，可以分成两层，dp0 代表选的物品中没有部分使用的物品，dp1 代表选的物品中有部分使用的物品，dp0 可以转移到 dp1，另外需要注意，最后取 dp0 所有状态最值和 dp1 的满容量状态最值

细节上就是注意初始化成 -inf，否则会导致 dp1 的计算出现问题，会导致不合法状态

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int inf = 0x3f3f3f3f;

// 初始 - inf 才是完全严格
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> sz(n + 1);
    vector<vector<int>> w(n + 1);
    for(int i=1; i<=n; i++){
        cin >> sz[i];
        w[i].resize(sz[i] + 1);
        for(int j=1; j<=sz[i]; j++){
            cin >> w[i][j];
        }
    }
    int ma = 0;
    vector<vector<int>> dp0(n + 1, vector<int>(m + 1, -inf)), dp1 = dp0;
    dp0[0][0] = 0;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=m; j++){
            dp0[i][j] = max(dp0[i][j], dp0[i-1][j]);
            dp1[i][j] = max(dp1[i][j], dp1[i-1][j]);
            if(j >= sz[i]){
                dp0[i][j] = max(dp0[i][j], dp0[i-1][j-sz[i]] + w[i][sz[i]]);
            }
            if(j >= sz[i]){
                dp1[i][j] = max(dp1[i][j], dp1[i-1][j-sz[i]] + w[i][sz[i]]);
            }
            ma = max(ma, dp0[i][j]);
        }
        for(int j=0; j<=m; j++){
            for(int k=1; k<=sz[i]; k++){
                if(j >= k){
                    dp1[i][j] = max(dp1[i][j], dp0[i-1][j-k] + w[i][k]);
                }
            }
        }
    }
    cout << max(ma, dp1[n][m]) << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BM Master of Both

难度: 2

给你 n 个字符串，按照给定的字典序比较，q 次询问，每次给定一个字典序，求这 n 个字符串逆序对的数量

(n ≤ 5e5, q ≤ 5e4)

思路

字典树，预处理

两个字符串比较，取决于第一个不相等的字符，我们只需要记录关键字符对 x-y 的数量，比如说 abc 和 abd，只需记录 c-d 字符对

每次询问 O(26²) 枚举给定的字典序即可

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
    int n, q;
    cin >> n >> q;

    int tot = 0;
    vector<map<char, int>> kid(1);
    vector<int> path(1), end(1); // 路径数, 终点个数
    vector<vector<ll>> cnt(26, vector<ll>(26)); // x-y 对
    ll pre = 0; // 前缀逆序
    auto insert = [&](string s) ->void {
        int x = 0;
        path[x]++;
        for(int i=0; i<s.size(); i++){
            char c = s[i];
            if(!kid[x].count(c)){
                kid[x][c] = ++tot;
                kid.push_back({});
                path.push_back({});
                end.push_back({});
            }
            for(int i=0; i<26; i++){
                if(kid[x].count('a'+i)){
                    cnt[i][c-'a'] += path[kid[x][i+'a']];
                }
            }
            x = kid[x][c];
            path[x]++;
            if(i == s.size()-1) end[x]++;
        }
        // pre += path[x] - 1; // 可能同一点终止
        pre += path[x] - end[x];
    };
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        insert(s);
    }

    for(int qq=0; qq<q; qq++){
        string s; cin >> s;
        ll ans = pre;
        for(int i=0; i<26; i++){
            for(int j=i+1; j<26; j++){
                ans += cnt[s[j]-'a'][s[i]-'a'];
            }
        }
        cout << ans << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

BY - Infection

期望树上背包合并

难度: 3

选一个点为根，每个点被选中的概率为，不断向外染色，每个点被染色成功的概率是 p_i，计算恰好 k 个节点被染色的概率，需要计算所有 k=1,2…n 的答案

思路

最后形成的一定是一个连通块。dp 来解决连通块相关的计数问题。

对于一个连通块 S，它的生成概率为

将此概率拆成两部分维护，令 dp[i][j] = {prod, val} ，代表连通块最上面的点是 i，当前形成的连通块大小为 j。

但是不包括 i 的父亲的 1 − p_fa，这个放到最后去乘

dp 状态转移

对于两个相邻且无重叠连通块 S1, S2，合并答案，则

prod₃ = prod₁ × prod₂

val₃ = val₁prod₂ + val2prod₁

之后进行树上背包合并就好了，时间复杂度 O(n²)

val 的转移公式推导

把前面的一坨简记为 ∑，后面的一坨简记为 p

$而，也同理$

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr int inf = 0x3f3f3f3f;
constexpr int mo = 1e9 + 7;

ll qpow(ll a, ll x){
    ll ans = 1;
    while(x){
        if(x & 1) ans *= a;
        a *= a;
        x >>= 1;
        ans %= mo;
        a %= mo;
    }
    return ans;
}
ll inv(int x){
    return qpow(x, mo - 2);
}

struct Node{
    ll prod;
    ll val;
};

// 期望, 树上背包合并
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> gra(n + 1);
    for(int i=0; i<n-1; i++){
        int u, v;
        cin >> u >> v;
        gra[u].push_back(v);
        gra[v].push_back(u);
    }

    ll sum = 0;
    vector<int> a(n + 1), p(n + 1);
    for(int i=1; i<=n; i++){
        int b, c;
        cin >> a[i] >> b >> c;
        sum += a[i]; sum %= mo;
        p[i] = b * inv(c) % mo;
    }
    
    ll isum = inv(sum);
    vector<int> sz(n + 1);
    vector<ll> ans(n + 1);
    vector<vector<Node>> dp(n + 1, vector<Node>(n + 1));
    auto dfs = [&](auto&& self, int fa, int u) -> void {
        sz[u] = 1;
        dp[u][1].prod = p[u];
        dp[u][1].val = a[u] * isum % mo;
        dp[u][0].prod = (1 - p[u] + mo) % mo; // 断点
        dp[u][0].val = 0;
        for(int v : gra[u]) if(v != fa) {
            self(self, u, v);
            vector<Node> ndp(n + 1, {0, 0});
            ndp[0] = dp[u][0];
            for(int i=1; i<=sz[u]; i++){
                for(int j=0; j<=sz[v]; j++){
                    ndp[i+j].prod += dp[u][i].prod * dp[v][j].prod % mo;
                    ndp[i+j].val += (dp[u][i].val * dp[v][j].prod + dp[u][i].prod * dp[v][j].val) % mo;
                    ndp[i+j].prod %= mo; ndp[i+j].val %= mo;
                }
            }
            sz[u] += sz[v];
            swap(dp[u], ndp);
        }
        for(int i=1; i<=sz[u]; i++){
            ans[i] += dp[u][i].val * (fa==0? 1:(1-p[fa]+mo)%mo) % mo;
            ans[i] %= mo;
        }
    };
    dfs(dfs, 0, 1);
    for(int i=1; i<=n; i++){
        cout << ans[i] << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}