20.	（最优子序列）取m = 16，给出长度为n的整数序列a1, a2,…, an(0≤ ai <$2^m$)。对于一个二进制数x，定义其分值w(x)为x+ popcnt(x)，其中popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1, b2…, bk，定义其子序列分值S为w(b1 ⊕ b2) + w(b2 ⊕ b3)+w(b3 ⊕  b4)+…+w(bk-1 ⊕ bk)。其中⊕表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤n ≤ 40000)。接下来一行包含n个整数a1, a2,…, an。
提示：考虑优化朴素的动态规划算法，将前m/2位和后m/2位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是x、最后一个位置的低8位是y时的最大价值。
试补全程序。
```
1 	#include <iostream>
2 
3 	using namespace std;
4 
5 	typedef long long LL;
6 
7 	const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
8 	const LL INF = 1000000000000000LL;
9 	LL Max[MS + 4][MS + 4];
10
11	int w(int x) 
12	{
13		int s = x;
14		while(x) 
15		{
16			①;
17			s++;
18		}
19		return s;
20	}
21
22	void to_max(LL &x, LL y) 
23	{
24		if(x < y)
25			x = y;
26	}
27
28	int main() 
29	{
30		int n;
31		LL ans = 0;
32		cin >> n;
33		for(int x = 0; x <= MS; x++)
34			for(int y = 0; y <= MS; y++)
35				Max[x][y] = -INF;
36		for(int i = 1; i <= n ; i++) 
37		{
38			LL a;
39			cin >> a;
40			int x = ② , y = a & MS;
41			LL v = ③;
42			for(int z = 0; z < = MS; z++)
43				to_max(v, ④);
44			for(int z = 0; z < = MS; z++)
45				⑤;
46			to_max(ans , v);
47		}
48		cout << ans << endl;
49		return 0;
50	}
```
①处应填（）
 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))

有道小图灵信息学

2020CSP提高级第一轮认证

有道小图灵 信息学

2020CSP提高级第一轮认证

有道小图灵信息学