补题 Vampiric Powers, anyone?

题面翻译

题目描述

DIO 意识到星尘十字军已经知道了他的位置，并且即将要来挑战他。为了挫败他们的计划，DIO 要召唤一些替身来迎战。起初，他召唤了 $ n $ 个替身，第 $ i $ 个替身的战斗力为 $ a_i $。依靠他的能力，他可以进行任意次以下操作：

  • 设当前的替身数量为 $ m $。
  • DIO 选择一个序号 $ i \text{ } ( 1 \le i \le m ) $。
  • 接着，DIO 召唤一个新的替身，其序号为 $ m + 1 $，战斗力为 $ a_{m + 1} = a_i \oplus a_{i + 1} \oplus \ldots \oplus a_m $。其中，运算符 $ \oplus $ 表示按位异或。
  • 现在，替身总数就变成了 $ m + 1 $。

但对于 DIO 来说，不幸的是，星尘十字军通过隐者之紫的占卜能力，已经知道了他在召唤替身迎战的事情，而且他们也知道初始的 $ n $ 个替身的战斗力。现在，请你帮他们算一算 DIO 召唤的替身的最大可能战斗力（指单个替身的战斗力，并非所有替身战斗力之和）。

输入格式

每个测试点包含多组测试数据。每个测试点的第一行包含一个整数 $ t \text{ } ( 1 \le t \le 10^4 ) $，代表测试数据组数。

每组测试数据的第一行包含一个整数 $ n \text{ } ( 1 \le n \le 10^5 ) $，代表初始的替身数量。

每组测试数据的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n \text{ } ( 0 \le a_i < 2^8 ) $，代表每个替身的战斗力。

保证单个测试点内 $ n $ 的总和不超过 $ 10^5 $。

输出格式

对于每组测试数据，在一行内单独输出一个整数，代表 DIO 召唤的替身的最大可能战斗力（指单个替身的战斗力，并非所有替身战斗力之和）。

说明/提示

在第一组测试数据中，其中一种召唤新替身的方式如下：

  • 选择 $ i = 4 $，然后，序列 $ a $ 变为 $ [0, 2, 5, 1, 1] $。
  • 选择 $ i = 1 $，然后，序列 $ a $ 变为 $ [0, 2, 5, 1, 1, 7] $。$ 7 $ 即为替身的最大可能战斗力。

在第二组测试数据中，DIO 不需要召唤任何新的替身，因为 $ 3 $ 已经是替身的最大可能战斗力。

题目描述

DIO knows that the Stardust Crusaders have determined his location and will be coming to fight him. To foil their plans he decides to send out some Stand users to fight them. Initially, he summoned $ n $ Stand users with him, the $ i $ -th one having a strength of $ a_i $ . Using his vampiric powers, he can do the following as many times as he wishes:

  • Let the current number of Stand users be $ m $ .
  • DIO chooses an index $ i $ ( $ 1 \le i \le m $ ).
  • Then he summons a new Stand user, with index $ m+1 $ and strength given by: $ $$$a_{m+1} = a_i \oplus a_{i+1} \oplus \ldots \oplus a_m, $ $

    where the operator $ \\oplus $ denotes the bitwise XOR operation.

    </li>
  • Now, the number of Stand users becomes $ m+1$$$.

Unfortunately for DIO, by using Hermit Purple’s divination powers, the Crusaders know that he is plotting this, and they also know the strengths of the original Stand users. Help the Crusaders find the maximum possible strength of a Stand user among all possible ways that DIO can summon.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10\,000 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) – the number of Stand users initially summoned.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i < 2^8 $ ) – the strength of each Stand user.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output a single integer, maximum strength of a Stand user among all possible ways that DIO can summon.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
3
4
0 2 5 1
3
1 2 3
5
8 2 4 12 1

样例输出 #1

1
2
3
7
3
14

提示

In the first test case, one of the ways to add new Stand users is as follows:

  • Choose $ i=n $ . Now, $ a $ becomes $ [0,2,5,1,1] $ .
  • Choose $ i=1 $ . Now, $ a $ becomes $ [0,2,5,1,1,7] $ . $ 7 $ is the maximum strength of a Stand user DIO can summon.

In the second test case, DIO does not need to add more Stand users because $ 3 $ is the maximum strength of a Stand user DIO can summon.

题解

题目解析

CF1847C Vampiric Powers, anyone? - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

除此之外我再添加一点我自己迷惑的地方:

首先 $a_i$ 的数值是小于 $2^8$ 的, 所以可以用桶存值然后遍历的方式来实现 $O(T\cdot n)$ 级别的操作, 其中我当时卡在了一个地方: ans=max(ans,x[i]^j);

这里的 x[i]^j 究竟是什么东西?

1
2
3
4
5
我们实际上的j是在之前组成了的结果之下才能执行这个语句的.
我们把组成j的值所需要的右边界的位置设为p_j
实际上x[i]^j指的是:
(p_j,i]/(i,p_j]这个区间内的所有值按位异或,也就是组成的力量值.
其实j就是我们的x[p_j],可以理解了吧.

但是这里的前面是开区间怎么办? 也就是异或不到第一位的值, 想一个方法:

我们把 x[0] 也加进去不就可以了吗, 反正 $0 \oplus x = x$ .

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits\stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(1e5);
int x[MAXN],n,vis[1<<9],temp,ans;

signed main(){
	CIN_;CIN;
	T_{
		mem(vis,0);
		cin >> n;
		fa(i,1,n){
			cin >> temp;
			x[i] = temp ^ x[i-1];
			vis[x[i]] = 1;
		}
		ans = 0;
		fa(i,0,n) fa(j,0,(1<<8)) if(vis[j]) ans = max(ans,j ^ x[i]);
		cout << ans << endl;
	}
	return 0;
}