文章首發(fā)于我的個人博客：歡迎大佬們來逛逛

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

A

題目大意：有n個電視節(jié)目，每個電視節(jié)目占據(jù)一定的時間，并且具有一個娛樂值，一秒可以額換一次臺，你需要在規(guī)定的時間內(nèi)找出最大娛樂值的電視節(jié)目。（一個電視節(jié)目必須看完，意味著你的剩余時間必須大于這個電視節(jié)目的時間）

我們可以將自己的規(guī)定時間與電視節(jié)目進(jìn)行枚舉，相當(dāng)于每次進(jìn)行一次換臺，如果我們的剩余時間大于電視節(jié)目所占據(jù)的時間，則每次記錄一下娛樂值的最大值。

---

B

題目大意：給出一個序列，你可以任意刪除其中的元素，規(guī)定序列中的最美值為序列中相鄰兩個元素的乘積的最大值，找出整個序列中的最美值。

由于可以刪除元素，則我們就可以認(rèn)為元素之間是無序的，因此我們可以進(jìn)行排序，從小到大，然后進(jìn)行遍歷相鄰兩元素乘積最大值即可。

---

C

題目大意：在一個 n*n 的圖形中，找出整個圖形（包括內(nèi)部和外部）的線的總長，每一段線長 1。

這是一道規(guī)律題：

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

因此公式為：

$$ans=n?n?1+3+2?n$$

---

D

題目大意：尋找超級排列，所謂超級排列是指從 1到n 每個元素只出現(xiàn)一次，不能不出現(xiàn)，也不能重復(fù)出現(xiàn)。規(guī)定 b數(shù)組為 a數(shù)組的前綴和數(shù)組%n，如果 b數(shù)組為超級排列，那么a數(shù)組也是超級排列。因此給你一個 n，判斷這個n能否構(gòu)成一個超級排列。

• 如果n是奇數(shù)，那么n的前綴和數(shù)組的最后一項(xiàng)一定是 n的倍數(shù)，同理 n-1項(xiàng)也一定是n的倍數(shù)
  • 例如：n=5： s = 1 3 6 10 15；則 10與15都是n的倍數(shù)，因此%n都為0，所以不是超級排列
  • n=1除外
• 如果n是偶數(shù)，則不妨找規(guī)律：
  • n=6： 6 5 2 3 4 1，可以看作 n n-1 （n-1）。其中前兩項(xiàng)是固定的，往后每兩項(xiàng)都需要組成一個 n-1 ，因此 2+3 =5；4+1 =5，可以算出這樣的排列一定是超級排列。
  • 第三項(xiàng)開始枚舉 2 4 6 …. 對應(yīng)為 n-1-2 n-1-4 n-1-6

---

E

題目大意：一個字符串，你可以交換任意兩個位置元素，使得這個字符串每一個字符位置都不回文，即s[i] ≠ s[n-i-1] (i≥0) ，求出是否可以經(jīng)過操作得到，輸出交換次數(shù)，否則輸出 -1

• 無解：
  • 觀察到奇數(shù)個數(shù)得字符一定是無解的，因?yàn)闀嘁粋€字符無法匹配。
  • 如果一個字符出現(xiàn)次數(shù)大于數(shù)組總長度的一半，則一定會出現(xiàn)一半全是這個字符，另一半至少出現(xiàn)一個這個字符，因此一定有重復(fù)，無解。
• 有解：
  • 左半邊記錄不滿足條件時的該元素出現(xiàn)的次數(shù)，相鄰兩個元素可以進(jìn)行一次交換，因此抵消為一次，直到記錄的不滿足條件的元素的次數(shù)為0，使用multiset維護(hù)很方便！