Codeforces Round 867 (Div 3) 总结

文章首发于我的个人博客：欢迎大佬们来逛逛

Dashboard - Codeforces Round 867 (Div. 3) - Codeforces

A

题目大意：有n个电视节目，每个电视节目占据一定的时间，并且具有一个娱乐值，一秒可以额换一次台，你需要在规定的时间内找出最大娱乐值的电视节目。（一个电视节目必须看完，意味着你的剩余时间必须大于这个电视节目的时间）

我们可以将自己的规定时间与电视节目进行枚举，相当于每次进行一次换台，如果我们的剩余时间大于电视节目所占据的时间，则每次记录一下娱乐值的最大值。

---

B

题目大意：给出一个序列，你可以任意删除其中的元素，规定序列中的最美值为序列中相邻两个元素的乘积的最大值，找出整个序列中的最美值。

由于可以删除元素，则我们就可以认为元素之间是无序的，因此我们可以进行排序，从小到大，然后进行遍历相邻两元素乘积最大值即可。

---

C

题目大意：在一个 n*n 的图形中，找出整个图形（包括内部和外部）的线的总长，每一段线长 1。

这是一道规律题：

• n=4：容易得到 15 + 3 + 2*4 为 26
• n=5：容易得到 24 + 3 + 2*5 为 37
• n=6：容易得到 35 + 3 + 2*6 为 50

因此公式为：

$$ans=n\ast n-1+3+2\ast n$$

---

D

题目大意：寻找超级排列，所谓超级排列是指从 1到n 每个元素只出现一次，不能不出现，也不能重复出现。规定 b数组为 a数组的前缀和数组%n，如果 b数组为超级排列，那么a数组也是超级排列。因此给你一个 n，判断这个n能否构成一个超级排列。

• 如果n是奇数，那么n的前缀和数组的最后一项一定是 n的倍数，同理 n-1项也一定是n的倍数
  • 例如：n=5： s = 1 3 6 10 15；则 10与15都是n的倍数，因此%n都为0，所以不是超级排列
  • n=1除外
• 如果n是偶数，则不妨找规律：
  • n=6： 6 5 2 3 4 1，可以看作 n n-1 （n-1）。其中前两项是固定的，往后每两项都需要组成一个 n-1 ，因此 2+3 =5；4+1 =5，可以算出这样的排列一定是超级排列。
  • 第三项开始枚举 2 4 6 …. 对应为 n-1-2 n-1-4 n-1-6

---

E

题目大意：一个字符串，你可以交换任意两个位置元素，使得这个字符串每一个字符位置都不回文，即s[i] ≠ s[n-i-1] (i≥0) ，求出是否可以经过操作得到，输出交换次数，否则输出 -1

• 无解：
  • 观察到奇数个数得字符一定是无解的，因为会多一个字符无法匹配。
  • 如果一个字符出现次数大于数组总长度的一半，则一定会出现一半全是这个字符，另一半至少出现一个这个字符，因此一定有重复，无解。
• 有解：
  • 左半边记录不满足条件时的该元素出现的次数，相邻两个元素可以进行一次交换，因此抵消为一次，直到记录的不满足条件的元素的次数为0，使用multiset维护很方便！