Codeforces Round #765 ABC 题解 (Java/C++)

A. Ancient Civilization

题解

统计每一位为1的x的个数。如果某一位的1多于了一半，则y在这一位为1，否则则为0。

代码

Java

C++

B. Elementary Particles

题解

对于任意两个相同的数，我们至少可以找到长度为1的l和r。同时非常自然的，我们会希望扩展l和r的长度。
显然，如果考虑向右拓展，则两个数中靠右的数限制多一些；如果向左拓展，则靠左的数限制多一些。
因此，相邻的两个相同的数一定比不相邻的两个数最终的长度要长。

因此我们只需要记录每个数上次出现的位置，这样每次都可以快速求出当前数对应的最大长度。

代码

Java

C++

C. Road Optimization

题解

显然是一个DP问题。

dp[i][j]表示，移除j个路标时，到达第i个路标需要的最小时间。
根据定义，显然dp[0][j]=0。需要注意的是，这里我也定义了dp[0][2]=0，也就是说：允许浪费删除路标的额度。

接着对于不等于0的i，dp[i][i - 1 - j + x]=min{dp[j][x]+a[j]*(d[i]-d[j])}。
也就是说，考虑到达第i个路标，且从j到i之间没有别的路标的情况下最小的时间。显然从j到i需要a[j]*(d[i]-d[j])的时间。
其中，假设到达j时已经删除了x个路标。那么此时，加上删除i到j之间所有的路标，共删除了x+i-1-j个路标。

最后找出dp[n+1]的最小值即可。

代码

Java

C++