A. Two Gruops
将正负数分离为两个集合,得到 \(sum_{+},sum_{-}\) 。
考虑将一个数移到正负性相反的集合中,一定会导致 \(sum_{+},sum_{-}\) 同时在数轴上向原点移动,差值绝对值不更优。故所有数的和取绝对值等价于答案。
Code
B. BAN BAN
贪心题。
每次贪心交换靠前的 \(N\) 与靠后的 \(A\) ,将所有 \(N\) 移至 \(A\) 之前即可。
Code
C. Swap Game
贪心、博弈题。
对于任何人 \(R\) :当前一轮 \(R\) 操作后送上 \(a_1\) 的元素在下一次 \(R\) 操作时( \(2\) 轮后)一定同样可选。
规则:一个人若可以在 \(a_2\sim a_n\) 选择 \(0\) (送上 \(a_1\) ),胜利。
那么最优策略即为:初始选定可选的最小值,每次都选它直至减到 \(0\) 获胜。
\(a_1\) 相当于被Bob先手在第 \(0\) 轮选上,我们只需要判断 \(a_1\) 是否是序列最小值———Bob能否获胜
Code
D. Yet Another Problem
给定区间 \([l, r]\) 。
若 \(\oplus_{i=l}^{r}a[i] \ne 0\) 则无解
否则分类讨论:
1.区间全为 \(0\) :\(0\) 。
2.区间长为奇数: \(1\)。
3.区间长为偶数、两端存在 \(0\) :\(1\) 。
4.区间长为偶数、两端无 \(0\) : \(-1\) 。
\(\quad\)若区间内二分查找存在 \(p\) 使得 \((p-l+1)\& 1=1\) 且 \(\oplus_{i=l}^{p}a[i] \ne 0\) 为 \(0\) : \(2\)。
\(\quad\)否则无解: \(-1\)。
Code
n = read(), Q = read();
for(ll i = 1; i <= n ; i++) a[i] = read(), xr[i] = xr[i-1]^a[i], sum[i] = sum[i-1]+a[i];
for(ll i = 1; i <= n ; i++) pos[i&1][xr[i]].pb(i);
while(Q--){
ll l = read(), r = read();
if(xr[r] ^ xr[l-1]) puts("-1");
else if(sum[r] == sum[l-1]) puts("0");
else if((r-l+1) & 1) puts("1");
else if(!a[l] || !a[r]) puts("1");
else{//one even is divided into two odds
auto it = lower_bound(pos[l&1][xr[l-1]].begin(), pos[l&1][xr[l-1]].end(), l-1);
if(it != pos[l&1][xr[l-1]].end() && *it < r) puts("2");
else puts("-1");
}
}
标签:832,Code,长为,sum,Codeforces,区间,Div2,贪心
From: https://www.cnblogs.com/CAL522/p/CFR832Div2.html