D. Yet Another Problem
算法本质
思维
题目大意
给定一个长度为n的数组arr[]，下面给出m此询问，每次询问给出l r。
需要回答，对于arr[l~r]，我们可以最少进行多少次操作，使得其元素全部为0（无法输出-1）。
一次操作定义：
选定arr[l~r]内连续的奇数个元素，设x为这些元素异或运算，然后将在arr[]这奇数个元素全部赋为x。
思路推演
梳理思路，显然我们需要找到一个可以通用的、死板的方法来方便解题。
在各种猜测、尝试后，第一个问题映入脑海：某个元素变为0，是否会存在中间过程，还是说一步到位。
如果是存在中间步骤，则肯定是会对下一次操作有利的。通过这个点，我们可以很快推出：
- 元素变为0是一步到位的。
思维部分最难想到的地方就是这一步了，当推出这个结论后，无数多个结论就蜂拥而至：
- 元素总个数为奇数时，是会被化为奇数个操作搞定的——>奇数个操作，可以直接融合为1次操作
- 元素总个数为奇数时，如果能被操作，是被1次或者2次操作搞定的
- ……
进一步分类：
元素个数为奇数：
元素和为0（元素全部为0）次数为：0
元素异或运算值不等于0：-1
元素异或运算值等于0：1
元素个数为偶数：
元素和为0（元素全部为0）次数为：0
元素异或运算值不等于0：-1
元素异或运算值等于0：
{
若能划分出2个连续的奇数块，且这两个连续的奇数块都必须异或和为0，则：1 或 2 （若其中一个奇数块全为0则选择1）
若无法满足上述要求：-1
}接下来就需要查询复杂度：
重点在于，如何O(log~2~n)查询到是否存在这样的奇数块呢？
继续推理：
若第一个奇数块异或为0，且整体异或为0，则第二个奇数块异或也为0。
怎么判断是否存在一个以l为下标的奇数块异或为0呢：
异或性质！
设xsum[y]表示arr[1~y]的元素异或值
设i表示第一个奇数块的末尾下标，若存在i使得xsum[i] == xsum[l-1] && i-l+1为奇数，则说明arr[l~i]元素异或值为0，即第一个奇数块！
ac核心代码
记得关流！
头文件、宏定义、快读模板、常见变量、常见变量等略。
int sum[maxn], xsum[maxn]; //sum[]前缀和，xsum[]异或前缀
int gsum(int l, int r)
{
return sum[r] - sum[l-1];
}
int gxsum(int l, int r)
{
return xsum[r] ^ xsum[l-1];
}
map<int, vector<int>> mp1, mp2; //mp1用来存放奇数下标的异或前缀和，mp2存偶数
//mp[异或前缀]里放的是下标集合
inline void solve()
{
//init
cin>>n>>m;
rep(i,1,n) cin>>ar[i];
rep(i,1,n)
{
sum[i] = sum[i-1] + ar[i]; //搞定前缀和、异或前缀和
xsum[i] = xsum[i-1] ^ ar[i];
}
for (int i=0; i<=n; i++)
{
if (i%2==1) mp1[xsum[i]].push_back(i); //奇数下标的异或前缀和
else mp2[xsum[i]].push_back(i); //偶数下标的异或前缀和
}
//cal
while (m--)
{
int l, r, len;
cin>>l>>r;
len = r-l+1; //长度
//cal
if (gsum(l, r)==0) //全是0的情况，不需要出手
ans=0;
else if (gxsum(l, r)!=0) //如果异或和不为0，直接G
ans=-1;
else if (len%2==1) //奇数，不全为0，且可以操作得到0，则只需要一次操作
ans=1;
else if (ar[l]==0 || ar[r]==0) //偶数区间的特殊情况，可以看作一个奇数区间
ans=1;
else //偶数，不全为0，也许可以操作得到0，还需要进一步判断
{
vector <int> *pv; //奇数下标的异或前缀和
if (l%2==1) pv=&mp1[xsum[l-1]]; //奇数下标
else pv=&mp2[xsum[l-1]]; //偶数下标
auto it = lower_bound((*pv).begin(), (*pv).end(), l); //找到第一个大于l的下标
if (it!=(*pv).end() && *it<=r) //如果存在，且小于等于r，说明可以操作得到0
ans=2;
else
ans=-1;
}
//out
cout<<ans<<endl;
}
return;
}
评论 (0)