題意：

• 給一序列，問能否將這序列劃分為若干個連續的子序列，使得這些這些子序列的最長上升子序列長度的異或和為0

思路：

• 性質：偶數（包含0）個1和若干0異或和即0，其它情況即1
• 如果n是偶數，直接就yes，因為可以使每個數分別為一序列，那么就滿足了偶數個1異或
• 如果n是奇數，參照n為偶數的情況，想象怎樣才能讓n個1變成n-1（偶數）個1呢？就是從n個數里拿出一個逆序對，逆序對是2個數，且貢獻為1個1，剩下的n-2個數貢獻n-2個1，那么一共就是n-1（偶數）個1異或和了

#include <iostream>using namespace std;typedef long long ll;const int N = 1e5 + 10;int a[N];int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _;cin >> _;while (_ -- ){int n;cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];bool flag = false;for (int i = 1; i <= n; i ++ )if (i != 1 && a[i] <= a[i - 1])flag = true;if (n % 2 == 0 || flag)cout << "YES" << endl;elsecout << "NO" << endl;}return 0; }

總結

以上是生活随笔為你收集整理的XOR Specia-LIS-t 异或和 贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。