2025“钉耙编程”中国大学生算法设计春季联赛（1）

62天前 · 题解 · 152次阅读

1001 签到

签到题。

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

#define int long long
void solve() {
    int n;cin>>n;
    string a;cin>>a;
    int pos=-1;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        if(s==a)pos=i;
    }
    cout<<pos<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1002 船长

为了描述方便，我们把这 $k$ 个人称为高手

考虑用 $a$ 数组存储高手可能的位置（first）以及是高手的概率（second）。我们直接在 $log$ 轮暴力模拟最终的游戏，用 $ans$ 记录被高手击败的概率，$st$ 记录染染的位置。

  • 不管是奇数还是偶数，第 $i$ 个位置的高手经过一把游戏，新位置都是 $(a[i].first+1)/2$ 。

  • 当前这个高手的位置是奇数：

    • 如果他是最后一个人，高手的概率不变。
    • 如果不能和后面合并，下一轮游戏中是高手的概率减半。
    • 如果能和后面合并，并且需要合并的这两个都不是染染，由于合并时任意一方获胜的概率都是50%，那么新一把游戏相应位置是高手的概率是 $50\%*a[i].second+50\%*a[i+1].second$ ，下一次处理时跳过后面偶数位。
    • 如果能和后面合并，并且需要合并的有一个是染染，那么染染在这一局赢过高手的概率就是 之前没赢得概率*对面是高手的概率 ，新位置对应是高手的概率是0，下一次处理时跳过后面偶数位。
  • 当前这个高手的位置是偶数，由于我遍历到的偶数一定都是不能合并得偶数位（能合并的在我处理奇数位时一块处理了），所以概率减半。
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 42
#endif

template <unsigned M_> struct ModInt {
    static constexpr unsigned M = M_;
    unsigned x;
    constexpr ModInt() : x(0U) {}
    constexpr ModInt(unsigned x_) : x(x_ % M) {}
    constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
    constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
    constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
    constexpr ModInt operator++() { (*this) += 1; return *this; }
    constexpr ModInt operator--() { (*this) -= 1; return *this; }
    constexpr ModInt operator++(int) { const ModInt temp = *this; ++(*this); return temp; }
    constexpr ModInt operator--(int) { const ModInt temp = *this; --(*this); return temp; }
    ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
    ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
    ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
    ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
    ModInt pow(long long e) const {
        if (e < 0) return inv().pow(-e);
        ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
    }
    ModInt inv() const {
        unsigned a = M, b = x; int y = 0, z = 1;
        for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
        assert(a == 1U); return ModInt(y);
    }
    ModInt operator+() const { return *this; }
    ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
    ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
    ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
    ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
    ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
    template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
    template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
    template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
    template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
    explicit operator bool() const { return x; }
    bool operator==(const ModInt &a) const { return (x == a.x); }
    bool operator!=(const ModInt &a) const { return (x != a.x); }
    bool operator<(const ModInt &a) const { return (x < a.x); }
    bool operator>(const ModInt &a) const { return (x > a.x); }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
    friend std::istream &operator>>(std::istream &is, ModInt &a) { return is >> a.x; }
};

constexpr int P = 998244353;
using Z = ModInt<P>;

void solve() {
    int n,k;cin>>n>>k;
    vector<pair<int,Z>> a;
    for(int i=0;i<=k;i++){
        int x;cin>>x;a.push_back({x,1});
    }
    int st=a[0].first;
    a[0].second=0;
    sort(a.begin(),a.end());
    Z ans=0;
    while(n!=1){
        vector<pair<int,Z>> tmp;
        int k=a.size();
        for(int i=0;i<k;i++){
            int p=(a[i].first+1)/2;
            Z v=a[i].second/2;
            if(a[i].first&1){
                if(a[i].first==n){
                    v=a[i].second;
                }
                else if(i<k-1&&a[i+1].first-1==a[i].first){
                    if(a[i].first!=st&&a[i+1].first!=st){
                        v=(a[i].second+a[i+1].second)/2;
                    }
                    if(a[i].first==st||a[i+1].first==st){
                        ans+=(1-ans)*(a[i].second+a[i+1].second);
                        v=0;
                    }
                    i++;
                }
            }
            tmp.push_back({p,v});
        }
        a=tmp;st=(st+1)/2;n=(n+1)/2;
    }
    cout<<1-ans<<'\n';


}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1003 船舱（待补）

1004 海浪

很常见的处理区间问题的思路。这类问题都有一个特点，如何重复利用之前的信息。

首先考虑没有任何限制下如何求每个点作为左端点的海浪长度，显然这个需要 奇数位的最大值小于偶数位的最小值 或者 偶数位的最大值小于奇数位的最小值 ，并且每个左端点对应的海浪的右端点是递增的（海浪的子序列依旧是海浪，例如 $[l,r]$ 是海浪，那么 $[l+1,r]$ 一定是海浪，而且 $l+1$ 对应的最短点由于少了一个 $l$ 的限制，它对应的海浪右端点可能会更长）。题解采用两个 $multiset$ 来处理，$L$ 记录当前海浪的左端点，用 judge 函数判断是否是海浪，如果不是就移除左端点（这个左端点现在才被移除，说明 $i-1$ 这个位置一定是L最长的海浪右端点），这样就通过类似双指针的思路处理出来了每个位置对应的最长海浪的长度。同时用 $l[i]$ 记录右端点对应的海浪左端点最小值。

得到了每个端点能延长的最长长度，我们存到线段树里面。

现在考虑将询问进行离线处理，按照右端点从大到小排序

  1. 询问的右端点 $r$ 恰好为 $n$ ，这时候直接线段树获取区间 $[l,n]$ 最大值即可得到答案。
  2. 询问的右端点 $r$ 变成 $n-1$ ，这时候我们考虑少了一个 $n$ 会对前面线段树维护的值产生什么影响，这个影响就是让某些点最长延长的长度减一，而根据我们之前推出来的性质，$n$ 这个点影响到左端点一定是连续的，所以把预处理能影响到的最左边的区间减1即可得到所有端点最长延伸到 $r-1$ 的答案。
  3. 之后重复上述过程即可。
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 42
#endif
// #define int long long
template <unsigned M_> struct ModInt {
    static constexpr unsigned M = M_;
    unsigned x;
    constexpr ModInt() : x(0U) {}
    constexpr ModInt(unsigned x_) : x(x_ % M) {}
    constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
    constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
    // constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
    constexpr ModInt operator++() { (*this) += 1; return *this; }
    constexpr ModInt operator--() { (*this) -= 1; return *this; }
    constexpr ModInt operator++(int) { const ModInt temp = *this; ++(*this); return temp; }
    constexpr ModInt operator--(int) { const ModInt temp = *this; --(*this); return temp; }
    ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
    ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
    ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
    ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
    ModInt pow(long long e) const {
        if (e < 0) return inv().pow(-e);
        ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
    }
    ModInt inv() const {
        unsigned a = M, b = x; int y = 0, z = 1;
        for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
        assert(a == 1U); return ModInt(y);
    }
    ModInt operator+() const { return *this; }
    ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
    ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
    ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
    ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
    ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
    template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
    template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
    template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
    template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
    explicit operator bool() const { return x; }
    bool operator==(const ModInt &a) const { return (x == a.x); }
    bool operator!=(const ModInt &a) const { return (x != a.x); }
    bool operator<(const ModInt &a) const { return (x < a.x); }
    bool operator>(const ModInt &a) const { return (x > a.x); }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
    friend std::istream &operator>>(std::istream &is, ModInt &a) { return is >> a.x; }
};

constexpr int P = 1e9+7;
using Z = ModInt<P>;

struct SegTree {
    #define mid (t[rt].l+t[rt].r>>1)
    #define ls (rt<<1)
    #define rs (rt<<1|1)
    struct info {
        int val, l, r, lazy, maxx;
    };
    vector<info> t;

    SegTree(int n) : t(4 * n + 5) { init(1, 1, n); }

    void init(int rt, int l, int r) {
        t[rt] = {0, l, r, 0, 0};
        if (l == r) return;
        init(ls, l, mid);
        init(rs, mid + 1, r);
    }

    void pushdown(int rt) {
        if (t[rt].lazy) {
            int lz = t[rt].lazy;
            t[ls].lazy += lz;
            t[rs].lazy += lz;
            t[ls].val += lz * (t[ls].r - t[ls].l + 1);
            t[rs].val += lz * (t[rs].r - t[rs].l + 1);
            t[ls].maxx += lz;
            t[rs].maxx += lz;
            t[rt].lazy = 0;
        }
    }

    void pushup(int rt) {
        t[rt].val = t[ls].val + t[rs].val;
        t[rt].maxx = max(t[ls].maxx, t[rs].maxx);
    }

    void add(int l, int r, int x, int rt = 1) {
        if (l <= t[rt].l && t[rt].r <= r) {
            t[rt].lazy += x;
            t[rt].maxx += x;
            t[rt].val += (t[rt].r - t[rt].l + 1) * x;
            return;
        }
        pushdown(rt);
        if (l <= mid) add(l, r, x, ls);
        if (r > mid) add(l, r, x, rs);
        pushup(rt);
    }

    int qmax(int l, int r, int rt = 1) {
        if (l <= t[rt].l && t[rt].r <= r) return t[rt].maxx;
        pushdown(rt);
        int ans = 0;
        if (l <= mid) ans = max(ans, qmax(l, r, ls));
        if (r > mid) ans = max(ans, qmax(l, r, rs));
        return ans;
    }
};

void solve() {
    int n,m;cin>>n>>m;
    vector<multiset<int>> se(2);
    vector<int> l(n+1),a(n+1);
    SegTree seg(n);
    auto judge=[&](){
        if(*se[1].rbegin()<*se[0].begin()){
            return 1;
        }
        if(*se[0].rbegin()<*se[1].begin()){
            return 1;
        }
        return 0;
    };
    int L=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        se[i&1].insert(a[i]);
        if(se[1].empty()||se[0].empty())continue;
        while(se[1].size()&&se[0].size()&&!judge()){            
            seg.add(L,L,i-L);
            se[L&1].erase(se[L&1].lower_bound(a[L]));
            L++;
        }
        l[i]=L;
    }
    for(int i=L;i<=n;i++)seg.add(i,i,n+1-i);
    vector<array<int,3>> ask(m+1);
    for(int i=1;i<=m;i++){
        cin>>ask[i][0]>>ask[i][1];
        ask[i][2]=i;
    }
    sort(ask.begin()+1,ask.end(),[&](auto a,auto b){
        return a[1]>b[1];
    });
    int pos=1;
    Z ans=0;
    debug(l);
    for(int i=n;i>=1;i--){
        while(pos<=m&&ask[pos][1]==i){
            auto [l,r,id]=ask[pos];
                ans+=seg.qmax(l,r)*Z(id);
            pos++;
        }
        seg.add(l[i],n,-1);
    }
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1005 航线

类似之前做过的一个镜子题，我写的很屎

建议参考 这个题解

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 42
#endif

#define int long long
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<vector<int>>> mp(
        4, vector<vector<int>>(n + 1, vector<int>(m + 1, 0)));
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            mp[0][i][j] = ++cnt;
            mp[1][i][j] = ++cnt;
            mp[2][i][j] = ++cnt;
            mp[3][i][j] = ++cnt;
        }
    }
    auto getid = [&](int x, int y, int op) {
        if (mp[op][x][y])
            return mp[op][x][y];
    };
    vector<vector<pair<int, int>>> e(n * m * 4 + 1);
    vector<int> dx = {-1, 0, 1, 0};
    vector<int> dy = {0, -1, 0, 1};
    vector<int> ne = {2, 3, 0, 1};
    auto add = [&](int xid, int yid, int dis) {
        e[xid].push_back({dis, yid});
        e[yid].push_back({dis, xid});
    };
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k < 2; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;
                int nowid = getid(i, j, k);
                int newid = getid(nx, ny, ne[k]);
                add(nowid, newid, 0);
            }
        }
    }
    vector<vector<int>> t(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int d;
            cin >> d;
            t[i][j] = d;
            int xid = getid(i, j, 0), yid = getid(i, j, 2);
            add(xid, yid, d);
            xid = getid(i, j, 1), yid = getid(i, j, 3);
            add(xid, yid, d);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int d;
            cin >> d;
            d += t[i][j];
            vector<int> id(4);
            for (int k = 0; k < 4; k++)
                id[k] = getid(i, j, k);
            for (int k = 0; k < 4; k++) {
                add(id[k], id[(k + 1) % 4], d);
            }
        }
    }
    vector<int> dis(n * m * 4 + 1, 1E18);
    auto djikstra = [&](int s) -> void {
        using PII = pair<int, int>;
        priority_queue<PII, vector<PII>, greater<PII>> q;
        q.emplace(0, s);
        dis[s] = 0;
        vector<int> vis(n * m * 4 + 1);
        while (!q.empty()) {
            int x = q.top().second;
            q.pop();
            if (vis[x])
                continue;
            vis[x] = 1;
            for (auto [w, y] : e[x]) {
                if (dis[y] > dis[x] + w) {
                    dis[y] = dis[x] + w;
                    q.emplace(dis[y], y);
                }
            }
        }
    };
    djikstra(getid(1, 1, 1));
    cout << dis[getid(n, m, 2)] << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

1006 密码

枚举一个数的答案检验是否正确。

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 42
#endif

#define int long long
void solve() {
    int n;
    cin >> n;
    vector<array<int, 3>> q(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> q[i][0] >> q[i][1] >> q[i][2];
    }

    auto check = [&](int x) {
        for (int i = 1; i <= n; i++) {
            array<int, 3> p = q[i];
            sort(p.begin(), p.end());
            bool valid = false;
            do {
                if (p[0] * x + p[1] == p[2]) {
                    valid = true;
                    break;
                }
            } while (next_permutation(p.begin(), p.end()));
            if (!valid) return false;
        }
        return true;
    };

    array<int, 3> p = q[1];
    sort(p.begin(), p.end());
    do {
        if ((p[2] - p[1]) % p[0] == 0) {
            int x = (p[2] - p[1]) / p[0];
            if (x >= 0 && check(x)) {
                cout << x << '\n';
                return;
            }
        }
    } while (next_permutation(p.begin(), p.end()));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

1007 分配宝藏

如果只有一个手下，肯定不给他分钱。

0

如果有两个手下，我肯定要联合继承人2，给他一元他就能支持我，而继承人1不给钱，因为如果继承人2和继承人1联手击败了船长，那么就变成了上面的情况，继承人2一分钱都拿不到，支持现在的船长还能拿到一元。

0 1

如果现在有三个手下，我应该联合继承人2，因为继承人2反对的话会变成上面这种情况，继承人2拿不到钱，还不如现在拿1元

0 1 0
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 42
#endif
template <unsigned M_> struct ModInt {
    static constexpr unsigned M = M_;
    unsigned x;
    constexpr ModInt() : x(0U) {}
    constexpr ModInt(unsigned x_) : x(x_ % M) {}
    constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
    constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
    // constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
    constexpr ModInt operator++() { (*this) += 1; return *this; }
    constexpr ModInt operator--() { (*this) -= 1; return *this; }
    constexpr ModInt operator++(int) { const ModInt temp = *this; ++(*this); return temp; }
    constexpr ModInt operator--(int) { const ModInt temp = *this; --(*this); return temp; }
    ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
    ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
    ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
    ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
    ModInt pow(long long e) const {
        if (e < 0) return inv().pow(-e);
        ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
    }
    ModInt inv() const {
        unsigned a = M, b = x; int y = 0, z = 1;
        for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
        assert(a == 1U); return ModInt(y);
    }
    ModInt operator+() const { return *this; }
    ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
    ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
    ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
    ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
    ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
    template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
    template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
    template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
    template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
    explicit operator bool() const { return x; }
    bool operator==(const ModInt &a) const { return (x == a.x); }
    bool operator!=(const ModInt &a) const { return (x != a.x); }
    bool operator<(const ModInt &a) const { return (x < a.x); }
    bool operator>(const ModInt &a) const { return (x > a.x); }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
    friend std::istream &operator>>(std::istream &is, ModInt &a) { return is >> a.x; }
};

constexpr int P = 1e9+7;
using Z = ModInt<P>;
// #define int long long
void solve() {
    int n;cin>>n;
    function<Z(int x)> get=[&](int x){
        return Z(x)*Z(1+x)/Z(2);
    };
    cout<<get(n/2)*Z(2)<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}
//0
//0 1
//0 1 0
//0 1 0 1

1008 运输（待补）

1009 切割木材

比较麻烦的dp

  • dp[i]：表示第 $i$ 个位置的答案，$n^2$转移

    $$ dp[i]=max_{j=1}^{i}\left(dp[i],dp[j-1]+g(f(l,r)) \right) $$

  • 我们考虑这个 $f(l,r)$ 的变化，在固定 $i$ ，$j$ 变化的过程中，$f(l,r)$ 的值最多只会变化 m 次。所以我们在转移的时候可以批量处理$f(l,r)$ 相等的一堆连续区间，用线段树维护区间max，单点修改区间查询，复杂度 $O(n*m)$
  • 当 $l==r$ 的时候，$f(l,r)$ 的值就是0，每次 $f(l,r)$ 变化的时候，也就是这一位二进制出现了和第 i 个数这一位二进制不同的地方（在 $j>p$ 时贡献都是0，其次之外贡献都是1），所以我们预处理出来每一位二进制变化单独进行处理即可
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 42
#endif

#define int long long

struct Segt {
    vector<int> wmax;
    int n;
    Segt(int n) : wmax(2 * n + 4 , (int)0), n(n) {}

    // 更新位置 pos 的值为 val
    void modify(int pos, int val) {
        for (wmax[pos += n] = val; pos > 1; pos /= 2) {
            wmax[pos / 2] = max(wmax[pos], wmax[pos ^ 1]);
        }
    }

    int qmax(int l, int r) {
        int res = -1e18;
        if(l == 0) res = 0,l = 1;//dp[0]记为0，其他位置可能是负数，设置成1e8
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) res = max(res, wmax[l++]);
            if (r % 2 == 1) res = max(res, wmax[--r]);
        }
        return res;
    }
};
void solve() {
    int n,m;cin>>n>>m;

    vector<int> a(n+1);
    vector<int> g(1ll<<m);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<(1ll<<m);i++)cin>>g[i];
    Segt dp(n);
    auto pos=vector<vector<int>>(2,vector<int>(m,0));//

    for(int i=1;i<=n;i++){
        vector<array<int,2>> op;
        for(int j=0;j<m;j++){
            int nval=(a[i]>>j)&1;
            pos[nval][j]=i;//记录上一个这个位置出现的地方
            if(pos[nval^1][j])op.push_back({pos[nval^1][j],1ll<<j});
        }
        sort(op.begin(),op.end(),greater<>());
        int val=0;
        int r=i;
        int ans=-1e18;

        for(int p=0,nep=0;p<op.size();p=nep){
            int tmp=0;
            int l=op[p][0]+1;
            while(nep<op.size()&&(op[nep][0]==op[p][0])){
                tmp+=op[nep][1];
                nep++;
            }
            ans=max(g[val]+dp.qmax(l-1,r-1),ans);
            val+=tmp;
            r=l-1;
        }
        ans=max(ans,g[val]+dp.qmax(0,r-1));
        dp.modify(i,ans);
    }
    cout<<dp.qmax(n,n)<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1010 返航（待补）

👍 0

none

最后修改于59天前

评论

目录

avatar

coolarec

你好，未曾谋面的陌生人

31

文章数

16

评论数

5

分类

那就出发吧！

❤ 99

  • 赛事游记
  • 日常
  • coding
  • 全部