传送门
https://codeforces.com/blog/entry/97795
https://zhuanlan.zhihu.com/p/444714636
Table of Contents
这场因为出原题被喷惨了。。。
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)。。。
