某島

… : "…アッカリ~ン . .. . " .. .
December 17, 2021

Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3)

傳送門

https://codeforces.com/blog/entry/97795
https://zhuanlan.zhihu.com/p/444714636

這場因為出原題被噴慘了。。。

Problem C : https://po.kattis.com/problems/biblioteket
Problem D : https://open.kattis.com/problems/bread | https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0448
Problem F : https://atcoder.jp/contests/arc115/tasks/arc115_e

特別是 F 題的影響最為嚴重。。。(但是我覺得這個 F 題真的是一個好題啊。。。

Problem D. Yet Another Sorting Problem

給定要給數組。可以對數組進行操作,每次選擇三個不同的下標(i, j, k)。
交換這三個位置的數。a[i]移動到a[j],a[j]移動到a[k],a[k]移動到a[i]。
問能不能通過若干次操作,讓數組有序(非減)。

尋找 invariant 。。。似乎這個三元交換操作不改變逆序對的奇偶性。。
猜想逆序對是偶數一定有解。。。

交了一發上去 WA 了。。。
最後發現沒考慮相等的數。。

如果有相等的數,那麼一定有解,因為可以拿這個數充當緩存區= =。。

Problem E. Frequency Queries

給定一棵n節點的樹,樹上每個節點有一個數字(範圍1~n)。有q個查詢,每個查詢給出三個數 v, l, k。
問節點v到根的(最短)路徑上的所有數字,出現次數大於等於l次的數字中,出現次數排第k的是什麼?(可能有出現次數相同的,這時候輸出任意都可)

離線樹狀數組 + 二分查找。。挺無聊的題。。

Problem F. Non-equal Neighbours

給定n個正整數$a_1,\cdots,a_n$,求滿足下麵條件的數組$b$的個數

  • $1\le b_i \le a_i$
  • $b_i \ne b_{i – 1}, i\in [1, n – 1]$

第一感覺是 DP 優化。。。但是如果狀態設計成 f[][] 好像就走進死胡同了。。題解說要笛卡爾樹。。不過不會也能做。。
狀態設計成 f[],然後應用容斥原理,枚舉後綴有多少連續相等的數字。。這樣可以得到一個 O(n2) 的 dp,已經成功了一大半。。。
考慮 dp 優化。。可以用單調棧和部分和漂亮的優化到 O(n)。。。