首页 > 其他分享 >Codeforces Round #832 (Div2)

Codeforces Round #832 (Div2)

时间:2022-11-05 13:55:28浏览次数:82  
标签:832 Code 长为 sum Codeforces 区间 Div2 贪心

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

相关文章

  • Codeforces Round #832 (Div. 2) E
    牛逼题。通过拐点刻画路径,这样每条路径的贡献方式唯一,你只要钦定拐点都选即可刻画唯一的路径,然后路径上的其他点随便选。https://codeforc.es/contest/1747/problem/Eht......
  • Codeforces Round #751 (Div. 2) D
    D.FrogTraveler考虑dpdp[i]表示i高度的时候最少多少步能达到然后再bfs就可以了但是这样是n2的虽然看起来只有n个点我们考虑优化我们主要复杂度是当前点还会去搜......
  • Codeforces Round #832 (Div. 2) A-D
    比赛链接A题解知识点:贪心。我们考虑把正数和负数分开放,显然把负数和正数放在一起的结果不会更优。时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码#include<bits/std......
  • Codeforces Round #832 (Div. 2)
    A.TwoGroups数组和的绝对值即为答案。B.BANBAN大概就是尽可能把前面的B搞到后面,尽可能把后面的N搞到前面。答案为\(\lceil\frac{n}{2}\rceil\),操作为每次......
  • Codeforces Round #764 (Div. 3) G
    G.MinOrTree看到或运算我们思考如何按位来做我们可以贪心的从高位到低位的要是该位可以都用0的来构成一颗生成树我们显然是很高兴的但是怎么check?我们每次遍历一......
  • CodeForces - 914C Travelling Salesman and Special Numbers
    题意:给出一个二进制数a,每次操作将当前数变成其二进制下1的个数,若干次操作后可以将其变为1.给定k,求不大于a的数中,经过k次操作能变成1的数的数量。解:观察一下这个操作,可以求......
  • Codeforces Round #776 (Div. 3) E
    E.ReschedulingtheExam显然我们能想到的每次操作都是先将最小的取出来操作要是我们有两个数都是最小的我们只有相邻的时候才能操作要是大于两个那我们就不管怎么操......
  • Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) F M
    A-E都还是比较简单的。首先,容易想到的,异或上\(2^k\),相当于以\(2^{k+1}\)的长度分块,然后每一块对半切,然后交换左右部分。我的想法是由于这个交换的性质,也许我们可以尝......
  • Codeforces Round #766 (Div. 2)
    CodeforcesRound#766(Div.2)\(\color{Green}{★}\)表示赛时做出。\(\color{Yellow}{★}\)表示赛后已补。\(\color{Red}{★}\)表示\(\text{To\be\solved}\)......
  • Codeforces Round #820 (Div. 3) F
    F.KireiandtheLinearFunction首先我们知道的是给定长度w都是%9意义下的所以我们枚举四个位置的数就是9^4预处理出来答案这里我们要去w长度的串%9但是w的位数过......