3月做题记录

Posted by WHZ0325 on 2023-03-22, Viewed times
【HAOI 2009】逆序对数列

看到 DP 的标签还挺好想的,用前缀和优化一下转移就可以 $O(n^2)$ 了,老年选手一开始把 $i$ 插入后最多产生的逆序对数错算成 $i$ 了(应该是 $i-1$ 嘛),WA 了一发……TAT

【HEOI 2015】兔子与樱花

退化了,看了以前的题解,每个点被删除的代价是它的樱花值与其没有没删除的子节点个数之和,当然删除一个子节点后父节点的代价除了要加上子节点的代价外还要减去这个子节点贡献给子节点个数的代价 $1$,每个节点被删去的奖励相同,那么就选所有子节点中代价最小的节点优先删去就好了。

【UVa 120】Stacks of Flapjacks

《入门经典》上的题,本来想练 Java 的结果不小心写了 C++,又用 Java 交了一发。

sscanf 中用 %n 获取偏移量,需要累加,fgets 用来读取整行。

【UVa 1605】Building for UN

用来练 Java,居然是多组数据……

【UVa 1152】Values whose Sum is 0

Java 写的,练 HashMap,注意最后一组数据结尾没有空行。

蓝桥杯 2022 省赛 A组

感觉自己确实老了,有点训练价值的两题写了题解,求逆元可以用 $x^{p-2}$ 快速幂求(模数为质数,欧拉定理),Java 递归层数多了会爆栈,并查集要用非递归写。

【HAOI 2008】 糖果传递

感觉可能在哪儿做过,$x_i$ 表示 $i$ 向左传递的糖果数,列出方程组,可以把问题转化为使数轴上若干点到 $x_1$ 距离和最小,即 $\sum |x_1+C_i|$ 的形式,这时 $x_1$ 应当取中位数。

【LG P1484】种树

可能是没见过的思路……用双向链表实现贪心的反悔操作,因为选择两边的点后距离为两边之外的相邻点不能选,与把包含两边点的整体作为一个点影响相同。

(还有长链剖分的做法,贪心的证明,需要补一份题解。)

【UVa 11134】Fabled Rocks

一开始想错了,按右端点排序后左端点顺序可能不定,所以应当从左往右一个一个尽可能地填,无法一一对应,话说是不是也可以用并查集优化……

【UVa 11054】Wine trading in Gergovia

水题,【HAOI 2008】糖果传递 弱化版。

Codeforces Round 860 (Div. 2)

最后一分钟交过了第四题,真刺激,虽然打得并不好……明天补题吧……

【CF 1798E】Multitest Generator

补题,写了题解。

【CF 1798F】Gifts from Grandfather Ahmed

没有见过的动态规划,写了题解。