Codeforces刷题笔记-----好题大杂烩

​​​​​​​​​​​​​​​​

C. Sequence Pair Weight

题目大意
给定a,b两个数组，可选择a的子数组进行至多一次的翻转操作，使得${\sum }_{i=1}^n{a}_i\ast b_i$最大

题解

暴力做法：$O(n^3)$,枚举每个区间并进行翻转操作求和的最小值

优化：通过枚举区间$[l,r]$的中心,然后由中心进行$[l-1,r+1]$的拓展，可知每次拓展其区间乘积的和都增加$a_l\ast b_r+a_r\ast b_l$，枚举中心的复杂度为$O(N)$,拓展的复杂度为$O(N)$，因此优化后的复杂度为$O(N^2)$。

D. Maximum Sum of Products

题意

给定n支队伍，每两支队伍都会进行一场比赛，比赛胜利者得3分，失败者不得分，平局各得一分。构造每场比赛的胜负，使得平局数最小的情况下每支队伍的最终得分相同。

题解

此题解法的巧妙之处在于其模型的构造：给每两支队伍之间都连接一条边，表示它们之间会进行一场比赛，建完图后我们可以很容易的发现，当n为奇数时，每支队伍都连有偶数条边，那么我们可以在没有任何平局的情况下解决问题：每支球队应该准确地赢得 $\lfloor n/2\rfloor$场比赛并输掉相同数量的比赛。当n为偶数时，每支队伍都连有奇数条边，此时我们可以通过一些平局操作删去一些边，使得每支队伍剩余的边的数量仍为偶数条，然后再按照n为奇数的情况处理即可。
C. Minimum Ties