2022百度之星程序设计大赛 - 复赛 1001 子序列

problem

度度熊有一个大小为 nn 的整数数组 a_1,a_2,\cdots,a_na
1
​
,a
2
​
,⋯,a
n
​
。

数组 a_1,a_2,\cdots,a_na
1
​
,a
2
​
,⋯,a
n
​
的一个子序列 a_{b_1},a_{b_2},\cdots,a_{b_k}a
b
1
​

​
,a
b
2
​

​
,⋯,a
b
k
​

​
是非空的递增子序列当且仅当 k\geq 1k≥1，且对于任意的 i \in [1,k-1]i∈[1,k−1]，有 b_i i
​
i+1
​
,a
b
i
​

​
b
i+1
​

​
。

她需要将这个数组分成若干个非空的递增子序列，满足每个位置都在这些子序列中出现恰好一次。

定义一个序列 c_1,c_2,\cdots ,c_mc
1
​
,c
2
​
,⋯,c
m
​
的价值为 c_1\oplus c_2\oplus \cdots \oplus c_mc
1
​
⊕c
2
​
⊕⋯⊕c
m
​
，即所有数按位异或后的结果。对于一个数组 aa 的子序列划分方案，其价值定义为所有子序列价值的代数和。

度度熊想知道所有符合上述要求的划分方案中，划分方案的最大价值。

格式
输入格式：
第一行一个整数 n(1\le n \le 10^5)n(1≤n≤10
5
)，表示数组的长度。
第二行 nn 个整数，为 a_1,a_2,\cdots,a_n(0\le a_i\le 10^9)a
1
​
,a
2
​
,⋯,a
n
​
(0≤a
i
​
≤10
9
)，表示这个数组。

输出格式：
一行一个整数，表示所有符合要求的划分方案的最大值。

样例 1
输入：
2 1 2
输出：
3
说明：

solution

• 发现结论，直接全部加起来输出即可。
• 记得开longlong，不然会WA

  #include
  using namespace std;
  typedef long long LL;
  int main(){
      int n;  cin>>n;
      LL sum = 0;
      for(int i = 1; i <= n; i++){
          LL x;  cin>>x;
          sum += x;
      }
      cout<<sum<<"\n";
      return 0;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13