Codeforces Round 893 (Div. 2) ABCD 题解 (Java/C++)

A. Buttons

题解

两个人一定会优先点$c$。所以当且仅当$c$为奇数的时候Anna可以多点一次。之后只需看$a-b$的结果是否大于零即可。如果小于等于0，那么Anna一定会输，否则会赢。

代码

Java

C++

B. The Walkway

题解

因为最多每d分钟他就一定会吃一块饼干，所以移除掉一个卖家的影响只会在相邻两个卖家之间。
所以移除一个卖家$i$的影响是从$\lfloor\frac {s_{i+1}-s_{i}} d\rfloor  + \lfloor\frac{s_i - s_{i-1}} d\rfloor + 1$变成$\lfloor\frac {s_{i+1}-s_{i-1}} d\rfloor$
所以只需要看看删除哪个卖家产生的影响比较大即可。

代码

Java

C++

C. Yet Another Permutation Problem

题解

首先，不难想到，最多只有$\lfloor \frac n 2 \rfloor$个不同的结果。
假设这个存在$x>\lfloor \frac n 2 \rfloor$，那么最好的情况就是$a_i=x,a_{i+1}=2\cdot x$，那么$a_{i+1}>n$。

到此，可以猜测正确的结果就是有$\lfloor \frac n 2 \rfloor$个不同的结果，所以就尝试找一种方式构造出来。

不难想到，对于$\lfloor \frac n 2 \rfloor$必然只能和$2\cdot \lfloor \frac n 2 \rfloor$相邻。因为$3\cdot \lfloor \frac n 2 \rfloor>n$。
同理$\lfloor \frac n 2 \rfloor - 1$必然只能和$2\cdot (\lfloor \frac n 2 \rfloor - 1)$相邻。
举个例子，假设$n=21$，那么10和20相邻，9和18相邻。

于是通过这个方式我们能一只构造到$\lfloor \frac n 4 \rfloor$左右。比如20，可以一只构造到6和12相邻。但5和10相邻就不是那么显然了，因为10已经和20相邻了。
但可以发现，4并不需要和9相邻，而是需要和$2\cdot 4=8$相邻。
于是就可以发现，每个数$a_i$只需要和$2\cdot a_i$相邻即可。

比如$n=21$，就是$[1,2,4,8,16]+[3,6,12]+[5,10,20]+[7,14]+[11]+[13]+[17]+[19]+[21]$即可。或者简单一点说，就是类似筛法求素数的方法。

代码

Java

C++

D. Trees and Segments

题解

首先，根据数据规模，$n^2=9\cdot 10^6 \approx 10^7$。

因为随着$a$不断增大，$l_0$和$l_1$的重要程度并非线性。比如$l_0=1, l_1=100$和$l_0=2, l_1=90$以及$l_0=5, l_1=30$三个可能的结果里，随着$a$的变化，选择也会不一样。
比如$a=1$，那$1\cdot 1 + 100= 101$最优，但是$a=20$时，$20\cdot 2 + 90 = 130$最优。$a=100$时，$100\cdot 5 + 30=530$最优。

所以，如果能计算出任意$l_1$对应最大的$l_0$，那么我们能就可以在$n^2$的范围内得到结果。也就是要计算一个$dp[l_1]=\max(l_0)$。

这里思路先在这里暂停。
对于$l_0$显然可以在$n\cdot k = n^2$的范围内计算在最多修改$k$次时0的最长连续子串。也就是$dpLeft[i][j]$表示从左到右第$i$棵树，最多修改$j$次，最长的连续子串。
同理也可以$n^2$的维护一个$dpRight[i][j]$表示从右到左第$i$棵树，最多修改$j$次，最长的连续子串。

到此，整合所有部分。
可以想到，可以$n^2$的枚举最长连续的1。
假设枚举到的区间是$[left, right]$，可以用前缀和维护出将任意区间中所有数都变成1需要的操作数，记为$count[right]-count[left-1]$。记$remian=k-(count[right]-count[left-1])$
那么$dp[right-left+1]=\max(dpLeft[left-1][remain], dpRight[right+1][remain])$。

代码

Java

C++