茶6.24-6.28

Mon

https://codeforces.com/problemset/problem/1759/E

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

一开始你有一个数 sum，初始值为 h。
每次操作，你可以选择如下三种操作的其中一个：

删除一个小于sum的 a[i]，然后把 sum 增加 floor(a[i]/2)。
sum *= 2，该操作至多执行 2 次。
sum *= 3，该操作至多执行 1 次。

输出最多可以删除多少个数。

输入
8
4 1
2 1 8 9
3 3
6 2 60
4 5
5 1 100 5
3 2
38 6 3
1 1
12
4 6
12 12 36 100
4 1
2 1 1 15
3 5
15 1 13
输出
4
3
3
3
0
4
4
3

Sol：

枚举 2 和 3 的使用顺序，有三种情况：

2 2 *3

2 3 *2

3 2 *2

对于每种顺序，贪心从小到大遍历 a（所以需要把 a 排序），如果 a[i] >= 当前数字就使用乘法。

Code：

int f(vll a, ll sum, ll* f) {
    int now = 0;
    int i = 0;
    while(true) {
        if(now == a.size()) {
            break;
        }
        if (a[now] < sum) {
            sum += a[now++]/2;
        } else if (i < 3){
            sum *= f[i++];
        } else {
            break;
        }
    }
    return now;
}
void solve()
{
    ll n,sum;
    cin>>n>>sum;
    vll a(n);
    FOR(i, 0, n-1) cin >> a[i];
    sort(a);
    ll now = 0;
    ll f1[3] = {2,2,3};ll f2[3] = {2,3,2};ll f3[3] = {3,2,2};
    cout << max(f(a,sum,f1),max(f(a,sum,f2),f(a,sum,f3))) << endl;
}

Tue

You Are So Beautiful_905F

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

输出 a 有多少个非空连续子数组 b，满足 b 是 a 的唯一子序列（不存在其他的子序列等于 b）。

输入
6
1
1
2
1 1
3
1 2 1
4
2 3 2 1
5
4 5 4 5 4
10
1 7 7 2 3 4 3 2 1 100
输出
1
1
4
7
4
28

考察子数组最左边和最右边的元素。

条件一：子数组最左边的元素 a[L]，其左侧不能有等于 a[L] 的元素，否则子序列不唯一。

条件二：子数组最右边的元素 a[R]，其右侧不能有等于 a[R] 的元素，否则子序列不唯一。

结论：满足这两个条件，则子序列是唯一的。

证明：用反证法证明。

假设子序列不唯一，那么另一个子序列的不同下标一定位于 [L,R] 内部（如果位于 [L,R] 外面就破坏了条件一或条件二），但是这个范围内的所有下标我们都选了，不可能存在一个子序列没有而另一个子序列有的情况，矛盾，故原命题成立。

怎么计算子数组个数呢？前后缀分解。

处理出每个 a[i] 首次和最后一次出现的位置。（实际只需要处理最后一次）枚举 a[i] 作为左端点，那么 a[i] 必须是首次出现的元素，我们还需要知道 >=i 的且是最后一次出现的元素的个数，具体见代码。

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    mii r;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        r[a[i]]=i;
    }
    int ans = 0;
    map<int, bool> vis;
    int rs = r.size();
    for (int i = 0; i < n; i++) {
        if (!vis[a[i]]) {
            vis[a[i]] = true;
            ans += rs; 
        }
        if (r[a[i]] == i) {
            rs--;
        }
    }
    cout << ans << endl;
}

Wed

Kolya and Movie Theatre_894E

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

从 a 中选一个长度至多为 m 的子序列 b。
设 b 的最后一个数在 a 中的下标为 i，定义 f(b)=sum(b)-i*d。（下标从 1 开始）
你需要最大化 f(b)。如果 b 是空的，那么 f(b)=0。

注：子序列不一定连续。

输入
6
5 2 2
3 2 5 4 6
4 3 2
1 1 1 1
6 6 6
-82 45 1 -77 39 11
5 2 2
3 2 5 4 8
2 1 1
-1 2
6 3 2
-8 8 -2 -1 9 0
输出
2
0
60
3
0
7

Sol:

枚举最后一个数的下标 i=1,2,3,…,n，同时维护前 m 大的正数。

那么答案就是【堆中元素之和 - i*d】的最大值。

Code:

void solve()
{
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    set<pair<int, int> > s;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int cur = sum + a[i] - d * (i + 1);
        ans = max(ans, cur);
        if (a[i] > 0) {
            s.insert({a[i], i});
            sum += a[i];
            if (s.size() >= m) {
                // BUG(s.begin()->first);
                sum -= (s.begin()->first);
                s.erase(s.begin());
            }
        }
    }
    cout << ans << endl;
}

Thu

The Great Equalizer_894E

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5，m 之和 ≤2e5，q 之和 ≤2e5。
每组数据输入 n(2≤n≤2e5) m(1≤m≤2e5)，表示一个 n 点 m 边的无向图。节点编号从 1 开始。保证图中无自环和重边。
然后输入长为 n 的数组 h(1≤h[i]≤1e9)。每个节点有一座山，第 i 座山的高度为 h[i]。
然后输入 m 条边。
然后输入 q(1≤q≤2e5) 和 q 个询问，每个询问输入 a b e(0≤e≤1e9)。

从第 i 座山移动到和 i 相邻的第 j 座山，你的能量会减少 h[j]-h[i]。如果这个值是负数则你会增加能量。
只有在移动后能量 >= 0 的情况下才能从 i 移动到 j。
对于每个询问，回答：在你初始能量为 e 的情况下，能否从第 a 座山移动到第 b 座山？输出 YES 或 NO。注意节点编号从 1 开始。

样例太长，请在原题查看。

离线+并查集。

Sol：

根据题意，从 a 到 b，路径上的山的高度必须都 <= h[a] + e。

把询问按照 h[a]+e 从小到大排序，把 h 也从小到大排序（带上下标一起排序）。

双指针遍历询问和 h 数组，对于所有高度 <= h[a]+e 的山 x，我们将 x 及其高度 <= x 的邻居用并查集合并。

合并后，如果发现 a 和 b 被合并在一起，就说明可以从 a 到 b。

为了找到 x 的所有高度 <= x 的邻居，在读取 m 条边时，总是把 h 值大的点指向 h 值小的点。

Code:

struct Dsu {
    std::vector<int> f, siz;
    explicit Dsu(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
    int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};
void solve()
{
    int n, m, q;
    cin >> n >> m;
    vi h(n);
    FOR(i, 0, n-1) cin >> h[i];
    vector<pii> es(m);
    vector<array<int, 4> > events;
    for (auto &[u, v] : es) {
        cin >> u >> v;
        --u; --v;
        events.push_back({max(h[u], h[v]), -1, u, v});
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u, v, e;
        cin >> u >> v >> e;
        --u; --v;
        events.push_back({(h[u] + e), i, u, v});
    }
    sort(events);
    Dsu dsu(n);
    vi ans(q);
    for (auto [w, id, u, v] : events) {
        if (id >= 0 && id < q) {
            ans[id] = dsu.same(u, v);
        } else {
            dsu.merge(u, v);
        }
    }
    for (int i=0; i<q; i++) {
            cout << (ans[i]?"YES":"NO") << '\n';
        }
        cout << '\n';
}

Fri

Mice and Holes_edu19F

输入 n(1≤n≤5000) 和 m(1≤m≤5000)。
然后输入长为 n 的数组 a(-1e9≤a[i]≤1e9)，表示在数轴上有 n 个一样的小球，第 i 个小球的位置是 a[i]。
然后输入 m 行，每行两个数 pi(-1e9≤pi≤1e9) 和 ci(1≤ci≤5000)，表示有 m 个洞，第 i 个洞的位置是 pi，能容纳 ci 个小球。

把所有小球都移入洞中，移动距离之和的最小值是多少？
如果无法满足，输出 -1。

输入
4 5
6 2 8 9
3 6
2 1
3 6
4 7
4 7
输出 11

输入
7 2
10 20 30 40 50 45 35
-1000000000 10
1000000000 1
输出 7000000130

Sol:

划分型 DP + 单调队列优化。

没做过划分型 DP 的可以看看动态规划题单

不了解单调队列的可以看看【基础算法精讲 27】

首先有如下贪心结论：

把小球和洞按照位置从小到大排序，那么最左边的若干个小球（可能 0 个）进第一个洞，接下来的若干小球（可能 0 个）进第二个洞，依此类推。

于是问题变成，把 a 分成若干段，第 i 段的小球（不能超过 ci 个）进第 i 个洞，移动距离之和为 sum(abs(a[j] - pi) for j in 这一段)

按照划分型 DP 的套路，定义：

f[i] [j] = a[:j] 进前 i 个洞的距离和

注意这个定义 j=0 表示没有小球，j=1 表示第一个小球，j=n 表示所有小球。

考虑最后一个子数组的小球进第 i 个洞的距离和。

枚举最后一个子数组的左端点 L，从 f[i-1] [L] 转移到 f[i] [j]，考虑 a[L:j] 对最优解的影响，设 abs(a[j]-pi) 的前缀和数组为 s，那么有

f[i] [j] = min{ f[i-1] [L] + s[j] - s[L] } = min{ f[i-1] [L] - s[L] } + s[j]

其中 L 属于区间 [j-ci,j]。如果 L=j 表示没有小球移动到第 i 个洞。

由于上式随着 j 的变大，L 的最小值也在变大，所以是一个滑动窗口最小值问题，可以用单调队列优化。

单调队列保存 (f[i-1] [j] - s[j], j)，注意额外保存下标。由于计算的是最小值，右边遇到更小的可以把左边更大（或者相等）的弹出，所以是单调队列从左到右是严格递增的，队首就是转移来源的最小值。

即 f[i] [j] = 队首 + s[j]。如果队首的下标 < j - ci，那么弹出队首。

初始值 f[0] [0] = 0, f[0] [j] = inf (j >= 1)。

最后答案为 f[m] [n]。

代码实现时，由于队列中保存了 f[i-1] [.] 的信息，所以 f 数组的第一个维度可以去掉。

Code(学习一下):

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[5005][5005],a[5005],b[5005],c[5005];
pair <int,int> d[5005];
inline int D(int x,int y)
{
	return max(x,y)-min(x,y);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=m;i++)
		cin >> d[i].first >> d[i].second;
	sort(d+1,d+m+1);
	for(int i=1;i<=m;i++) b[i]=d[i].first,c[i]=d[i].second;
	for(int i=0;i<=m;i++)
		for(int j=0;j<=n;j++)
			dp[i][j]=1e18;
	dp[0][0]=0;
	for(int i=1;i<=m;i++)
	{
		int w[5005]={},qzh[5005]={};
		for(int j=1;j<=n;j++)
			qzh[j]=D(b[i],a[j])+qzh[j-1];
		for(int j=0;j<=n;j++) w[j]=dp[i-1][j]-qzh[j];
		int q[5005]={},head=1,tail=0;
		for(int j=0;j<=n;j++)
		{
			while(head<=tail&&w[q[tail]]>w[j]) --tail;
			while(head<=tail&&q[head]<j-c[i]) ++head;
			q[++tail]=j;
			dp[i][j]=qzh[j]+w[q[head]];
		}
	}
	if(dp[m][n]>8e17) dp[m][n]=-1;
	cout << dp[m][n];
	return 0;
}

codeforces

#Dynamic Programming #Greedy Algorithm #Subsequence #Prefix Sum #Binary Search #Codeforces #Sorting #Offline Queries #Union-Find #Monotonic Queue

茶6.24-6.28

https://www.polarishaw.top/2024/06/24/茶6.24-6.28/

作者

Polaris

发布于

2024年6月24日

许可协议

CMU15445-lecture7 上一篇

CMU15445-lecture6 下一篇