Codeforces Round #764 (Div. 3) 题解A-G

本文主要是介绍Codeforces Round #764 (Div. 3) 题解A-G，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

比赛链接

A. Deletions of Two Adjacent Letters

下标为奇数的不能用，其他的能用。遍历一边就完事了。

B. DIV + MOD

\(x\)要么是\(r\)，要么是\(r\)前面最大的满足模\(a\)等于\(a - 1\)的数。

C. Weight of the System of Nested Segments

对于任意\(2n\)个点，都可以构造出来满足条件的\(n\)个线段，所以选权值最小的\(2n\)个，这个排一下序就可以找出来。

然后构造的话，就是按横座标排序，第1个和最后1个组，第2个和倒数第2个组，以此类推。

D. Twist the Permutation

反着搞一遍就行了，就是通过从最后一个操作开始反向操作，还原出原来的数组，且反向操作的次数就是答案。

具体就是对于\(i\)从\(n\)到\(1\)，每次可以对前\(i\)个元素进行循环左移操作。因为如果\(i < j\)，第\(j\)个元素无法被\(i\)的操作影响，所以第\(i\)次需要将数\(i\)还原回原位，这样需要循环左移的次数也就有了。

没有无解的情况。

E. Rescheduling the Exam

一开始有\(n\)个休息时间，对于每一个考试，考虑先将其删去，然后再找一个最优的地方插入，这样必定会考虑到所有可能的答案。

插入要么是将最长的休息时间分成两半，要么是插到最后一天。

维护一下休息时间的可重集合就可以了。

F. Vitaly and Advanced Useless Algorithms

对于每一个工作，注意到最多就是百分之百，可以直接01背包算出完成工作需要的最短时间以及方案。

然后就是贪心做deadline最近的工作了。

G. Counting Shortcuts

首先，计算单元多汇的最短路的长度以及方案数是一个非常经典的问题，这里不再赘述。以s为源点跑一次dijkstra，算出s到t的最短路方案数，后续只需要考虑比最短路长1的方案数。

对于边\((u,v)\)，考虑用它去做那个多出来的1，假设\(d(x, y)\)表示x到y的最短路长度，那么需要\(d(s, u) + 1 + d(t, v) = d(s, t) + 1\)，又因为\(d(s, t) = d(s, u) + d(u, t)\)，所以有\(d(t, v) = d(t, u)\)。同理，因为\(dis(s, t) = d(t, v) + d(v, s)\)，所以\(d(s, u) = d(s, v)\)。

枚举所有边\((u, v)\)，如果满足\(d(s, u) = d(s, v)\)且\(d(s, u) + d(v, t) = d(s, t)\)就算上贡献即可得到答案。

这篇关于Codeforces Round #764 (Div. 3) 题解A-G的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！