最近文章

[Fortuna OJ]4605 – 排序 sort 题解

主要思路

这道题好有意思啊,提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。

我们可以先二分出\(c\)位置的值,然后令所有大于等于\(c\)的值变成\(1\),小于的则变成\(0\)。然后排序的时候发现,其实就是重新组织零一的位置,所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。

继续阅读[Fortuna OJ]4605 – 排序 sort 题解

「2018泉州国庆集训#3」 – 解题报告

A – 人类基因组

这套题全都是暴力出奇迹系列。

我们枚举一个端点,然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\),然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。

然后用 sb 线段树搞下就行了,太特么傻逼了。

继续阅读「2018泉州国庆集训#3」 – 解题报告

[Fortuna OJ]6352 – 给(ca)题解

主要思路

首先,叶子结点为\(k\)时,整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。

考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点,且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移:

\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]

向新的节点加入统计数据:多了一个叶子结点,要么向左走,加深当前的路径;要么补上最后一个向左走的右节点。

然后就可以写代码了。

继续阅读[Fortuna OJ]6352 – 给(ca)题解

CF1206D:Shortest Path 题解

主要思路

刚开始以为是搞\(\log n\)个基底点,然后双向边上面做事情,最后发现找图上最小环的复杂度非常的高。所以 GG。

正解考虑把问题的规模进行缩小:也就是把一些答案预先特判掉。比如说,如果某一个位上有超过三个点连接,那么环的大小就可以被确定为是\(3\),也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。

再考虑剩下的情况。此时,\(n\)已经缩小了很多,所以我们暴力建图,用 Floyd 跑最小环即可。

继续阅读CF1206D:Shortest Path 题解