茶6.3-6.7

Mon

输入 T(≤1e3) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5) k(1≤k≤1e9) 和长为 n 的数组 a(1≤a[i]≤1e4)，长为 n 的数组 h(1≤h[i]≤1e9)。

选一个子区间 [L,R]，对于 [L,R-1] 内的 i，满足 h[i] 是 h[i+1] 的倍数，且 a[L] + a[L+1] + … + a[R] 不超过 k。
输出子区间长度 R-L+1 的最大值。
如果没有这样的子区间，输出 0。

输入
5
5 12
3 2 4 1 8
4 4 2 4 1
4 8
5 4 1 2
6 2 3 1
3 12
7 9 10
2 2 4
1 10
11
1
7 10
2 6 3 1 5 10 6
72 24 24 12 4 4 2
输出
3
2
1
0
3

Sol:

分组循环+不定长滑窗。

分组循环求满足 h[i] 能被 h[i+1] 整除的组。

每组内用滑窗求元素和不超过 k 的最长子数组。分组循环

Code:

void solve()
{
    int n, k;
    cin >> n >> k;
    vi a(n),b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    int ans = 0;
    for(int i = 0; i < n;) {
        int st = i;
        for(i++; i < n && b[i - 1] % b[i] == 0; i++) {
        }
        //cout << "st:"<< st <<" i :"<< i << endl;
        vi c(a.begin() + st, a.begin() + i);
        int l = 0, s = 0;
        for (int r = 0; r < c.size(); r++) {
            s += c[r];
            while (s > k) {
                s -= c[l];
                l++;
            }
            ans = max(ans, r - l + 1);
        }
    }
    cout << ans << endl;
}

Tue

Liebig’s Barrels_985C

输入 n k(1≤n,k≤1e5 且 1≤nk≤1e5) L(0≤L≤1e9) 和长为 nk 的数组 a(1≤a[i]≤1e9)，表示 n*k 条木板的长度。

你要制作 n 个木桶，每个木桶需要 k 条木板。
你可以使用任意 k 条木板来组装一个木桶，每条木板必须恰好属于一个木桶。
一个木桶的体积，等于其最短木板的长度。

要求：任意一对木桶的体积差都不能超过 L。
输出所有木桶体积和的最大值。
如果无法满足，输出 0。

输入
4 2 1
2 2 1 2 3 2 2 3
输出 7

输入
2 1 0
10 10
输出 20

输入
1 2 1
5 2
输出 2

输入
3 2 1
1 2 3 4 5 6
输出 0

Sol:

贪心，先将木板排序，最小的木桶肯定是a[0]，那么我们最多能选到长度为a[0]+l的木板。如果数量不足n个，则无法满足，若是多余n个，则可以让小的木桶带几个小的木板，以增加最终体积的最大值。

Code:

void solve()
{
    int n,k,l;
    cin>>n>>k>>l;
    vi a(n*k);
    for(int i = 0;i < n*k;i++) cin>>a[i];
    sort(a);
    int rg = int(upper_bound(a.begin(), a.end(), a[0] + l) - a.begin());
    if (rg < n) {
        cout << "0" << endl;
        return;
    }
    int u = 0;
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += a[u++];
        for(int j = 0;j < k - 1; j++) {
            if (rg - u > n - i - 1) {
                u++;
            } else {
                break;
            }
        }
    }
    cout << ans << endl;
}

Wed

Alarm Clock_451D

输入 n(1≤n≤2e5) m(1≤m≤1e6) k(1≤k≤n) 和长为 n 的数组 a(1≤a[i]≤1e6)。

数轴上有 n 个点，要求任意长为 m-1 的闭区间不能包含 >= k 个点。
问：至少要去掉多少个点？

注：闭区间 [L,R] 的长度为 R-L。

输入
3 3 2
3 5 1
输出 1

输入
5 10 3
12 8 18 25 1
输出 0

输入
7 7 2
7 3 4 1 6 5 2
输出 6

输入
2 2 2
1 3
输出 0

Sol:

首先，我们需要按照时间递增的顺序对所有闹钟进行排序。我们还将使用 queue 来存储闹钟时间。

我们将从第一个警报开始迭代。设当前闹钟时间等于x。在 set 不为空并且第一个集合元素小于 x - m + 1 之前，我们应该删除第一个集合元素。此后，只有时间不早于相对 x 的 m - 1 分钟的警报才会被设置。如果之后集合大小小于 k - 1，我们应该在集合中插入 x （我们不会关闭此警报）。在另一种情况下，我们应该关闭此警报，因此我们增加一个答案，并且不在集合中插入 x。

Code:

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vi a(n);
    FOR(i, 0, n-1) cin >> a[i];
    sort(a);
    int ans = 0;
    queue<int> q;
    FOR(i, 0, n-1) {
        int now = a[i];
        while (!q.empty() && q.front() < now - m + 1) {
            q.pop();
        }
        if (q.size() >= k-1) {
            ans++;
        } else {
            q.push(now);
        }
    }
    cout << ans << endl;
}

Thu

Choosing Balls_162C

输入 n(1≤n≤1e5) q(1≤q≤500) 和长为 n 的数组 v(-1e5≤v[i]≤1e5)，长为 n 的数组 c(1≤c[i]≤n)。
有 n 个球排成一排，第 i 个球的价值为 v[i]，颜色为 c[i]。

然后输入 q 个询问，每个询问输入 a 和 b，范围 [-1e5,1e5]。
对每个询问，计算：
从这一排球中，选出一个子序列，子序列的价值和为：

如果球不在序列开头，且球的颜色与前一个球的颜色相同，则加上球的值 * a。
否则，加上球的值 * b。
输出子序列的价值和的最大值。
子序列可以是空的，此时价值和为 0。

注：子序列不一定连续。

输入
6 3
1 -2 3 4 0 -1
1 2 1 2 1 1
5 1
-2 1
1 0
输出
20
9
4

输入
4 1
-3 6 -1 2
1 2 3 1
1 -1
输出
5

Sol:

每个询问跑一个 O(n) 的子序列 DP。

提示：想一想，如果只有两种颜色，要如何 DP？

遍历到第 i 个球时，我们需要维护以颜色 c 结尾的子序列的最大价值和，定义为 f[c]，初始全为 -inf。

对于每个球，有四种决策：

不选：f[c] 不变。
选，且和前一个球颜色一样：f[c] += v*a。
选，且和前一个球颜色不一样：我们需要知道颜色不等于 c 的最大 f，记作 f[mxC]。具体分析见下。
选，作为子序列第一个数：f[c] = v*b。

对于第三个决策，我们需要维护 f 的最大值 mx1、最大值对应的颜色 mxC，以及 f 的颜色不等于 mxC 的最大值 mx2。如果 c != mxC，那么 f[c] = mx1 + v b，否则 f[c] = mx2 + v b。最后答案为 mx1。

Code:

void solve()
{
    int n, q, a, b, mx;
    cin >> n >> q;
    vector<pii> ps(n);
    for (int i = 0; i < n; i++) {
        cin >> ps[i].first;
    }
    for (int i = 0; i < n; i++) {
        cin >> ps[i].second;
    }
    vi f(n + 1, 0);
    for (int i = 0; i < q; i++) {
        cin >> a >> b;
        fill(all(f), -1e18);
        int mx1 = 0, mx2 = 0, mxC = 0;
        for (int j = 0; j < n; j++) {
            int c = ps[j].second;
            if (c != mxC) {
                mx = mx1;
            } else {
                mx = mx2;
            }
            f[c] = max(f[c] + max(ps[j].first * a, 0), mx + ps[j].first * b);
            if (f[c] > mx1) {
                if (c != mxC) {
                    mx2 = mx1;
                    mxC = c;
                }
                mx1 = f[c];
            } else if (c != mxC && f[c] > mx2) {
                mx2 = f[c];
            }
        }
        cout << mx1 << endl;
    }
}

Fri

https://codeforces.com/problemset/problem/650/D

输入 n(1≤n≤4e5) m(1≤m≤4e5) 和长为 n 的数组 a(1≤a[i]≤1e9)，数组下标从 1 开始。
然后输入 m 个询问，每个询问输入两个数 i(1≤i≤n) 和 b(1≤b≤1e9)。

对于每个询问，输出把 a[i] 替换成 b 后，a 的最长严格递增子序列（LIS）的长度。
注意每个询问之间彼此独立，比如第一个询问把 a[1] 替换成 6，那么对于第二个询问，a[1] 还是原来的值。

输入
4 4
1 2 3 4
1 1
1 4
4 3
4 5
输出
4
3
3
4

输入
4 2
1 3 2 6
3 5
2 4
输出
4
3

Sol：

上周五的 CF486E，需要用到这题的结论。

修改后的 LIS，有两种情况：

LIS 不包含修改后的 a[i]，那么计算的就是原数组去掉 a[i] 后的 LIS 长度。
LIS 包含修改后的 a[i]。这两种情况取 max 即为答案。

第一种情况的计算方法：

设原数组的 LIS 长度为 k。

用上周五（CF486E）的结论，如果原数组的 a[i] 在所有 LIS 中，则去掉 a[i] 后，LIS 长度缩小，即 k-1；否则 LIS 长度不变，仍然为 k。

注意，为了判断这件事，需要正着计算一遍所有前缀的 LIS 长度，再反着计算所有后缀的 LIS 长度。

第二种情况的计算方法：

（先把询问离线，按照修改的下标分组）

上面说到，我们需要计算所有前缀/后缀的 LIS 长度，这用的是二分算法，会用到一个辅助数组 g，其中 g[i] 等于长为 i 的上升子序列的末尾元素的最小值。

正序遍历到 a[i] 时，先对所有在 i 处的询问，在 g 数组上二分查找 b，算出 LIS 中小于 b 的元素个数，加到答案中，然后答案再加一（把 b 算进去）。

倒序遍历到 a[i] 时，先对所有在 i 处的询问，在 g 数组上二分查找 b，算出 LIS 中大于 b 的元素个数，加到答案中。这样我们就得到了包含 a[i]=b 的 LIS 长度。

Code:

void solve()
{
    int n, m;
    cin >> n >> m;
    vi a(n);
    FOR(i, 0, n-1) cin >> a[i];
    vector<vector<pair<int, int> > > qs(n);
    for (int i = 0; i < m; i++) {
        int j, v;
        cin >> j >> v;
        qs[j-1].push_back({i, v});
    }
    vector<int> ans(m);
    vector<int> pre(n);
    vector<int> g;
    for (int i = 0; i < n; i++) {
        for (auto p : qs[i]) {
            ans[p.first] = lower_bound(g.begin(), g.end(), p.second) - g.begin() + 1;
        }
        int p = lower_bound(g.begin(), g.end(), a[i]) - g.begin();
        if (p < g.size()) {
            g[p] = a[i];
        } else {
            g.push_back(a[i]);
        }
        pre[i] = p + 1;
    }
    vector<int> suf(n);
    g.clear();
    for (int i = n - 1; i >= 0; i--) {
        for (auto p : qs[i]) {
            ans[p.first] += lower_bound(g.begin(), g.end(), -p.second) - g.begin();
        }
        int v = -a[i];
        int p = lower_bound(g.begin(), g.end(), v) - g.begin();
        if (p < g.size()) {
            g[p] = v;
        } else {
            g.push_back(v);
        }
        suf[i] = p + 1;
    }
    int lis = g.size();
    vector<int> cnt(n+1);
    for (int i = 0; i < n; i++) {
        if (pre[i] + suf[i] - 1 == lis) {
            cnt[pre[i]]++;
        }
    }
    for (int i = 0; i < n; i++) {
        int k = lis;
        if (pre[i] + suf[i] - 1 == lis && cnt[pre[i]] == 1) {
            k--;
        }
        for (auto p : qs[i]) {
            ans[p.first] = max(ans[p.first], k);
        }
    }
    for (int v : ans) {
        cout << v << endl;
    }
}

codeforces

#Dynamic Programming #Subsequence #Binary Search #Sorting #Offline Queries #Sliding Window #Subarray Sum #Greedy #Array Manipulation #Queue #Interval Problem #Longest Increasing Subsequence (LIS) #Data Structures

茶6.3-6.7

https://www.polarishaw.top/2024/06/07/茶6.3-6.7/

作者

Polaris

发布于

2024年6月7日

许可协议

CMU15445-lecture3 上一篇

CMU15445-lecture2 下一篇