2020年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第1题）
第2题
（最优子序列）取 m=16，给出长度为 n的整数序列
a
1
,
a
2
,
…
,
a
n
(
0
≤
a
i
<
2
m
)
a_1,a_2,…,a_n(0≤a_i<2^m)
a1,a2,…,an(0≤ai<2m)。对于一个二进制数 x，定义其分值 w(x)为 x+popcnt(x)，其中 popcnt(x) 表示 x二进制表示中 1的个数。对于一个子序列
b
1
,
b
2
,
…
,
b
k
b_1,b_2,…,b_k
b1,b2,…,bk，定义其子序列分值 S为
w
(
b
1
⊕
b
2
)
+
w
(
b
2
⊕
b
3
)
+
w
(
b
3
⊕
b
4
)
+
⋯
+
w
(
b
k
−
1
⊕
b
k
)
w(b_1⊕b_2)+w(b_2⊕b_3)+w(b_3⊕b_4)+⋯+w(b_{k−1}⊕b_k)
w(b1⊕b2)+w(b2⊕b3)+w(b3⊕b4)+⋯+w(bk−1⊕bk)。其中 ⊕表示按位异或。对于空子序列，规定其子序列分值为 0求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数 n(1≤n≤40000)接下来一行包含 nn 个整数
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1,a2,…,an。
提示：考虑优化朴素的动态规划算法，将前
m
2
\\frac{m}{2}
2m位和后
m
2
\\frac{m}{2}
2m位分开计算。
Max[x][y] 表示当前的子序列下一个位置的高 8位是 x、最后一个位置的低 8位是 y 时的最大价值。
试补全程序。
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) – 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x)
{
int s = x;
while(x)
{
①;
s++;
}
return s;
}
void to_max(LL &x, LL y)
{
if(x < y)
x = y;
}
int main()
{
int n;
LL ans = 0;
cin >> n;
for(int x = 0; x <= MS; x++)
for(int y = 0; y <= MS; y++)
Max[x][y] = –INF;
for(int i = 1; i <= n ; i++)
{
LL a;
cin >> a;
int x = ② , y = a & MS;
LL v = ③;
for(int z = 0; z < = MS; z++)
to_max(v, ④);
for(int z = 0; z < = MS; z++)
⑤;
to_max(ans , v);
}
cout << ans << endl;
return 0;
}
①处应填（ ）
A. x >>= 1
B. x ^= x &(x ^ (x + 1))
C. x -= x | -x
D. x ^= x &(x ^ (x – 1))
②处应填（ ）
A. (a & MS) << B
B. a >> B
C. a & (1 << B)
D. a & (MS << B)
③处应填（ ）
A. -INF
B. Max[y][x]
C. 0
D. Max[x][y]
④处应填（ ）
A. Max[x][z] + w(y ^ z)
B. Max[x][z] + w(a ^ z)
C. Max[x][z] + w(x ^ (z << B))
D. Max[x][z] + w(x ^ z)
⑤处应填（ ）
A. to_max(Max[y][z], v + w(a ^ (z << B)))
B. to_max(Max[z][y], v + w((x ^ z) << B))
C. to_max(Max[z][y], v + w(a ^ (z << B)))
D. to_max(Max[x][z], v + w(y ^ z))
题目分析
本题要求计算一个子序列的最大分值，其中分值为相邻元素异或值的 (w(x)=x+\\operatorname{popcnt}(x)) 之和。直接枚举子序列的复杂度太高，需要利用动态规划并优化转移。
关键性质
将每个数 (a) 拆分为高8位 (h) 和低8位 (l)（因为 (m=16)，(B=8)）。对于两个数 (a=(h_1,l_1)) 和 (b=(h_2,l_2))，有： $ a \\oplus b = (h_1 \\oplus h_2) \\ll 8 ;\\big|; (l_1 \\oplus l_2) $ 由于高低位不重叠，
w
(
a
⊕
b
)
w(a \\oplus b)
w(a⊕b) 可以分解为： $ w(a \\oplus b) = w\\big((h_1 \\oplus h_2) \\ll 8\\big) + w(l_1 \\oplus l_2) $ 其中
w
(
x
≪
8
)
=
(
x
≪
8
)
+
popcnt
(
x
)
w(x \\ll 8) = (x \\ll 8) + \\operatorname{popcnt}(x)
w(x≪8)=(x≪8)+popcnt(x)，而
w
(
l
1
⊕
l
2
)
w(l_1 \\oplus l_2)
w(l1⊕l2) 是8位数的分值。
动态规划状态设计
设 dp[i]表示以第 i个数结尾的子序列的最大分值。转移时需枚举前一个数 j： $ dp[i] = \\max\\left(0,\\ \\max_{j < i} \\big( dp[j] + w((h_i \\oplus h_j) \\ll 8) + w(l_i \\oplus l_j) \\big) \\right) $ 直接枚举 j 是
O
(
n
2
)
O(n^2)
O(n2) 不可行。利用分解式，我们可以将状态按高8位分组，并维护一个二维数组
M
a
x
[
u
]
[
v
]
Max[u][v]
Max[u][v]，其含义为：
- 对于所有之前已经处理过的数，固定未来数的高8位为 (u)，且当前数的低8位为 (v) 时，所能获得的最大“部分价值”，即： $ Max[u][v] = \\max_{\\text{之前的数 } b=(h_b,l_b)} \\big( dp[b] + w((u \\oplus h_b) \\ll 8) \\big) $ 这里 v 对应之前数的低8位
l
b
l_b
lb。
那么对于当前数
a
=
(
h
,
l
)
a=(h,l)
a=(h,l)，考虑从任意之前的数 b 转移：
- 从 b 转移的价值为
d
p
[
b
]
+
w
(
(
h
⊕
h
b
)
≪
8
)
+
w
(
l
⊕
l
b
)
dp[b] + w((h \\oplus h_b) \\ll 8) + w(l \\oplus l_b)
dp[b]+w((h⊕hb)≪8)+w(l⊕lb)。 - 若固定 b 的低8位
l
b
=
v
l_b = v
lb=v，则M
a
x
[
h
]
[
v
]
Max[h][v]
Max[h][v] 已经存储了所有满足l
b
=
v
l_b=v
lb=v 的 b中d
p
[
b
]
+
w
(
(
h
⊕
h
b
)
≪
8
)
dp[b] + w((h \\oplus h_b) \\ll 8)
dp[b]+w((h⊕hb)≪8)的最大值。 - 因此，对于当前 a，只需枚举所有可能的 v，取
max
v
(
M
a
x
[
h
]
[
v
]
+
w
(
l
⊕
v
)
)
\\max_v (Max[h][v] + w(l \\oplus v))
maxv(Max[h][v]+w(l⊕v))，再与0比较即得 dp[a]。
状态更新
计算出 dp[a] 后，需要用 a更新 Max数组，以便后续数使用。对于任意未来的高8位 u，a 贡献的价值为
d
p
[
a
]
+
w
(
(
u
⊕
h
)
≪
8
)
dp[a] + w((u \\oplus h) \\ll 8)
dp[a]+w((u⊕h)≪8)，且其低8位为 l。因此更新： $ Max[u][l] = \\max\\big(Max[u][l],\\ dp[a] + w((u \\oplus h) \\ll 8)\\big) $
算法流程
−
∞
-\\infty
−∞（负无穷）。
- 计算高8位
x
=
a
≫
B
x = a \\gg B
x=a≫B，低8位y
=
a
&
M
S
y = a \\& MS
y=a&MS（M
S
=
(
1
<
<
B
)
−
1
MS = (1<<B)-1
MS=(1<<B)−1）。 - 设当前最优值 v = 0（空子序列）。
- 枚举所有
z
=
0
…
M
S
z = 0 \\ldots MS
z=0…MS，用M
a
x
[
x
]
[
z
]
+
w
(
y
⊕
z
)
Max[x][z] + w(y \\oplus z)
Max[x][z]+w(y⊕z) 更新 (v)（取最大值）。 - 记录答案
a
n
s
=
max
(
a
n
s
,
v
)
ans = \\max(ans, v)
ans=max(ans,v)。 - 枚举所有
z
=
0
…
M
S
z = 0 \\ldots MS
z=0…MS，更新M
a
x
[
z
]
[
y
]
=
max
(
M
a
x
[
z
]
[
y
]
,
v
+
w
(
(
x
⊕
z
)
≪
B
)
)
Max[z][y] = \\max(Max[z][y],\\ v + w((x \\oplus z) \\ll B))
Max[z][y]=max(Max[z][y], v+w((x⊕z)≪B))。
时间复杂度：每个数处理两个 256的循环，共
O
(
n
×
512
)
O(n \\times 512)
O(n×512)，空间
O
(
256
2
)
O(256^2)
O(2562)，可行。
答案及解析
- ① 计算 (w(x)) 需要统计 (x) 的二进制1个数。常用技巧是每次消去最低位的1：x ^= x & (x ^ (x-1)) 等价于 x &= x-1，但这里用异或实现。选 D 。
- ② 取高8位：a >> B，B=8，选 B。
- ③ 初始化 v 为 0，表示空子序列，选 C。
- ④ 转移时用
M
a
x
[
x
]
[
z
]
+
w
(
y
⊕
z
)
Max[x][z] + w(y \\oplus z)
Max[x][z]+w(y⊕z)，选 A。 - ⑤ 更新时用
M
a
x
[
z
]
[
y
]
=
max
(
…
,
v
+
w
(
(
x
⊕
z
)
≪
B
)
)
Max[z][y] = \\max(\\dots, v + w((x \\oplus z) \\ll B))
Max[z][y]=max(…,v+w((x⊕z)≪B))，选 B。
专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html
各种学习资料，助力大家一站式学习和提升！！！
#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 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.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;
}
