codeforces/atcoder 选题

2022-05-15 | 阅读：次

===

Index

codeforces
atcoder

atcoder/codeforce选题

codeforces

二进制字符串的最小代价

ecr128c div2

二进制字符串s，你可以从s的开始和结束删除任意数目的字符(包括0个或者全部)，删除后的字符串代价是下面两个值的最大值

剩余字符串中0的数目
删掉字符串中1的数目

求删除后字符串s的最小代价。

1 <= n <= 2e5

方法1:二分

设总共有m个1，其出现位置分别在p[0],,,p[m-1], 则答案不超过m，对答案进行二分，设当前检测的答案为md,则我们最多能删除md个1，且当我们删除md个1时，能留下最少的0，因为从两端删除1不回增加剩下的0的数目。依次枚举，前面删除i个1，后面删除md-i个1时，中间留下的0是否小于等于md，判断md答案成不成立即可。

int minStringCost(string& s) {
    int n = s.size();
    vector<int> s1(n + 1), p;
    for (int i = 0; i < n; ++i) {
        s1[i + 1] = s1[i] + (s[i] == '0');
        if (s[i] == '1') p.push_back(i);
    }
    int m = p.size(), l = 0, r = m, ans = m;
    while (l < r) {
        int md = (l + r) / 2;
        bool ok = 0;
        for (int i = 0; i <= md; ++i) {
            int l1 = p[i], r1 = p[m - 1 - md + i];
            if (s1[r1 + 1] - s1[l1] <= md) {
                ok = 1;
            } 
        }
        if (ok) r = md;
        else l = md + 1;
    }
    return l;
}

方法2：滑动窗口

int minStringCost1(string& s) {
    int n = s.size(), x = 0, y = 0, ans = n;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0') x++;
        else y++;
    }
    int x1 = 0, y1 = y, j = 0;
    for (int i = 0; i < n; ++i) {
        while (j < n && x1 < y1) {
            if (s[j] == '0') x1++;
            else y1--;
            j++;
        }
        ans = min(ans, max(x1, y1));
        if (s[i] == '0') x1--;
        else y1++;
    }
    return ans;
}

方法3:动态规划

int minStringCost(string& s) {
    int n = s.size();
    vector<int> p(n + 1);
    for (int i = 0; i < n; ++i) {
        p[i + 1] = p[i] + (s[i] == '1');
    }
    if (p[n] == n || p[n] == 0) return 0;
    int res = min(p[n], n - p[n]);
    for (int i = 1; i <= n; ++i) {
        if (i >= p[n]) res = min(res, (i - p[i]) - (i - p[n] - p[i - p[n]]));
        else res = min(res, p[n] - p[i]);
    }
    return res;
}

只剩一个星号的最小步数

ecr128E, div2

题意：有一个2*n的方格, 包括星号 '*'和空白 .，保证至少有1个星号。

每一步星号可以移动到相邻的格子，如果移动后的新格子是*，则该格子的*被消灭，*不能走出方格。

求使得方格中有且仅有一个*的最少移动步数。

1 <= n <= 2e5

提示

最前面两列都是空白的和最后面两列都是空白的对答案没有贡献，可以删去。
假设最后剩的*在第j列，那么小于j列的*只会往右走，大于j列的*只会往左走。
最优解中，当前列只会保留一个*，因为如果有两个*，那么消灭掉一个*，只留一个*向右走会更优。
dp[i][0]: 最后处理的第i列，且*在第0行。
dp[i][1]: 最后处理的第i列，且*在第1行。

答案为 min(dp[n - 1][0], dp[n - 1][1])

int minMoveCost(vector<string>& s) {
    for (int i = 0; i < 2; ++i) {
        while (s[0].back() == '.' && s[1].back() == '.') {
            s[0].pop_back();s[1].pop_back();
        }
        reverse(s[0].begin(), s[0].end());
        reverse(s[1].begin(), s[1].end());
    }
    int n = s[0].size();
    vector<vector<int>> dp(n, vector<int>(2, 1e9));
    dp[0][0] = (s[1][0] == '*');
    dp[0][1] = (s[0][0] == '*');
    for (int i = 0; i + 1 < n; ++i) {
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + 1 + (s[1][i + 1] == '*'));
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + 2);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + (s[0][i + 1] == '*'));
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 2);
    }
    return min(dp[n - 1][0], dp[n - 1][1]);
}

区间最大值不小于区间和

cf795 div2 d

数组a，长度为n，如下不等式是否成立？ max(a[i],...,a[j]) >= a[i] + ... + a[j] 对任意的下标对i,j满足 1<==i<=j<=n。

1 <= n <= 2e5
-1e9 <= a[i] <= 1e9

分析

可以使用单调栈求出以i为最大值的区间，设为 l, l+1, …,i, i+1, … r.

则区间开始在[l,i]，结束在[i,r]的所有区间和都不大于a[i]。设左边区间和(不包括a[i])为x，右边区间和(不包括a[i])为y

则 x+y+a[i] <= a[i], 即 x + y <= 0, 对于不满足的下标对 x 和y 至少有一个大于0，设数组a的前缀和数组为 pref, 后缀和为suf. 则不满足条件时 max(suf[l], ..., suf[i-1]) > suf[i] 或者 max(pref[r+1], ..., pref[i+2]) > pref[i+1]

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

long long op(long long x, long long y) {return max(x, y);}
template <class T, T (*op)(T, T)>
class ST {
 public:
  int n;
  vector<vector<T>> mat;
 
  ST(const vector<T>& a) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = op(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
 
  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return op(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int n,m,x,y,k,q;
void solve(){
    cin>>n;
    vector<int> a(n);
    for(auto&x: a) cin>>x;
    
    vector<long long> pref(n + 1), suf(n + 1), left(n, -1), right(n, n);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i];
    for (int i = n - 1; i >= 0; --i) suf[i] = suf[i + 1] + a[i];
    stack<int> sk;
    for (int i = 0; i < n; ++i) {
        while(!sk.empty() && a[sk.top()] < a[i]) {
            right[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }
    sk = stack<int>();
    for (int i = n - 1; i >= 0; --i) {
        while (!sk.empty() && a[sk.top()] <= a[i]) {
            left[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }
    ST<long long,op> st1(pref), st2(suf);
    for(int i=0;i<n;++i){
        int l=left[i]+1,r=right[i]-1;
        long long x=-1e18,y=-1e18;
        if(i+2<=r+1) y=st1.get(i+2,r+1);
        if(l<=i-1) x=st2.get(l,i-1);
        if(pref[i+1]<y||suf[i]<x){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    cin >> T;
    for (int case_i = 1; case_i <= T; ++case_i) {
        solve();
    }
    return 0;
}

字典序最小的错位排列

cr798 1689B

给一个1-n的排列 p1,p2,…,pn，构造一个新的排列 q1,q2,…,qn, 使得 p1!=q1, p2!=q2, …, pn!=qn,且q的字典序最小。如果无解，返回空。

1 <= n <= 1000
进阶，如果 n <= 3e5, 怎么求？

分析

如果n=1，无解
贪心选择，对于前n-2个数字，每次选择剩余没有被使用的且不等于当前位置值的最小值.
对于后两个元素，设剩余的两个没有被选择的数字从小到大为a,b，如果a,b满足，则为a,b，否则b,a一定满足条件。

/*
a: 0-n-1排列
return : 0 - n - 1排列
*/
vector<int> minLexicographicallyPerm(vector<int> &nums) {
    int n = nums.size();
    if (n == 1) return {};
    vector<int> s(n), c(n);
    for (int i = 0; i < n - 2; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!s[j] && nums[i] != j) {
                s[j] = 1, c[i] = j;
                break;

            }
        }
    }
    int a = -1, b = -1; 
    for (int i =  0; i < n; ++i) if (!s[i]) {
        if (a == -1) a = i;
        else b = i;
    }
    if (a == nums[n - 2] || b  == nums[n - 1]) swap(a, b);
    c[n - 2] = a, c[n - 1] = b;
    return c;
}

进阶

O(n) 算法

vector<int> minLexicographicallyPerm1(vector<int> &a) {
    int n = a.size();
    if (n == 1) return {};
    vector<int> b(n);
    for (int i = 0; i < n; ++i) b[i] = i;

    for (int i = 0; i < n - 1; ++i) if (a[i] == b[i])
        swap(b[i], b[i + 1]);
    if (a[n - 1] == b[n - 1]) swap(b[n - 2], b[n - 1]);
    return b;
}

按位与排列

cr455 div2 f

对于整数n，找两个排列

排列p, 对于任意 i = 1, 2, …, n，p[i]!=i 且 p[i] & i == 0
排列q, 对于任意 i = 1, 2, …, n，q[i]!=i 且 q[i] & i != 0

1 <= n <= 1e5

void solvep(int n){ // 0
    if(n % 2 == 1){
        cout << "NO" << endl; return;
    }
    int ans[n+1];
    int cur = n;
    while(cur){
        int f = 1;
        while(f <= cur) f *= 2;
        f--;
        for(int i = cur; i > f-cur; i--){
            ans[i] = f-i;
            ans[f-i] = i;
        }
        cur = f-cur - 1;
    }
    cout << "YES" << endl;
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return;
}
void solveq(int n){ // nonzero
    if(n <= 5 || __builtin_popcount(n) == 1){
        cout << "NO" << endl; return;
    }
    int ans[n+1];
    ans[2] = 6; ans[6] = 2;
    ans[1] = 3; ans[3] = 1;
    vector<int> g[30];
    for(int j = 1; j <= n; j++){
        if(6 % j == 0) continue;
        for(int r = 0; r < 25; r++){
            if(j >= (1<<r) && j < (1 << (r+1))){
                g[r].push_back(j);
            }
        }
    }
    for(int r = 0; r < 25; r++){
        for(int i = 0; i < g[r].size(); i++){
            ans[g[r][i]] = g[r][(i+1) % g[r].size()];
        }
    }
    cout << "YES" << endl;
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return;    
}

划分两个集合

cr 805 div3 E

n个多米诺骨牌，(n是偶数),每个多米诺骨牌上写两个1-n的数，问能否将这些多米诺骨牌分成两份，使得每一份中都没有重复的数字。

2 <= n <= 2e5

分析

显然每份1-n中每个数恰好出现一次

并查集

对于每一张多米诺骨牌，就将正面与反面的数合并，这表示我们取了正面的数就一定会取反面的数。最后如果存在一个连通块中的点数是奇数，说明至少有一个数被重复选取了。

struct DSU {
  ...
};

// a[i]: 0-n-1, b[i]: 0-n-1
bool canDivide2set(vector<int> &a, vector<int> &b) {
    int n = a.size();
    vector<int> cnt(n);
    DSU dsu(n);
    for (int i = 0; i < n; ++i) {
        cnt[a[i]]++, cnt[b[i]]++;
        if (a[i] == b[i]) return 0;
        dsu.merge(a[i], b[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (dsu.size(i) % 2 == 1 || cnt[i] > 2) return 0;
    }
    return 1;
}

tourist 的并查集写法：

// a[i]: 0-n-1, b[i]: 0-n-1
bool canDivide2set(vector<int> &a, vector<int> &b) {
    int n = a.size();
    vector<int> c(n);
    DSU dsu(n * 2);
    for (int i = 0; i < n; ++i) {
        c[a[i]]++, c[b[i]]++;
        dsu.merge(a[i], b[i] + n);
        dsu.merge(a[i] + n, b[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (c[i] > 2 || dsu.same(i, i + n)) return 0;
    }
    return 1;
}

二分图 dfs

将1-n看成n个节点，每个多米诺是一条边，因为1-n每个数出现2次，图中有多个环，环长必须是偶数。

// a[i]: 0-n-1, b[i]: 0-n-1
bool canDivide2set(vector<int> &a, vector<int> &b) {
    int n = a.size();
    vector<vector<int>> g(n);
    vector<int> vis(n);
    bool ok = 0;
    for (int i = 0; i < n; ++i) {
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
        if (a[i] == b[i] || g[a[i]].size() > 2 || g[b[i]].size() > 2) return 0;
    }

    function<int(int)> dfs = [&](int u) {
        vis[u] = 1;
        for (auto &v: g[u]) {
            if (!vis[v]) return dfs(v) + 1;
        }
        return 1;
    };

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            if (dfs(i) % 2) return 0;
        }
    }
    return 1;
}

相等的multiset

cr805 div3F abc 254 Ex

两个长度为n的数组a,b, 一次操作，你可以b中一个元素乘以2或除以2，可以做任意次操作，能否使得a，b相等。

分析

首先如果a中某个元素是偶数，可以一直对其做除以2操作，直到a中为奇数，如果b可以和a中该奇数相等，则可以通过乘以2操作，使其和原始数相等。这样在b中只需做除以2操作。

然后从大到小，对a,b进行排序，每一次比较a、b中相应元素，如果相等，则将两个元素都删掉，如果不等，如果b中元素已经为1，则不可能变为a (后面元素也全变为1)，否则删掉b中元素，假如该元素的一半，最后判断b是否为空。

1 <= n <= 2e5
1 <= a[i], b[i] <= 1e9

bool isEquateMultisets(vector<int> &a, vector<int> &b) {
    priority_queue<int> q1, q2;
    for(auto &x: a) {
        while (x % 2 == 0) x /= 2;
        q1.push(x);
    }
    for (auto &x: b) {
        q2.push(x);
    }
    while (!q2.empty()) {
        if (q1.top() == q2.top()) {
            q1.pop(), q2.pop();
        } else {
            if (q2.top() == 1) return 0;
            q2.push(q2.top() / 2);
            q2.pop();
        }
    }
    return q2.empty();
}

方法2

将操作看作是二进制运算

将每一个数看作是二进制字符串，其中

除以2操作，删除B中string的最后一个字符
乘以2操作，删除A中string的结束为’0’的字符（和B中元素除以2等价）

使用 Trie

为字符串A,B构造一个Trie，每个操作可以认为将一个字符串变为其父节点，在trie树中，从叶节点到根节点，进行逐个匹配。

bool isEquateMultisets(vector<int> &a, vector<int> &b) {
    vector<vector<int>> trie(1, vector<int>(2, -1));
    vector<int> val(1, 0);
    for (int i = 0; i < 2 * n; ++i) {
        int x = (i < n ? b[i] : a[i - n]);
        int sign  = (i < n ? 1 : -1);
        while (x % 2 == 0) x /= 2;
        int bit = 30;
        while (!(x & (1 << bit))) bit -= 1;
        int t = 0;
        for (int j = bit; j >= 0; --j) {
            int d = (x >> j) & 1;
            if (trie[t][d] == -1) {
                trie[t][d] = (int) trie.size();
                trie.emplace_back(2, -1);
                val.push_back(0);
            }
            t = trie[t][d];
            val[t] += sign;
            if (val[t] < 0) return 0;
        }
    }
    return 1;
}

获得最多峰值的最小代价

cf 809c dic2

长度为n的数组，一个峰值指 a[i] > a[i-1] 且 a[i] > a[i+1] (a[i]不能为第一个或最后一个数), 可以给每个值加上任意数，代价为所加数的值，求使得数组峰值最多的最小代价。

3 <= n <= 2e5
1 <= a[i] <= 1e9

long long minCostMaxMountainValue(vector<int> &a) {
    int n = a.size();

    auto get = [&](int x) {
        long long  t = max(a[x - 1], a[x + 1]) + 1;
        return max(t - a[x], 0ll);
    };
    long long tot = 0, ans = 0;
    for (int i = 1; i < n - 1; i += 2) {
        tot += get(i);
    }
    ans = tot;
    if (n % 2 == 0) {
        for (int i = n - 2; i > 0; i -= 2) {
            tot -= get(i - 1);
            tot += get(i);
            ans = min(ans, tot);
        }
    }
    return ans;
}

最大最小子数组数目

cr 823div2 E

长度为n的数组a，求满足如下条件的子数组数目: 子数组的最小值整除最大值

1 <= n <= 2e5
1 <= a[i] <= 1e6

分析

维护lmx,rmx,lmn,rmn,左右第一个比当前元素大/小的数。

遍历数组，统计以第i个元素为最大值的子数组数目，对于第i个元素，遍历其所有因子，找到该因子左边离i最近的出现位置j，如果求以j为最小值的区间和以i为最大值的区间的交集长度。加入总子数组数目；同时找到该因子右边离i最近的出现位置j，同理求其数目。

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

const int MX = 1e6 + 5;
vector<int> divs[MX];

void solve() {
    int n, m;
    cin >> n;
    vector<int> a(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        m = max(a[i], m);
    }
    vector<vector<int>> pos(m + 1);
    vector<int> ind(m + 1);

    for (int i = 0; i < n; ++i) 
        pos[a[i]].push_back(i);

    vector<int> lmx(n, -1), rmx(n, n), lmn(n, -1), rmn(n, n);
    stack<int> sk;
    for (int i = 0; i < n; ++i) {
        while(!sk.empty() && a[sk.top()] < a[i]) {
            rmx[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }
    sk = stack<int>();
    for (int i = n - 1; i >= 0; --i) {
        while (!sk.empty() && a[sk.top()] <= a[i]) {
            lmx[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }
    sk = stack<int>();
    for (int i = 0; i < n; ++i) {
        while(!sk.empty() && a[sk.top()] > a[i]) {
            rmn[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }
    sk = stack<int>();
    for (int i = n - 1; i >= 0; --i) {
        while (!sk.empty() && a[sk.top()] > a[i]) {
            lmn[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }

    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        for (int x : divs[a[i]]) {
            if (ind[x] >= 1) {
                int j = pos[x][ind[x] - 1];
                if (j > lmx[i] && i < rmn[j]) {
                    ans += (j - max(lmx[i], lmn[j])) * 1ll * (min(rmx[i], rmn[j]) - i);
                }
            }

            if (ind[x] < pos[x].size()) {
                int j = pos[x][ind[x]];
                if (j < rmx[i] && lmn[j] < i) {
                    int t = ind[x] >= 1 ? pos[x][ind[x] - 1] : -1;
                    ans += (i - max({lmx[i], lmn[j], t})) * 1ll * (min(rmx[i], rmn[j]) - j); 
                }
            }
        }
        ind[a[i]]++;
    }
    cout << ans << "\n";

}

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

    for (int i = 1; i < MX; ++i) {
        for (int j = i; j < MX; j += i) {
            divs[j].push_back(i);
        }
    }
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

奇偶序列

cf 1370d

长度为n的数组a，s是a的一个子序列，s的代价定义为一下两者的最小值

s中所有奇数下标的最大值(下标从1开始)
s中所有偶数下标的最大值

求a中长度为k的代价最小的字序列。

2 <= k <= n <= 2e5
1 <= a[i] <= 1e9

分析

二分答案，check答案是否可行

int minCostSubSeq(vector<int> &a, int k) {
    int n = a.size();
    auto chk = [&](int x) {
        for (int d = 0; d < 2; ++d) {
            int len = 0;
            for (int i = 0; i < n; ++i) {
                if (len % 2 != d || a[i] <= x) {
                    len++;
                }
            }
            if (len >= k) return 1;
        }
        return 0;
    };

    int l = 1, r = 1e9, ans = l;

    while (l <= r) {
        int md = (l + r) / 2;
        if (chk(md)) {
            ans = md;
            r = md - 1;
        } else l = md + 1;
    }
    return ans;
}

取模最大值数对

cf485 d

长度为n的数组a，找到数对a[i],a[j], a[i]<=a[j], 且a[j]%a[i]最大。返回其最大值。

1 <= n <= 2e5
1 <= a[i] <= 1e6

分析

可以先排序，对于a[i] 的每个整数倍 k * a[i]，会在数组中小于k * a[i]的最大数处取的模a[i]的最大值，注意剪枝。

int maxModPair(vector<int> &a){
    int n = a.size(), ans = 0;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) {
        if (i > 0 && a[i] == a[i - 1]) continue;
        for (int j = 2 * a[i]; j <= a[n - 1] + a[i]; j += a[i]) {
            if (ans + 1 >= a[i]) break;
            int pos = lower_bound(a.begin(), a.end(), j) - a.begin() - 1;
            if (pos >= 0) {
                ans = max(ans, a[pos] % a[i]);
            }
        }
    }
    return ans;
}

区间最小值的最大值

cf547 b

长为n的数组a，定义f[x]为a中长为x的连续子数组的最小值的最大值，求f[1], f[2],…f[n]

1 <= n <= 2e5
1 <= a[i] <= 1e9

分析

对于每个 a[i], 找到左边和右边第一个小于a[i] 的数的下标。

显然，f[1]>=f[2]>=…>=f[n],

对于a[i],设其左右第一个比a[i]小的下标为l,r，len=r-l+1, 则 f[1],f[2],…f[len]都大于等于a[i],只需更新f[len]即可。最后从后往前取最大值。

vector<int> getMinMaxSubArray(vector<int> &a) {
    int n = a.size();
    vector<int> lmn(n, -1), rmn(n, n), ans(n);
    stack<int> sk;
    for (int i = 0; i < n; ++i) {
        while(!sk.empty() && a[sk.top()] > a[i]) {
            rmn[sk.top()] = i;
            sk.pop();
        }
        if (!sk.empty()) lmn[i] = sk.top();
        sk.push(i);
    }

    for (int i = 0; i < n; ++i) {
        int l = rmn[i] - lmn[i] - 1;
        ans[l - 1] = max(ans[l - 1], a[i]);
    }

    for (int i = n - 2; i >= 0; --i) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    return ans;
}

和的所有可能取值

cf687c

输入长为n的数组c, 和整数k，从c中选若干数，组成数组A，满足 sum(A)=k, 从A中再选若干数，组成数组B, 可以为空，计算sum(B)的所有可能取值，输出值得个数q，然后升序输出这q个数。

1 <= n,k <= 500
1 <= c[i] <= 500

分析

dp[i][j][k]: 前i个元素和为j，且存在一个子集和为k.

如果不使用第i个元素 dp[i][j][k] = dp[i - 1][j][k]
使用第i个元素组成和j，但不作为和为k的子集，dp[i][j][k] = dp[i][j-c[i]]][k]
使用第i个元素组成和j，同时作为和为k的子集，dp[i][j][k] = dp[i][j-c[i]]][k-c[i]]

实现时使用了滚动数组优化空间

int main() {    
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector f(k + 1, vector<int> (k + 1));
    f[0][0] = 1;
    auto g = f;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= k; ++j) {
            for (int l = 0; l <= k; ++l) {
                g[j][l] = f[j][l];
                if (j >= a[i]) g[j][l] |= f[j - a[i]][l];
                if (j >= a[i] && l >= a[i]) g[j][l] |= f[j - a[i]][l- a[i]];
            }
        }
        g.swap(f);
    }
    vector<int> res;
    for (int i = 0; i <= k; ++i) {
        if (f[k][i]) res.push_back(i);
    }
    cout << res.size() << '\n';
    for (int x : res) {
        cout << x << ' ';
    }

    return 0;
}

差值不超过k的子序列数量

cf 1462E2

给定n,m,k和长为n的数组a，求有多少个长为m的子序列b满足， max(b) - min(b) <= k. 模1e9+7

1 <= k <= n <= 2e5
1 <= m <= 100
1 <= a[i] <= n

atcoder

饲喂所有动物的最小代价

abc251 E

有n个动物，编号1到n。有n种喂动物组合：

使用 a1 元可以喂动物1和动物2
使用 a2 元可以喂动物2和动物3
…
使用 an 元可以喂动物n和动物1

求所有动物都得到饲喂所需要的最小代价。

2 <= n <= 2e5
1 <= ai <= 1e9

分析

考虑第n个，可以使用an喂，也可以使用a1喂。
如果使用an喂，则 a1可选，可不选
如果不使用an喂，则 a1必选，a2可选可不选。
s1[i] 表示前i个，且选第i个的最小代价，s2[i]表示前i个，且不选第i个的最小代价
选an时，s1[0] = a[0], s2[0] = 0;
不选an，选a1时，s1[1] = a[1], s2[1] = 0;

long long minCost(vector<int> &a) {
    vector<long long> s1(n), s2(n);
    long long ans = 1e18;
    s1[0] = a[0], s2[0] = 0; // 选第n个，则第1个可以选或不选
    for (int i = 1; i < n - 1; ++i) {
        s1[i] = min(s2[i - 1], s1[i - 1]) + a[i];
        s2[i] = s1[i - 1];
    }
    ans = min(s1[n - 2], s2[n - 2]) + a[n - 1];
    s1[1] = a[1], s2[1] = 0;
    for (int i = 2; i < n; ++i) {
        s1[i] = min(s2[i - 1], s1[i - 1]) + a[i];
        s2[i] = s1[i - 1];
    }
    ans = min(ans, min(s1[n - 1], s2[n - 1]) + a[0]);
    return ans;
}

前缀集合是否相等

abc250 E

有两个长度为n的数组a和b，有q个询问，第i个询问给出两个数x，y，判断a的前x个数与b的前y个数构成的集合是否相等。

1 <= n, q <= 2e5
1 <= ai, bi <= 1e9
1 <= xi, yi <= n

方法1:哈希

using ull = unsigned long long;
vector<int> prefixSetEqual(vector<int>& a, vector<int>& b, vector<vector<int>>& q) {
    int n = a.size(), m = q.size();
    vector<int> ans(m);
    mt19937_64 rng(random_device{}()); 
    set<int> st1, st2;
    map<int, ull> mp;
    for (auto &x: a) if (!mp.count(x)) mp[x] = rng();
    for (auto &x: b) if (!mp.count(x)) mp[x] = rng();
    vector<ull> s1(n+1), s2(n+1);
    for(int i = 0; i < n; ++i) {
        s1[i + 1] = s1[i];
        if (!st1.count(a[i])) s1[i + 1] += mp[a[i]];
        st1.insert(a[i]);
    }
    for(int i = 0; i < n; ++i) {
        s2[i + 1] = s2[i];
        if (!st2.count(b[i])) s2[i + 1] += mp[b[i]];
        st2.insert(b[i]);
    }
    for (int i = 0; i < m; ++i) {
        if (s1[q[i][0] + 1] == s2[q[i][1] + 1]) ans[i] = 1;
    }
    return ans;
}

方法2

对于 x = 1, 2, … n, 使得查询 (x,y) 为 true 的 y 如果存在，一定是一个特定区间[l, r]。
l[x], r[x] 表示使得(x,y)为true，的y的左边界和右边界。使用两个set维护，当前前缀a[i]和b[j]集合是否相等。
对于查询(x,y)，如果y在[l[x],r[x]]中，则为true，否则为false。

vector<int> prefixSetEqual(vector<int>& a, vector<int>& b, vector<vector<int>>& q) {
    int n = a.size(), m = q.size();
    vector<int> l(n, n), r(n, -1), ans(m);
    set<int> s1, s2;
    for (int i = 0, j = 0; i < n; ++i) {
        if (s1.count(a[i])) {
            l[i] = l[i - 1], r[i] = r[i - 1];
            continue;
        }
        s1.insert(a[i]);
        while (j < n && s1.size() != s2.size()) {
            if (!s1.count(b[j])) break;
            s2.insert(b[j++]);
        }
        if(s1.size() == s2.size()) {
            l[i] = j - 1;
            while (j < n && s2.count(b[j])) j++;
            r[i] = j - 1;
        }

    }
    for (int i = 0; i < m; ++i) {
        if (q[i][1] >= l[q[i][0]] && q[i][1] <= r[q[i][0]]) ans[i] = 1;
    }
    return ans;
}

最值为xy的数对数目

abc247 E

给定数组 a=[a1,…,an],和x,y. 求有多少对(l,r)满足如下条件

1 <= l <= r <= n
max(a[l..r]) = x, min(a[l..r]) = y
1 <= n <= 2e5
1 <= ai <= 2e5
1 <= y <= x <= 2e5

方法1:滑动窗口

long long countMinMaxPairs(vector<int> &a, int x, int y) {
    int n = a.size(), cx = -1, cy = -1, t = -1;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] > x || a[i] < y) {
            t = i, cx = cy = -1;
        }
        if (a[i] == x) cx = i;
        if (a[i] == y) cy = i;
        if (cx >= 0 && cy >= 0) ans += min(cx, cy) - t;
    }
    return ans;
}

方法2:容斥原理

代码借鉴自jiangly。

long long countMinMaxPairs(vector<int> &a, int x, int y) {
    int n = a.size();
    auto get = [&](int x, int y) {
        long long ans = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            if (a[i] > x || a[i] < y) j = i + 1;
            ans += i + 1 - j;
        }
        return ans;
    };
    return get(x, y) - get(x - 1, y) - get(x, y + 1) + get(x - 1, y + 1);
}

最短路径树

abc 252 E

n个点(编号1到n)m条边(编号1到m)的无向连通图，edge[i] = [ai,bi,ci],连接ai,bi,距离为ci，从中选择n-1条边，使图依然连通，设di表示节点1到节点i的距离，使 d2+d3+…+dn最小化。

2 <= n <= 2e5
n-1 <= m <= 2e5
1 <= ai < bi < n
1 <= ci <= 1e9

分析

设Di为原始图中节点1到节点i的最短路，显然di>=Di, 所以如果存在一种方案使得di=Di，那么这个方案一定是最优的，

实际上，这种方案是存在的，只需要保存从节点1到节点i的最短路径中的最后一条路径即可，这种选择方法可以使得di=Di。

这种选择称为最短路径树

类似题目，cf545E paths and Trees, acwing周赛2 p3

// n个节点(0-(n-1)，
// edges:边 (ai,bi,ci)， 0<=ai<bi<=n-1
// u:是起始节点。0 <= u <= n-1
// 如果有多种最短路径树，这里会取所选的n-1条边权和最小的那条。
vector<int> shortestPathTree(int n, vector<vector<int>> &edges, int u) {
    vector<vector<int>> g(n);
    vector<int> ans(n);
    for (int i = 0; i < edges.size(); ++i) {
        g[edges[i][0]].push_back(i);
        g[edges[i][1]].push_back(i);
    }
    vector<long long> dis(n, 1e18);
    vector<bool> vis(n); 
    priority_queue<pair<long long, int> > pq;
    dis[u] = 0;
    pq.push({0, u});
    while (pq.size()) {
        int t = pq.top().second; pq.pop();
        if (vis[t]) continue;
        vis[t] = true;
        for (auto &v : g[t]) {
            int x = edges[v][0] + edges[v][1] - t, cost = edges[v][2];
            if (dis[t] + cost < dis[x]) {
                dis[x] = dis[t] + cost;
                ans[x] = v;
                pq.push({-dis[x], x});
            } else if (dis[t] + cost == dis[x] && edges[ans[x]][2] > edges[v][2]) {
                ans[x] = v;
            } 
        }
    }
    return ans;
}

股票交易

abc250 G 同cf865 D

已知接下来n天的股票价格，每天你可以买进一只股票，卖出一只股票，或者什么也不做。n天后你所拥有的钱的最大值是多少。

模拟费用流(反悔贪心)

每一天，可以有两种操作

找到之前没操作的并且股票最便宜的一天，在那天买入，今天卖出
将之前的某一次操作反悔。比如今天是第c天，之前有一个操作：在第a 天买入第b 天卖出，将在第b天卖出这个操作反悔，不在第b天卖出，而是在第c天卖出，然后标记第b天没有被操作过。

仔细观察反悔操作

假如之前有一个操作：在第a天买入第b天卖出，那么它的贡献是fa-fb。
然后考虑反悔，那么我们需要将第b天的贡献减去，然后加上第c天的贡献，也就是加上 fc-fb

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

int main(){
  int n; cin >> n;
  vector<long long> a(n);
  for(auto &nx : a){cin >> nx;}
  long long res=0;
  priority_queue<long long,vector<long long>,greater<long long>> pq;
  pq.push(a[0]);
  for(int i = 1; i < n; i++){
    if(pq.top() < a[i]){
      res += (a[i]-pq.top());
      pq.pop();
      pq.push(a[i]);
    }
    pq.push(a[i]);
  }
  cout << res << '\n';
  return 0;
}

满足先序遍历序列的数量

N个节点的有根树，节点编号1-N，1是根节点，对树进行dfs，得到的结果为 p1,…pn, 遍历时，如果当前有多个子节点，先遍历编号最小的。

求有多少种有根树的先序遍历满足该结果序列。模998244353。

2 <= n <= 500
1 <= pi <= n
p1,…pn是1-n的排列，且p1 =1

分析

添加一个虚拟节点0.

dp[l][r] (2<=l<=r<=n+1) 表示:

有r-l+1个节点，0，Al,…Ar, 根节点是节点0，
0，Al, … Ar的先序结果与题目描述的一致的方案数

我们要求的是 dp[2][N+1]，

当l=r时，dp[l][r]=1
否则
- 如果A[l] 是 0的唯一子节点，则其他节点都是A[l]的子节点，方案数为dp[l+1][k]
- 如果0有其他子节点，假设下一个最小的节点为A[k],则A[l]子节点的方案数为dp[l+1][k] ,去掉A[l]及其子节点，有dp[k][r]种树的方案。所以可以使用区间dp。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int main() {
    int n; cin >> n;
    int a[500];
    long long dp[501][501];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int l = n; l >= 1; l--) {
        dp[l][l] = 1;
        for (int r = l + 1; r <= n; r++) {
            dp[l][r] = dp[l + 1][r];
            for (int k = l + 1; k < r; k++) {
                if (a[l] < a[k])dp[l][r] = (dp[l][r] + (dp[l + 1][k] * dp[k][r])) % MOD;
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

最多奖金数

abc261 D

仍一枚硬币n次，同时有个计数器，初始为0.

如果第i次为正面，计数器+1，同时获得x[i]奖金。
如果第i次为反面，计数器清零，无奖金。

另外还有m种连胜奖金，第i种，每当计数器为c[i]时，可以获得y[i]奖金。

求能获得的最多奖金数量。

1 <= m <= n <= 5000
1 <= x[i],y[i] <= 1e9
1 <= c[i] <= N
c[1],c[2],,,c[m] 互不相同

分析

dp[i][j]表示扔了前i次硬币，最终的计数器为j时获得的最大奖金，

如果j>0, dp[i+1][j]=dp[i][j-1]+x[i+1]+w[j]
如果j=0，说明第i+1次是反面，dp[i+1][0]=max(dp[i][j])

时间复杂度O(n^2)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> x(n + 1), w(n + 1);
    vector<vector<long long>> dp(n + 1, vector<long long> (n + 1, -1e18));
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) cin >> x[i];

    for (int i = 0, x, y; i < m; ++i) {
        cin >> x >> y;
        w[x] = y;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) 
            dp[i][j] = dp[i - 1][j - 1] + x[i] + w[j];
        dp[i][0] = 0;
        for (int j = 0; j < i; ++j)
            dp[i][0] = max(dp[i][0], dp[i - 1][j]);
    }

    cout << *max_element(dp[n].begin(), dp[n].end()) << "\n";
}

每次操作后的值

abc261 E

有个变量x和n种操作，第i种操作表示为(t[i], a[i])

如果 t = 1, 操作 x = x & a[i]
如果 t = 2, 操作 x = x | a[i]
如果 t = 3, 操作 x = x ^ a[i]

x 初始值为 c, 按顺序执行如下步骤：

执行操作1，输出x的结果, 执行操作1，2，输出x的结果 … 指定操作1,2,…,n 输出x的结果

1 <= N <= 2e5
1 <= t[i] <= 3
0 <= a[i] <= 2^30
0 <= c <= 2^30

方法1

每一位操作是独立的，可以按位考虑。

#include<bits/stdc++.h>
using namespace std;
#define bit(x,i) (((x)>>(i))&1)

int main() {
    int n, c, x, a, t; 
    cin >> n >> c;

    vector<int> ans(n);
    vector<array<int, 2>> op(n);

    for (int i = 0; i < n; ++i) 
        cin >> op[i][0] >> op[i][1];

    for (int k = 0; k < 30; ++k) {
        array<int, 2> func = {0, 1};
        int b = bit(c, k);
        for (int i = 0; i < n; ++i) {
            array<int, 2> f;
            int t = op[i][0], a = op[i][1], x = bit(a, k);
            if (t == 1) f = {0 & x, 1 & x};
            if (t == 2) f = {0 | x, 1 | x};
            if (t == 3) f = {0 ^ x, 1 ^ x};
            func = {f[func[0]], f[func[1]]};
            b = func[b];
            ans[i] |= b << k;
        }
    }
    
    for (int i = 0; i < n; ++i)
        cout << ans[i] << "\n";
}

方法2

#include<bits/stdc++.h>
using namespace std;
#define bit(x,i) (((x)>>(i))&1)

int main() {
    int n, x, s0 = 0, s1 = (1 << 30) - 1, m = s1;
    cin >> n >> x;
    for (int i = 0, t, a; i < n; ++i) {
        cin >> t >> a;
        if (t == 1) s1 &= a, s0 &= a;
        else if (t == 2) s1 |= a, s0 |= a;
        else s1 ^= a, s0 ^= a;
        x = (x & s1) | ((x ^ m) & s0);
        cout << x << "\n";
    }
}

每次操作后的mex

abc272 e

长度为n的数组a, 每次操作，对于 (1<=i<=n) 执行 a[i]=a[i]+i

给定长度为n的数组a,执行m次操作：求每次操作完后，数组的mex(不包含在a中的非负最小整数)

1 <= n,m <= 2e5
-1e9 <= a[i] <= 1e9

分析

对于一个长度为n的序列，其mex值一定在[0-N]之间。我们称可能影响到mex的值是重要的。

第一次操作，最多有n个，其值都在[0,N]之间，第二次操作，最多有 n/2 上取整个，递推下去，重要数量级为 nlog(n)

vector<int> addAndMex(vector<int> &a, int m) {
    int n = a.size();
    vector<vector<int>> f(m);
    for (int i = 0; i < n; ++i) {
        if (a[i] >= n) continue; //大于等于n的一定不会成为mex
        int l = (a[i] >= 0 ? 1 : (-a[i] + i) / (i + 1)); // 第几次操作后，会使a[i]>=n
        int r = min(m + 1, (n - a[i] + i) / (i + 1));
        for (int j = l; j < r; ++j)  
            f[j - 1].push_back(a[i] + (i + 1) * j);
    }
    vector<int> ans(m);
    for (int i = 0; i < m; ++i) {
        int k = f[i].size();
        vector<int> vis(k + 1);
        for (auto &x: f[i]) if (x < k) 
            vis[x] = true;
        while (vis[ans[i]]) ans[i]++;
    }
    return ans;
}

n次操作后的最大值

abc249 f

初始 x=0, 输入n,k, 以及n个操作，每个操作是如下两种之一

1 y 表示把x替换成y
2 y 表示 x += y

你可以跳过至多k次操作，求能获得的最大x。

1 <= n <= 2e5
0 <= k <= n
-1e9 <= y <= 1e9

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<array<int, 2>> ops(n + 1, {1, 0});
    for (int i = 1; i <= n; ++i) {
        cin >> ops[i][0] >> ops[i][1];
    }
    long long ans = -1e18, s = 0;
    priority_queue<int> q;

    for (int i = n; i >= 0 && k >= 0; --i) {
        if (ops[i][0] == 1) {
            ans = max(ans, s + ops[i][1]);
            k--;
        } else {
            if (ops[i][1] < 0) {
                q.push(ops[i][1]);
            } else s += ops[i][1];
        }
        while (q.size() > k) {
            s += q.top();
            q.pop();
        }
    }
    cout << ans << "\n";
}

dpcontest

正面多于反面的概率

dp contest I

有N个硬币，第i个硬币抛出去正面向上的概率为pi, 将N个硬币全部抛出，正面向上的硬币数所欲反面的概率。

1 <= N <= 2999，且N是个奇数
0 < pi < 1

分析

dp[i][j] 表示前i个硬币，出现j个正面向上的概率。

则对于第i个硬币

出现 0 个正面硬币的概率为 dp[i][j] = dp[i - 1][j] * (1.0 - p[i])
出现j(j>0)个正面硬币分两种情况
- 第i个是正面，概率为p[i],前i-1个出现j-1个正面。 dp[i][j] += dp[i - 1][j - 1] * p[i];
- 第i个是反面，前i-1个出现j个正面，dp[i][j] += dp[i - 1][j] * (1.0 - p[i]);

double calProb(vector<double>& p){
    int n = p.size();
    vector dp(n + 1, vector<double>(n + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j == 0) dp[i][j] = dp[i - 1][j] * (1.0 - p[i - 1]);
            else {
                dp[i][j] += dp[i - 1][j - 1] * p[i - 1];
                dp[i][j] += dp[i - 1][j] * (1.0 - p[i - 1]);
            }
        }
    }
    double ans = 0.0;
    for (int i = (n + 1) / 2; i <= n; ++i) 
        ans += dp[n][i];
    return ans;

}

有向图中最长路径

dp contest G

给一个有向无环图，求图中最长的路径，路径长度为边的数目。

分析

dfs + dp, dfs时先dfs 指向的节点，再把当前元素放入数组，保证每个点的子节点都在改点之前出现。 dp时，对于每个点连接的所有点，dp[v] = max(dp[v], dp[u] + 1)即可

int calLongestPath(vector<vector<int>> &g) {
    int n = g.size(), ans = 0;
    vector<int> vis(n), a, dp(n);

    function<void(int)> dfs = [&](int v){
        if(vis[v]) return;
        vis[v] = 1;
        for(int u : g[v]) dfs(u);
        a.push_back(v);
    };

    for (int i = 0; i < n; ++i) dfs(i);

    for(auto &v : a) for (auto &u : g[v]) 
        dp[v] = max(dp[v], dp[u] + 1), ans = max(ans, dp[v]);
    return ans;
}

吃完所有寿司的期望操作次数

dp contest J

n个盘子，每个盘子有ai (1 <= ai <= 3) 个寿司, 每次操作从1-n中随机选择一个盘子，如果选中的盘子中有寿司，吃掉其中一个，否则什么也不做。

求吃完所有寿司的期望操作次数是多少。

1 <= n <= 300

分析

dp[i][j][k] 表示1个寿司的盘子有i个，2个寿司的盘子有j个，3个寿司的盘子有k个的期望操作次数。

则对于 dp[i][j][k], 总共含有寿司的盘子为 t = i + j + k 个，最后一次操作选中t个盘子中的一个的期望次数为 n / t; 在这t个盘子中。

如果是i个盘子中的一个：dp[i][j][k] += dp[i - 1][j][k] * i / n
如果是j个盘子中的一个: dp[i][j][k] += dp[i + 1][j - 1][k] * j / n; 因为选中盘子上有2个寿司，吃掉一个后，j会-1，但i会+1，多了一个有1个寿司的盘子。
如果是k个盘子中的一个: dp[i][j][k] += dp[i][j + 1][k - 1] * k / n;

const int M = 305;
double dp[M][M][M];
void solve(){
    cin>>n;
    vector<int> a(3);
    for (int i = 0; i < n; ++i){
        cin>>x;
        a[--x]++;
    }
    dp[0][0][0] = 0.0;
    for (int k = 0; k <= a[2]; ++k) 
        for (int j = 0; j <= n; ++j) 
            for (int i = 0; i <= n; ++i) {
                if (i + j + k == 0) continue;
                dp[i][j][k] = 1.0;
                if (i) dp[i][j][k] += dp[i - 1][j][k] * i / n;
                if (j) dp[i][j][k] += dp[i + 1][j - 1][k] * j / n;
                if (k) dp[i][j][k] += dp[i][j + 1][k - 1] * k / n;
                dp[i][j][k] *= n * 1.0 / (i + j + k);
            }

    cout << dp[a[0]][a[1]][a[2]] << "\n";
}

石子游戏

dp contest K

数组a包含n个正整数，有一堆包含k个的石子，两人轮流进行如下操作。

每次选取a中的一个元素x，从石子中移除x个石子，采取最优策略条件下，先手是否必胜。

1 <= n <= 100
1 <= k <= 1e5
1 <= a1 < a2 < … < an <= k

分析

dp[i] 表示剩i个石子时，先手是否必胜，则对a中的元素j，如果i>=j 并且 dp[i-j]非必胜，由于是轮流操作，则i是必胜状态。

bool check(vector<int> &a, int k) {
    vector<bool> dp(k + 1);
    for (int i = 1; i <= k; ++i) 
        for (auto &j : a) 
            if (i >= j && !dp[i - j]) dp[i] = 1;
    return dp[k];
}

先手后手得分差

dp contest L

一个长度为n的数组，两个人轮流进行如下操作。

从数组的开头或结尾删掉一个元素，得分为删掉元素的值。

设先手得分为x，后手得分为y，先手最大化x-y，后手最小化x-y，最优策略下，求x-y的结果。

1 <= n <= 3000
1 <= ai <= 1e9

分析

设 dp[i][j] 是从i到j后手能取得的最优得分。对于区间i,j，要么选a[i]，或者a[j]，所以

dp[i][j] = max(a[i] - dp[i+1][j], a[j]-dp[i][j-1]);

long long calc(vector<int> &a){
    int n = a.size();
    vector dp(n, vector<long long>(n));
    for(int l = 1; l <= n; ++l) 
        for (int i = 0; i + l <= n; ++i) {
            int j = i + l - 1;
            if (l == 1) dp[i][j] = a[i];
            else dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1]);
        }
    return dp[0][n-1];
}

分糖果方案数

dp contest M

一个长度为n的数组，有k个糖果，将这k个糖果正好分给n个人，第i个人可以分0到ai个糖果，总共有多少种方案(mod 1e9 + 7)。

1 <= n <= 100
0 <= k <= 1e5
1 <= ai <= k

分析

dp[i][j] 表示将j个糖果分给前i个人的方案数，其中第i个人可以分0到a[i]个糖果，所以

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + … + dp[i-1][j-a[i]]

使用前缀和优化，时间复杂度为 O(NK)

int cal(vector<int> &a,int k){
    int n=sz(a), M = 1e9 + 7;
    vector dp(n + 1,vector<long long>(k + 1));
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        long long  s = 0;
        for (int j = 0; j <= k; ++j) {
            s += dp[i][j];
            if (j > a[i]) s -= dp[i][j - a[i] - 1];
            dp[i + 1][j] = (s % M + M) % M;

        }
    }
    return dp[n][k];
}

king-yyf

king-yyf

codeforces/atcoder 选题

Index

codeforces

二进制字符串的最小代价

只剩一个星号的最小步数

区间最大值不小于区间和

字典序最小的错位排列

按位与排列

划分两个集合

相等的multiset

获得最多峰值的最小代价

最大最小子数组数目

奇偶序列

取模最大值数对

区间最小值的最大值

和的所有可能取值

差值不超过k的子序列数量

atcoder

饲喂所有动物的最小代价

前缀集合是否相等

最值为xy的数对数目

最短路径树

股票交易

满足先序遍历序列的数量

最多奖金数

每次操作后的值

每次操作后的mex

n次操作后的最大值

dpcontest

正面多于反面的概率

有向图中最长路径

吃完所有寿司的期望操作次数

石子游戏

先手后手得分差

分糖果方案数