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

December 17, 2021

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个正整数a1,⋯,an，求满足下面条件的数组b的个数

1≤bi≤ai
bi≠bi–1,i∈[1,n–1]

第一感觉是 DP 优化。。。但是如果状态设计成 f[][] 好像就走进死胡同了。。题解说要笛卡尔树。。不过不会也能做。。
状态设计成 f[]，然后应用容斥原理，枚举后缀有多少连续相等的数字。。这样可以得到一个 O(n2) 的 dp，已经成功了一大半。。。
考虑 dp 优化。。可以用单调栈和部分和漂亮的优化到 O(n)。。。

Posted by xiaodao
Category: 日常

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