CF1604B XOR Specia-LIS-t
orz_z
·
·
题解
题目大意
给出一个长度为 n 的整数序列 a，将其划分为 k 个连续子串。
设 h_1, h_2, h_3...h_k 是每个子串的最长上升字序列的长度。
求是否有一种划分方式使得 h_1 \oplus h_2 \oplus h_3 \oplus ... \oplus h_n = 0。
对于 $100\%$ 的数据，$1 \leq t \leq 10000$，$2≤n≤10^5$，$1 \le a_i \le 10^9$。
### 解题思路
显然，当 $n$ 为偶数时，每个数都可自分一组，即 $k=n$ 且 $\forall 1 \leq i \leq k,h_i = 1$，满足题意。
当 $n$ 为奇数时，若可以找到一组 $a_{i-1} \geq a_i$ 时，那么可以将 $a_{i-1}$ 和 $a_i$ 分成一组，其他每个数自分一组，此时 $k=n-1$ 为 偶数且 $\forall 1 \leq i \leq k,h_i = 1$，，满足题意。
如果找不到一组 $a_{i-1} \geq a_i$，说明 $a$ 单调递增，那么无论如何都会有奇数个 $h_i$ 为奇数，此时必然无解。
具体见代码。
### CODE
```cpp
#include <bits/stdc++.h>
using namespace std;
int T, n;
int a[100007];
signed main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1 ; i <= n; ++i) scanf("%d", &a[i]);
if(n % 2 == 0)
{
puts("YES");
continue;
}
int flag = 0;
for(int i = 2; i <= n; ++i)
{
if(a[i - 1] >= a[i]) flag = 1;
}
if(flag)
{
puts("YES");
}
else
{
puts("NO");
}
}
return 0;
}
```