当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

分类 题解 下的文章

并不会正解,此处讲一个可以过此题(而且跑的飞快)的做法。

考虑直接分块,如果对每个块开个 bitset ,这样合并(如果觉得解释的不是很清楚可以点击阅读全文看完整代码 qwq:

void solve(int l, int r) {
    if (bln[l] == bln[r]) {
        for (register int i = l; i <= r; i++)
            ans.set(a[i]);
    } else {
        for (register int i = l; i < fst[bln[l] + 1]; i++)
            ans.set(a[i]);
        for (register int i = fst[bln[r]]; i <= r; i++)
            ans.set(a[i]);
        for (register int i = bln[l] + 1; i <= bln[r] - 1; i++)
            ans |= f[i];
    }
}

如果块大小为 \sqrt n ,那么实际上的复杂度是 \frac {n ^ 2 \sqrt n}{64},复杂度其实和暴力差不多。

Dilute: 我™写了个(假)正解分还和暴力一样。

在不会正解的情况下,显然只能考虑在优化分块上做文章。同学基本都是调整块大小为 7000 左右 + 奇技淫巧的卡常通过,此处讲一个不太一样的做法:

考虑使我们的复杂度变的不正确的部分:

    for (register int i = bln[l] + 1; i <= bln[r] - 1; i++)
        ans |= f[i];

由于最多会访问到 \sqrt n 个块,复杂度就不能保证。考虑处理出一个 pre[i][j] 数组,表示std::bitset <N> f[i]std::bitset <N> f[i + j - 1] 的异或和。由于空间限制只有 8MB ,我们只能开约 480std::bitset <N> ,就分成 80 个块,预处理的 j18 即可。

我们的 txc 哥哥还给了一个非常优秀的常数优化:如果一个数在整个序列里只出现了一次,那么他只要在区间内,对答案的贡献肯定为 1(不会因为出现和自己值相同的数而减少)。前缀和处理即可,理论可以少掉一半的常数,Orz.

READ MORE

按题意可知,考虑每个节点会给左孩子带来一个 (-\infty, a_i ) 的限制,会给右孩子带来一个 (a_i, +\infty) 的限制。 定义限制 (-\infty, a_i) 的限制取反为 (a_i, +\infty) ,反之亦然。

考虑把原树进行树链剖分。每个节点存放自己给重儿子带来的限制,用支持单点修改、区间取反、区间查询的线段树维护区间限制的并集。由于每个节点往上跳只会经过 \log n 条重链,重链内部直接从线段树上查询,两条重链之间的转移把转折点对重儿子的限制取反即可。总复杂度为 O(n \log ^ 2 n),可以通过此题。

READ MORE

非常妙的一道状压题。

考虑依次加入每一个点,状态之间的转移和对答案的贡献只与每个深度的节点个数,因此我们可以这样定义状态:把这棵树的节点按深度排序,显然相邻两个的深度最多相差一,如果差等于一,状压出的对应位就是 1 ,否则就是 0 。利用这个即可进行 O(2^n \times n ^ 2) 的转移。

还有一种 O(n ^ 3) 的天顶星写法,但是我暂时不会,只能等以后补锅。

READ MORE

询问树上路径第 k 大:二分答案 + 树上查询。查询时用主席树差分:

tree[now] = tree[u] + tree[v] - tree[lca(u,v)] - tree[father(lca(u,v))]

时间复杂度 O(n \log ^2 n)

READ MORE

由于每个门只会被两个钥匙控制,那么两个钥匙的选或不选就能建立起一种对应关系。即如果门本来是开着的,那么用了一把必须用另一把,不用一把必须不用另一把;如果们本来是开着的,那么不用一把必须用另一把,用了一把必须不用另一把。

Tarjan 跑 2-SAT 随手切,注意 nm 不要搞反。

READ MORE

到这题为止网络流 24 题也快刷完了呢,还剩下几道码量特大的等着以后有空去浪费时间(逃

这题一眼最小费用最大流,一开始我想了个类似于 NOI2008 志愿者招募 之类的利用满流的方法,但是一直没有调出来。后来怂了,直接连边,最后因为有个 - 1 没有删干净还是调了老半天。orz ,我还是太菜了。

把每一天分成两个节点,一个接受干净的毛巾,一个输出用过的毛巾。直接在这两个点之间连边显然不现实,我们可以分别把这两个点和源点、汇点连边。然后再按照题目条件一一连上对应边。这样最大流肯定能够跑满,求最小费用的话就是这图的最小费用最大流了。

这告诉我们对于不清楚的知识点不要瞎用。

READ MORE

题意:

给你个 1000 \times 1000 的矩阵,每次交换任意两个不重合的子矩阵,求最后的结果

如果你是一位数据结构学傻的选手(像我),那么第一感觉肯定是用平衡树做,复杂度 O(m \times n \log n) ,不过不幸的是,由于常数巨大,最后得分甚至可能不如暴力的 memcpy

如果你是一个不会高级数据结构的普及选手你说不定就能想到链表。维护一个矩形的链表,然后每次交换就分别把两块矩阵取出再拼接上去。

READ MORE

巧妙的使用满流的特性解决问题。

对每一天,连一条容量为 INF - 需求人数 的边,对于补充的人连一条容量为 INF ,花费为价格的边。

对这个图跑最小费用最大流,其中最大流一定是 INF ,最小费用即答案。

READ MORE