首先第一天切完了6道水题，然后剩下的题都不会。然后被某大爷训斥了。

第二天听从了训斥切掉了QSTRING，然后发现TRIPS[tex]O(n^2)[/tex]可过就切掉了。

第三天想了一上午发现点分+虚树可做就花了一下午切掉了。

然后就开始颓了。。。

n天以后发现有个小哥的challenge把大多数人艹翻了，就想了个鬼畜的做法把他艹了。

过了两天发现瞬间5个人AK了。然后感觉人生没有什么希望了。

最后一天发现challenge又被刷飞了。。。然后改了一个bug暂时碾掉了朝鲜哥。

然后中午的时候发现朝鲜哥的BTREE已经进入TLE阶段，然后challenge也被碾回来了。然后感觉他要AK了。。。然后稍微改了一下发现这做法好像优化不了了就弃疗打游戏去了。

晚饭回来看到朝鲜哥rank1的好消息可喜可贺。

以下是题解：

SEATSR [tex]O(n^2)[/tex]DP肯定都会，然后DP的时候只记录[tex]|i-j|\leq 100[/tex]的就行了。

QSTRING 后缀数组后相邻两个串之间的距离就是串长-h[i]，然后查询串的时候找到最早出现的位置，查询位置的时候二分出串在后缀数组中的位置就好了。

TRIPS 压8位[tex]O(n^2)[/tex]直接艹。或者可以分情况：步长大于[tex]\sqrt n[/tex]暴力二分下一个点，小的直接打倍增表（感觉不会比暴力快多少）

BTREE 首先假如询问都只有一个点可以点分求出来。假如有多个点先建出虚树然后考虑相邻的点：假如一个点没有完全覆盖另一个点那么就可以减掉重叠部分，这可以通过加一个询问来做到。假如完全覆盖了那么就要把小的那个替换成覆盖后的再去更新其他的。所以刚开始先BFS一遍把每个点变成需要更新的最大点就可以了。

CHEFPNT 我的做法大概是先全用横的，然后每次找一条能使涂得次数变少最多的竖的把它变成竖的，然后找一下有没有环，假如有环就不改。但是这样还是比较萎所以就把k条k条地改（就是一次把一个矩阵全部变成竖的）也枚举进来，然后就很厉害了。用最大子段和优化一下就[tex]O(n^2)[/tex]了。不过rank1小哥的代码里好像有最大流。。。感觉很厉害。。。

• 相关文章
• 全局相关文章