Codeforces Round #742 ABCDE 题解 (Java/C++)

A. Domino Disaster

题解

显然,如果第一行是LR,或RL,那么第二行只需要也摆成一样的就可以了。
如果第一行是U,那么第二行显然是D。反过来如果第一行是D,第二行则是U。

代码

Java

Submission #128131250 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #128131716 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. MEXor Mixup

题解

显然,根据MEX的定义,0到a-1以内的所有数都必须被选中,且a必须不被选中。

接着,如果$0\oplus 1\oplus\dots\oplus a-1=b$则直接输出a即可。

如果$0\oplus 1\oplus\dots\oplus (a-1)\neq b$且,$0\oplus 1\oplus\dots\oplus (a-1)\oplus b\neq a$,则我们选择0到a-1,以及$0\oplus 1\oplus\dots\oplus (a-1)\oplus b$,共a+1个数即可。

如果$0\oplus 1\oplus\dots\oplus (a-1)\neq b$且,$0\oplus 1\oplus\dots\oplus (a-1)\oplus b= a$,因为不能选择$0\oplus 1\oplus\dots\oplus (a-1)\oplus b$,所以我们随便选择任意一个其他的数x,使得$0\oplus 1\oplus\dots\oplus (a-1)\oplus b\oplus x\neq a$。
也就是选择选择0到a-1,以及x和$0\oplus 1\oplus\dots\oplus (a-1)\oplus b\oplus x$,共a+2个数。

代码

Java

Submission #128133288 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #128133515 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Carrying Conundrum

题解

因为定义的加法运算中是向往前两位进行进位。所以其运算可以拆分为奇数位和偶数位两部分。

于是我们把n的奇数和偶数拆出来,我们就能得到奇数位的和以及偶数位的和,分别记为x和y。接着我们只需要找出所有的x=x1+x2和y=y1+y2。

显然,对于固定的x和y,一旦确定了x1和y1,就能确定x2和y2。于是共有$(x+1)\cdot(y+1)$种可能。
最后,考虑a和b不能为0这个条件。显然当且仅当x1=0,y1=0时,a为0。当且仅当x1=x,y1=y的时候,b为0。
于是,最终结果为:$(x+1)\cdot(y+1)-2$。

代码

Java

Submission #128203017 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #128203151 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Expression Evaluation Error

题解

显然,我们希望尽可能避免进位。如果不得不进行进位,那么我们希望尽可能是较低的位置进行进位。
于是很自然的想到,我们从最高位拿走1,只要拿走这个1之后,还可能被分成n-1份就行。如果不够分,那就只能进行进位了。

举几个例子。

  1. 900分成3个数。显然,可以分成[100, 100, 700]。
  2. 200分成3个数。
    第一次,我们尝试拿走100,发现剩下的100够分成2个数。
    第二次,我们发现无法再拿走100,因为剩下的0不能分成1个数。因此只能被迫进位。于是尝试拿走10,剩下的90足够分给1个数。

总的来说,就是每次在最高位尝试拿走1。如果失败则被迫进位即可。

代码

Java

Submission #128526542 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #128526952 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Non-Decreasing Dilemma

这个题就是一个非常典型的线段树的应用,非常常见,建议熟练掌握。

Codeforces Round #742 Non-Decreasing Dilemma 题解 (Java/C++)
题解这个题目是一个典型的线段树的应用。如下图所示,我们对于每个区间维护三个属性:1. 满足条件的子串的个数,记为ans;2. 从最左侧开始,最长的连续不下降子串的长度,记为left_size;3. 从最右侧开始,最长不下降字串的长度,记为right_size。
点击上面链接查看详细题解
展示评论