关于网站建设的软文,自己建设网站需要多少钱,网站开发需求说明书模板,天津seo优化公司Problem - D - Codeforces
题意 思路
一看这个做法一定就是分类讨论
先判无解
显然#xff0c;如果区间异或和不是0一定无解
如果区间内全是0#xff0c;答案一定是0
之后怎么讨论
注意到需要讨论区间长度
如果长度是奇数#xff0c;那么直接操作即可#xff0c;答…Problem - D - Codeforces
题意 思路
一看这个做法一定就是分类讨论
先判无解
显然如果区间异或和不是0一定无解
如果区间内全是0答案一定是0
之后怎么讨论
注意到需要讨论区间长度
如果长度是奇数那么直接操作即可答案一定是1
else 如果是偶数需要看是否存在一个分割点使得一个区间可以分割成两个区间两个区间的区间异或和都是0
这点有点难注意到我们很容易地会以为如果一个区间的异或和是0一定存在分割点其实不一定这点需要记住
那么问题就是如何找这个分割点
这个分割点假设是 k, 需要满足pre[l - 1] pre[k] 且 位置的奇偶性要和 l 一致因为区间长度要是奇数那么就是去找后面第一个满足这个条件的就行
那么就是把所有前缀异或和为 pre[l - 1]和位置的奇偶性放进集合里二分查找即可
Code
#include bits/stdc.h#define int long longconstexpr int N 2e5 10;
constexpr int mod 998244353;std::mapint, std::vectorint S[2];int n, q;
int a[N];
int pre[N];
int s[N];int get(int l, int r) {return pre[r] ^ pre[l - 1];
}
void solve() {std::cin n q;pre[0] 0;for (int i 1; i n; i ) {std::cin a[i];pre[i] pre[i - 1] ^ a[i];s[i] s[i - 1] (a[i] 0);S[i 1][pre[i]].push_back(i);}while(q --) {int l, r;std::cin l r;if (get(l, r) ! 0) {std::cout -1 \n;continue;}if (s[r] - s[l - 1] r - l 1) {std::cout 0 \n;continue;}if ((r - l 1) % 2 1 ||((r - l 1) % 2 0 (a[l] 0 || a[r] 0))) {std::cout 1 \n;}else {auto it std::lower_bound(S[l 1][pre[l - 1]].begin(), S[l 1][pre[l - 1]].end(), l);if (it ! S[l 1][pre[l - 1]].end() *it r) {std::cout 2 \n;}else {std::cout -1 \n;}}}
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;while (t--) {solve();}return 0;
}
