Educational Codeforces Round 111 (Rated for Div. 2) D. Excellent Arrays

本文主要是介绍Educational Codeforces Round 111 (Rated for Div. 2) D. Excellent Arrays，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接：https://codeforces.com/contest/1550/problem/D

分析：

引入图论，1~n为点，当ai+aj=i+j时，在i和j之间连一条边；要满足ai!=i，只需要不存在奇圈；要使边数最多，即构造点集大小相差为0或1的完全二部图；

初始时，令ai=i

对k = 1, 2, ...，令二部图里一个部分里的所有数+k，另一个部分里所有数-k，直到这个部分里出现超过[l,r]范围的数；

显然，上述过程的终止只与每个部分里的min和max有关；

于是，我们枚举二分图每个部分里的min和max，计算这种情况下+k和-k分别能到多少，累加起来乘上满足这个min和max限制的二分图的个数；

更进一步，我们可以枚举max-min，复杂度O(n)

这篇关于Educational Codeforces Round 111 (Rated for Div. 2) D. Excellent Arrays的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！