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

A. Ancient Civilization

题解

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

代码

Java

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

C++

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

B. Elementary Particles

题解

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

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

代码

Java

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

C++

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

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

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

C++

Submission #144339520 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论