「杂题集」- 2019年9月19日

方格取数

看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。

继续阅读「杂题集」- 2019年9月19日

[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」 – 解题报告

Educational Codeforces Round 72 Div. 2 解题报告 (CF1217)

C – The Number Of Good Substrings

这道题比较傻逼。

考虑记录上一个最近的\(1\)的位置\(nxt_i\),然后显然的是:如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间,那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。

继续阅读Educational Codeforces Round 72 Div. 2 解题报告 (CF1217)

P4556:[Vani有约会]雨天的尾巴题解

主要思路

这道题可以离线回答,很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息,然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG,但是我们可以动态开点,然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的,这样空间就可以接受的了。

既然有了很好用的动态开点线段树,我们就可以用树上差分那一套路,在端点和\(LCA\)处打标记,然后考虑从下往上合并答案。合并可以用线段树合并,复杂度为重合部分,差不多就是\(O(\log n)\)。然后就没了,很傻逼的一道题。

继续阅读P4556:[Vani有约会]雨天的尾巴题解

[Fortuna OJ]Aug 12th – Group A 解题报告

A – 迷宫

这道题挺好的,让我知道了线段树还有这样的操作。

考虑线段树维护一段区间行入口到行出口的最短路,大概的维护方法非常像 Floyd。也没啥好说的,看代码吧。

继续阅读[Fortuna OJ]Aug 12th – Group A 解题报告