2024信奥赛C++提高组csp-s复赛真题及题解：染色-171主机测评

2024信奥赛C++提高组csp-s复赛真题及题解：染色

在这里插入图片描述

题目描述

给定一个长度为

$n$ 的正整数数组

$A$ ，其中所有数从左至右排成一排。

你需要将

$A$ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设

$C$ 为长度为

$n$ 的整数数组，对于

$A$ 中的每个数

A_i

$A_{i}$ （

≤

1 \\leq i \\leq n

$1 \leq i \leq n$ ）：

如果 $A_i Ai 左侧没有与其同色的数，则令 C i = 0 C_i = 0 Ci=0。$
否则，记其左侧与其最靠近的同色数为 $A_j Aj，若 A i = A j A_i = A_j Ai=Aj，则令 C i = A i C_i = A_i Ci=Ai，否则令 C i = 0 C_i = 0 Ci=0。$

你的最终得分为

$C$ 中所有整数的和，即

∑

\\sum \\limits_{i=1}^n C_i

$i = 1 \sum n C_{i}$ 。你需要最大化最终得分，请求出最终得分的最大值。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数

$T$ ，表示数据组数。

接下来包含

$T$ 组数据，每组数据的格式如下：

第一行包含一个正整数

$n$ ，表示数组长度。

第二行包含

$n$ 个正整数

…

A_1, A_2, \\dots, A_n

$A_{1}, A_{2}, \dots, A_{n}$ ，表示数组

$A$ 中的元素。

输出格式

对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。

输入输出样例 1

输入 1

3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4

输出 1

1
0
8

说明/提示

【样例 1 解释】

对于第一组数据，以下为三种可能的染色方案：

将

A_1, A_2 A1​,A2​ 染成红色，将 A 3 A_3 A3​ 染成蓝色，其得分计算方式如下：

对于 $A_1 A1，由于其左侧没有红色的数，所以 C 1 = 0 C_1 = 0 C1=0。$
对于 $A_2 A2，其左侧与其最靠近的红色数为 A 1 A_1 A1。由于 A 1 ≠ A 2 A_1 \\neq A_2 A1=A2，所以 C 2 = 0 C_2 = 0 C2=0。$
对于 $A_3 A3，由于其左侧没有蓝色的数，所以 C 3 = 0 C_3 = 0 C3=0。该方案最终得分为 C 1 + C 2 + C 3 = 0 C_1 + C_2 + C_3 = 0 C1+C2+C3=0。$

将

A_1, A_2, A_3 A1​,A2​,A3​ 全部染成红色，其得分计算方式如下：

对于 $A_1 A1，由于其左侧没有红色的数，所以 C 1 = 0 C_1 = 0 C1=0。$
对于 $A_2 A2，其左侧与其最靠近的红色数为 A 1 A_1 A1。由于 A 1 ≠ A 2 A_1 \\neq A_2 A1=A2，所以 C 2 = 0 C_2 = 0 C2=0。$
对于 $A_3 A3，其左侧与其最靠近的红色数为 A 2 A_2 A2。由于 A 2 ≠ A 3 A_2 \\neq A_3 A2=A3，所以 C 3 = 0 C_3 = 0 C3=0。该方案最终得分为 C 1 + C 2 + C 3 = 0 C_1 + C_2 + C_3 = 0 C1+C2+C3=0。$

将

A_1, A_3 A1​,A3​ 染成红色，将 A 2 A_2 A2​ 染成蓝色，其得分计算方式如下：

对于 $A_1 A1，由于其左侧没有红色的数，所以 C 1 = 0 C_1 = 0 C1=0。$
对于 $A_2 A2，由于其左侧没有蓝色的数，所以 C 2 = 0 C_2 = 0 C2=0。$
对于 $A_3 A3，其左侧与其最靠近的红色数为 A 1 A_1 A1。由于 A 1 = A 3 A_1 = A_3 A1=A3，所以 C 3 = A 3 = 1 C_3 = A_3 = 1 C3=A3=1。该方案最终得分为 C 1 + C 2 + C 3 = 1 C_1 + C_2 + C_3 = 1 C1+C2+C3=1。$

可以证明，没有染色方案使得最终得分大于

$1$ 。

对于第二组数据，可以证明，任何染色方案的最终得分都是

$0$ 。

对于第三组数据，一种最优的染色方案为将

A_1, A_2, A_4, A_5, A_7

$A_{1}, A_{2}, A_{4}, A_{5}, A_{7}$ 染为红色，将

A_3, A_6, A_8

$A_{3}, A_{6}, A_{8}$ 染为蓝色，其对应

[

]

C = [0, 0, 0, 5, 0, 2, 1, 0]

$C = [0, 0, 0, 5, 0, 2, 1, 0]$ ，最终得分为

$8$ 。

【数据范围】

对于所有测试数据，保证：

≤

1\\leq T\\leq 10

$1 \leq T \leq 10$ ，

≤

2\\leq n\\leq 2\\times 10^5

$2 \leq n \leq 2 \times 1 0^{5}$ ，

≤

1\\leq A_i\\leq 10^6

$1 \leq A_{i} \leq 1 0^{6}$ 。

测试点

A_i Ai​

$1\\sim 4 1∼4$	$\\leq 15 ≤15$	$\\leq 15 ≤15$
$5\\sim 7 5∼7$	$\\leq 10^2 ≤102$	$\\leq 10^2 ≤102$
$8\\sim 10 8∼10$	$\\leq 2000 ≤2000$	$\\leq 2000 ≤2000$
	$\\leq 2\\times 10^4 ≤2×104$	$\\leq 10^6 ≤106$
$13\\sim 15 13∼15$	$\\leq 2\\times 10^5 ≤2×105$	$\\leq 10 ≤10$
$16\\sim 20 16∼20$	^	$\\leq 10^6 ≤106$

思路分析

1. 问题转化

将原问题转化为：将序列分为两个子序列（红和蓝），在每个子序列中，若相邻两个数字相等，则得分为后一个数字的值。
相邻相等的数字可以直接处理，因为无论怎么染色，只要相邻相同就能得分。
对于不相邻的相同数字，需要在它们之间形成一个"区间"，选择一个区间意味着将这两个数字染成同色，中间部分染成另一种颜色。

2. 区间构建

lst数组记录每个数字最后出现的位置。
遍历数组：
- 如果当前数字a[i]之前出现过（lst[a[i]]存在）：
  - 如果上次出现位置是i-1（相邻相同），直接将a[i]加到答案中。
  - 否则，构建一个区间：左端点lst[a[i]]+1，右端点i-1，权值为a[i]。
- 更新lst[a[i]] = i。

3. 区间选择DP

将所有区间按照右端点排序（这里遍历时已经按右端点递增顺序处理）。
dp[i]表示前i个位置能获得的最大额外分数。
状态转移：
- 不选以i为右端点的区间：dp[i] = dp[i-1]
- 如果存在以i为右端点的区间（l[i] != 0）：dp[i] = max(dp[i], dp[l[i]-1] + w[i])

4. 最终答案

最终答案为相邻相同数字的得分ans加上区间选择的最大得分dp[n]。

代码实现

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

const int N = 2e5 + 10; // 数组最大长度
const int M = 1e6 + 10; // 值域上限

int T, n;
int a[N]; // 存储序列
long long dp[N]; // dp数组
int l[N]; // 区间左端点，l[i]表示以i为右端点的区间左端点
long long w[N]; // 区间权值
int lst[M]; // 记录每个数字最后出现的位置

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T—) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
long long ans = 0;
// 初始化l和w为0
memset(l, 0, sizeof(int) * (n + 5));
memset(w, 0, sizeof(long long) * (n + 5));

// 第一遍遍历，处理相邻相同和构建区间
// 对于每个位置i，如果a[i]之前出现过：
// 1. 如果上次出现位置是i-1（相邻相同），直接加到答案
// 2. 否则构建一个区间：左端点为上次出现位置+1，右端点为i-1，权值为a[i]
for (int i = 1; i <= n; i++) {
if (lst[a[i]]) { // 如果a[i]之前出现过
if (lst[a[i]] == i – 1) { // 相邻相同
ans += a[i];
} else { // 非相邻，构建区间
l[i – 1] = lst[a[i]] + 1; // 区间右端点为i-1，左端点为上次出现位置+1
w[i – 1] = a[i]; // 权值为a[i]
}
}
lst[a[i]] = i; // 更新最后出现位置
}

// 第二遍遍历，DP选择区间
// dp[i]表示前i个位置能够获得的最大额外分数（不包括已经加的相邻相同分数）
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i – 1]; // 不选以i为右端点的区间
if (l[i]) { // 如果存在以i为右端点的区间
dp[i] = max(dp[i], dp[l[i] – 1] + w[i]);
}
}
ans += dp[n]; // 加上区间选择的最大权值和
cout << ans << '\\n';

// 清空lst数组中出现过的数字，避免影响下一组数据
for (int i = 1; i <= n; i++) {
lst[a[i]] = 0;
}
}
return 0;
}

功能分析

输入处理

处理多组测试数据，每组包含数组长度n和数组元素a[1..n]。

主要逻辑

相邻相同处理：直接累加到答案，这些得分是确定的。

区间构建：为不相邻的相同数字构建可选择的区间。

区间选择DP：选择一些不相交的区间，最大化得分。

复杂度分析

时间复杂度：O(n)，每个位置处理一次，DP过程也是O(n)。
空间复杂度：O(n + M)，M为值域大小。

注意事项

需要清空lst数组中出现过的数字，避免影响下一组数据。
区间构建时，右端点为i-1，左端点为上次出现位置+1。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

在这里插入图片描述

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

在这里插入图片描述

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

在这里插入图片描述 GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转在这里插入图片描述

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}

2024信奥赛C++提高组csp-s复赛真题及题解：染色