首页 > 其他分享 >Codeforces Round #832 (Div. 2)

Codeforces Round #832 (Div. 2)

时间:2022-11-05 01:22:38浏览次数:73  
标签:832 先手 必败 Codeforces 必胜 BAN 操作 Div oplus

A. Two Groups

数组和的绝对值即为答案。

B. BAN BAN

大概就是尽可能把前面的 B 搞到后面,尽可能把后面的 N 搞到前面。

答案为 \(\lceil \frac{n}{2} \rceil\) ,操作为每次交换正数第 \(i\) 个 BANB 和倒数第 \(i\) 个 BANN

C. Swap Game

先说结论:若 \(a_1\) 等于 \(\min_{i = 1}^{n} a_i\),则先手必败,反之先手必胜。

推导过程如下:

\(a_1 > 0, \exist a_i = 0\) ,此时先手必胜;

\(a_1 = 1, a_i > 0\) 时,走一步到先手必胜,所以先手必败;

\(a_1 > 1, \exist a_i = 1\) 时,走一步到先手必败,所以先手必胜。

\(a_2 = 2, a_i > 1\) 时,走一步到先手必胜,所以先手必败。

以此类推,观察可得 \(a_1\) 是最小值时先手必败,并且走一步之后 \(a_1\) 就不是最小值了,先手必胜。

D. Yet Another Problem

特判全 \(0\) 的情况。

观察: 操作\(a_{L \dots R}\)相当于把 \(a_{L \dots R}\) 变成了 \(\oplus_{i = L}^{R} a_i\)。
推论: 若 \(\oplus_{i = l}^{r} a_i \ne 0\) ,则无解。因为不管怎么操作,\(\oplus_{i = l}^{r} a_i \ne 0\) 的值不会变。

现在只需要考虑 \(\oplus_{i = l}^{r} a_i = 0\) 的情况。

易得:若 \(r - l + 1\) 为奇数,则一次就能搞定。同理,若 \(a_l = 0\) 或 \(a_r = 0\) 则一次就能搞定。

现在只需要考虑 \(r - l + 1\) 为偶数,且 \(a_l\) 和 \(a_r\) 均不为 \(0\) 的情况。这种情况下至少需要两次操作,因为操作不能同时包括 \(a_l\) 和 \(a_r\) 。

如果存在某个 \(p\) 使得 \(p \in [l, r]\) 且 \(p - l + 1\) 为奇数且 \(\oplus_{i = l}^{p} a_i = 0\) ,则 \(r - (i + 1) + 1\) 也为奇数且 \(\oplus_{i = p + 1}^{r} a_i = 0\) 。所以如果存在这样的 \(p\) 就能用两次操作解决问题,否则就不行。

然后就是简单模拟了。

E. List Generation

写题 1h 然后罚坐 1h 。

To be solved.

标签:832,先手,必败,Codeforces,必胜,BAN,操作,Div,oplus
From: https://www.cnblogs.com/zengzk/p/16859551.html

相关文章

  • 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的位数过......
  • Codeforces Global Round 20 D F1 F2/more
    https://codeforc.es/contest/1672F1https://www.luogu.com.cn/blog/AlexWei/solution-cf1672f1将置换分解为若干轮换(环),悲伤值越大\(\Rightarrow\)环越少(设环为\(k......
  • Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2) D
    D.ExplorerSpace我们考虑一个性质就是他最多就是找到一条k/2的最短路径然后回来这样是肯定是包含最优解的这个观察第二个样例我们将其改变一下要是我们一半的长度......
  • CodeForces 1540B Tree Array
    CF传送门洛谷传送门很强的一个题。发现根的选择很重要,于是考虑先枚举根。考虑枚举两个点对\(i,j\(i<j)\),如果\(j\)比\(i\)先被标记,那么\(i,j\)就贡献了一个逆......
  • CodeForces - 204A Little Elephant and Interval
    题意:给定区间[l,r],问区间内有多少第一个数字和末尾数字一样的数。解:练习一些数位dp。先从高到低dp[pos][fir]表示dp到第pos个位置,以fir开头的串的数量,其中fir不为0。这道......