某岛

… : "…アッカリ~ン . .. . " .. .
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)。。。