tea-5.27-5.31

茶5.27-5.31

Mon

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

选一个 a 的子序列，要求：

子序列是交替的（相邻元素一正一负）。
在满足 1 的前提下，子序列尽量长。
在满足 2 的前提下，子序列元素和尽量大。
输出元素和的最大值。

注：子序列不一定连续。

输入
4
5
1 2 3 -1 -2
4
-1 -2 -1 -3
10
-2 8 3 8 -4 -15 5 -2 -3 1
6
1 -1000000000 1 -1000000000 1 -1000000000
输出
2
-1
6
-2999999997

Sol:

首先，让我们通过包含由具有相同符号的数字组成的数组的包含段来提取最大值。例如，如果数组是 [1,1,2，−1，−5,2,1，−3]，则这些段是 [1,1,2]、[−1，−5]、[2,1] 和 [−3]。我们可以使用任何类似“双指针”的算法来做到这一点。这些段的数量是交替子序列的最大可能长度，因为我们只能从每个块中获取一个元素。当我们想最大化总和时，我们需要从每个块中获取最大元素。

Code:

void solve()
{
    int n;
    cin>>n;
    vi a(n);
    for (auto &it : a) cin >> it;
    ll sum = 0;
    auto sgn = [&](int x) {
        if (x > 0) return 1;
        else return -1;
    };
    for (int i = 0; i < n; i++) {
        int cur = a[i];
        int j = i;
        while (j < n && sgn(a[i]) == sgn(a[j])) {
            cur = max(cur, a[j]);
            j++;
        }
        sum += cur;
        i = j - 1;
    }
    cout << sum << endl;
}

Feb

https://codeforces.com/problemset/problem/608/B

输入长度均 ≤2e5 的字符串 s 和 t，只包含 ‘0’ 和 ‘1’。并且 t 的长度大于等于 s 的长度。

定义 D(a,b) = |a[0]-b[0]| + |a[1]-b[1]| + … + |a[n-1]-b[n-1]|。
例如 D(“0011”, “0110”) = |0-0| + |0-1| + |1-1| + |1-0| = 0 + 1 + 0 + 1 = 2。

设 s 的长度为 n，对于 t 的所有长为 n 的连续子串 t’，计算 D(s,t’)。
输出所有 D(s,t’) 的和。

输入
01
00111
输出 3
解释要计算的是 D(“01”, “00”) + D(“01”, “01”) + D(“01”, “11”) + D(“01”, “11”)

输入
0011
0110
输出 2

Sol:

s[0] 对答案的贡献是多少？

s[1] 对答案的贡献是多少？

…

s[n-1] 对答案的贡献是多少？

设 d = m - n + 1，其中 n 和 m 分别为 s 和 t 的长度。

对于 s[0] 来说，它会与 t[0],t[1],…,t[d-1] 计算 D 值。

也就是 t[0],t[1],…,t[d-1] 中的不等于 s[0] 的字符个数。

对于 s[1] 来说，它会与 t[1],t[2],…,t[d] 计算 D 值。

依此类推，问题变成一个长为 d 的定长滑窗。要统计的是窗口内的 ‘1’ 的个数（’0’ 的个数等于 d 减去 ‘1’ 的个数）。

Code:

void solve()
{
    string s,t;
    cin>>s>>t;
    int d = t.size() - s.size() + 1;
    int c1 = count(t.begin(), t.begin() + d - 1, '1');
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        c1 += t[i + d - 1] & 1;
        if (s[i] == '0') {
            ans += c1;
        } else {
            ans += d - c1;
        }
        c1 -= t[i] & 1;
    }
    cout<<ans<<endl;
}

Wed

Tracking Segments_881E

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤1e5。
对于每组数据：
一开始，有一个长为 n 的全 0 数组 a，下标从 1 开始。
输入 n m(1≤m≤n≤1e5) 以及 m 个非空连续子数组的左右端点 L R。
然后输入 q(1≤q≤n) 和 q 个操作，每个操作输入一个下标 p，表示把 a[p] 变成 1。保证所有 p 互不相同。

如果一个子数组中的 1 的个数比 0 多，则称这个子数组是优美的。
输入的 q 个操作，按照输入顺序一个一个地执行。
至少执行多少个操作，可以使 m 个子数组中有优美子数组？
如果执行完了也没有优美子数组，输出 -1。

Sol:

二分答案，执行前 mid 个操作，用前缀和计算子数组和。

如果 1 的个数比 0 多，也就是 1 的个数比子数组长度减去 1 的个数多，即子数组元素和 * 2 > 子数组长度，则说明子数组是优美的。

Code:

void solve()
{
    scanf("%d%d", &n, &m);
		for(int i = 1; i <= m; ++ i) {
			scanf("%d%d", &l[i], &r[i]);
		}
		scanf("%d", &q);
		for(int i = 1; i <= q; ++ i) {
			scanf("%d", &pos[i]);
		}
		int ql = 1, qr = q, ans = -1;
		while(ql <= qr) {
			int mid = (ql + qr) >> 1;
			for(int i = 1; i <= n; ++ i)
				sum[i] = 0;
			for(int i = 1; i <= mid; ++ i)
				++ sum[pos[i]];
			for(int i = 1; i <= n; ++ i)
				sum[i] += sum[i - 1];
			int f = 0;
			for(int i = 1; i <= m; ++ i) {
				if(sum[r[i]] - sum[l[i] - 1] >= (r[i] - l[i] + 1) / 2 + 1) {
					f = 1;
					break;
				}
			}
			if(f)
				ans = mid, qr = mid - 1;
			else
				ql = mid + 1;
		}
		printf("%d\n", ans);
}

Thu

Maximum Subarray_144A

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

你需要把 a 中恰好 k 个数增加 x，其余数减少 x。
该操作必须恰好执行一次。
输出操作后，a 的最大连续子数组和。子数组可以是空的，元素和为 0。

输入
4
4 1 2
2 -1 2 3
2 2 3
-1 2
3 0 5
3 2 4
6 2 -8
4 -1 9 -3 7 -8
输出
5
7
0
44

Sol:

O(n) 做法。

如果 x<0，那么可以把 x 变成 -x，同时 k n-k。下面的讨论满足>=0。

为方便计算，先把所有数都减去 x，于是操作变成把 k 个数增加 2x。

分类讨论：

如果子数组长度超过 k，那么子数组内有 k 个数可以增加 2x，总和增加 2kx。我们计算的是长度有下限的最大子数组和。用前缀和思考，s[right]-s[left] 最大，那么 s[left] 尽量小，且 right-left > k，所以枚举 right 的同时，要维护 s[0] 到 s[right-k-1] 的最小值。可以先看【题解】最大子数组和的前缀和做法
如果子数组长度不超过 k，那么子数组内所有数都可以增加 2x。我们计算的是长度有上限的最大子数组和，这可以用前缀和+单调队列解决。关于单调队列，可以看【视频】单调队列

总的来说，这题同时考察了最大子数组和的长度下限变体和长度上限变体，是一道不错的综合题目。

void solve()
{
    int n, k, x;
    cin >> n >> k >> x;
    if (x < 0) {
        x = -x;
        k = n - k;
    }
    int ans = 0, pre = 0, pre2 = 0, minS = 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pre += a[i] - x;
        if (i >= k) {
            ans = max(ans, pre - minS + k * x * 2);
            pre2 += a[i - k] - x;
            minS = min(minS, pre2);
        }
    }
    vector<int> sum(n + 1);
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + a[i] + x;
    }
    vector<int> q;
    q.push_back(0);
    for (int i = 1; i <= n; ++i) {
        if (q[0] < i - k) {
            q.erase(q.begin());
        }
        while (!q.empty() && sum[i] <= sum[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
        ans = max(ans, sum[i] - sum[q[0]]);
    }
    cout << ans << endl;
}

Fri

LIS of Sequence_277E

LIS相关知识例题

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

定义 LIS 为 a 的最长严格递增子序列。
对于每个 i：
如果 a[i] 不在任何 a 的 LIS 中，输出 1。
如果 a[i] 在 a 的一个 LIS，但不在所有 LIS 中，输出 2。
如果 a[i] 在 a 的所有 LIS 中，输出 3。
输出在同一行，不要加空格。

注意，a=[1,2,2,3] 有两个相同的 LIS [1,2,3]，其中 1 和 3 都在这两个 LIS 中，但 2 只在其中一个 LIS 不在另一个 LIS 中，所以输出 3223。

输入
1
4
输出 3

输入
4
1 3 2 5
输出 3223

输入
4
1 5 2 3
输出 3133

Sol:

计算 a[0] 到 a[i] 的，以 a[i] 结尾的 LIS 长度，记作 pre[i]。

计算 a[i] 到 a[n-1] 的，以 a[i] 开头的 LIS 长度，记作 suf[i]。

如果 pre[i] + suf[i] - 1 ≠ 整个数组的 LIS 长度，那么 a[i] 一定不在任何 LIS 中。（减一是因为 a[i] 算重复了）否则，a[i] 是否一定在所有 LIS 中呢？

例如 a=[1,2,2,3]，这里的两个 2 对应的 pre[i] 是一样的，a[2]=2 虽然在 LIS 中，但不在所有 LIS 中。

（在 pre[i] + suf[i] - 1 = 整个数组的 LIS 长度的前提下）统计 pre[i] 的出现次数，如果只出现一次，那么 a[i] 一定在所有 LIS 中，否则 a[i] 不在所有 LIS 中。详细证明

关于 LIS 的二分做法，见视频讲解

int lis, a[N], lst[N], dp[N], dp2[N], cnt[N], tag[N];
int binary_search(int x) {
    int l = 1, r = lis, mid, ans = lis + 1;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (lst[mid] >= x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        dp[i] = binary_search(a[i]);
        if (dp[i] > lis) 
            lst[++lis] = a[i];
        else
            lst[dp[i]] = a[i];
    }
    for (int i = 1; i <= n; i++) {
        dp2[i] = dp[i];
        a[i] = -a[i];
    }
    for (int i = n; i >= 1; --i) {
        dp[i] = binary_search(a[i]);
        if (dp[i] > lis)
            lst[++lis] = a[i];
        else
            lst[dp[i]] = a[i];
    }
    for (int i = 1; i <= n; ++i) {
		if (dp[i] + dp2[i] - 1 == lis)
			++cnt[dp[i]];
		else
			tag[i] = 1;
	}
	for (int i = 1; i <= n; ++i) {
		if (tag[i])
			continue;
		if (cnt[dp[i]] == 1)
			tag[i] = 3;
		else
			tag[i] = 2;
	}
	for (int i = 1; i <= n; ++i)
		cout << tag[i];
}

codeforces

#Algorithm #Data Structure #Dynamic Programming #Greedy Algorithm #Code Implementation #Subsequence #Prefix Sum #Binary Search #Segment Tree #Competitive Programming

tea-5.27-5.31

https://www.polarishaw.top/2024/05/31/tea-5-27-5-31/

作者

Polaris

发布于

2024年5月31日

许可协议

scene-question-2 上一篇

An Optimized Conflict-free Replicated Set 下一篇