传送门

https://codeforces.com/contest/1558

久违的 Tourist round…
因为 B 题没做出来，直接又跌成蓝名。。。

Problem B. Up the Strip

给定下面的递推公式：
$f(x) = \sum \limits_{y=1}^{x-1} f(x-y) + \sum \limits_{z=2}^{x} f(\lfloor \frac{x}{z} \rfloor)$
f(1) = 1，求 f(n)。

const int N = int(4e6) + 9;

Int f[N], s[N];
int n;

int main()
{

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n, MOD); f[n] = s[n] = 1;
    DWN(i, n, 1) {
        f[i] = s[i+1];
        //FOR_1(j, 2, i) f[i/j] += f[i];
        for (int j=2;i*j<=n;++j) {
            int l = i*j, r = min(n+1, l+j);
            f[i] += s[l]-s[r];
        }
        s[i] = s[i+1] + f[i];
    }

    cout << f[1] << endl;
}

非常 nice 的题。。个人非常喜欢。。。naive 的我只会类似数论分块的 sqrt 搞法。
但这个方法只能过 div2 的弱化版，比赛时华丽的 TLE 了。
正确的做法是考察相邻状态求和过程中的 diff，然后整块整块的处理。。

Problem C. Bottom-Tier Reversals

给定一个排列，每次你可以选一个前缀翻转，问是否能在 5n/2 步数内排序这个排列。
递归构造，分情况倒着讨论即可，发现恰好至多 5 步可以将规模减小 2，满足条件。

Problem D. Top-Notch Insertions

计数。问有多少长度为 n 的排列 ai，满足 ai 的值域为 [1,n] 且，对它执行插入排序时，插入的时刻和位置恰好时给定的 m 个操作。

假设不提供任何插入信息，那么任意构造一个长度为 n，值域为 [1, n] 的非严格单调递增序列都满足条件，方案数是经典的 C(2n+1,n)。
（证明，后面的每个数都多一个等号成立的影子状态，相当于给后面每个位置都累加 1，以保证每个数不相等，构造出从 2n+1 个数里选 n 个数的一一映射。）
那么如果出现了插入信息，会让一些位置的等号关系不成立，从而上面的影子状态变少，假设有 m 个等号不成立，答案就是 C(2n+1-m,n)。

但是提供的插入信息不一定一定会让 m+=1，有些信息是会重复的。
问题变为使用数据结构维护出等号不成立的位置即可。

标准做法是 Treap 或者 Splay 这种，可以支持在 kth 位置插入一个数的平衡树结构，注意需要动态离散化。复杂度 O(nlogn)。
Splay + 动态离散化（608ms）

当然也可以使用 rope 卡过去，复杂度 O(nsqrt(n))，使用 rope 的代码非常之短，就几行，而且似乎因为是奇妙的可持久化块状链表结构，甚至不需要动态离散化，
虽然 使用 rope 有可能会带来不幸，但是哪怕是用来对拍也比暴力要好写的多。。。

    Rush {
        r = r0; RD(n); int m = 0; Rush {
            int x, y; RD(x, y);
            if (r[y] == 0) {
                ++m;
                r.insert(y+1, 1);
            } else {
                r.insert(y, 0);
            }
            //REP(i, 10) cout << r[i]; cout <<endl;
        }
        cout << Binom(n+n-1-m, n) << endl;
    }

Rope（1965ms）

貌似还有一种做法是倒着做，此时每次插入的位置就是最终的位置，于是可以 树状数组 记录 Offset + 二分答案求 kth，复杂度 O(nlog2n)，实际跑得比平衡树要快。
树状数组(374ms)

Problem E. Down Below

图论题。给定一个 n 个点 m 条边的无向图。（无重边、无自环、联通）
你从 1 出发，每个其他点都有一个怪物，怪物有数值 ai 和 bi，当你到达 i 点时，你英雄的 power 必须要 > ai，怪物被消灭，然后 power += bi。
你不可以重复使用一条边。（访问后立刻返回）
问要消灭所有的怪物，英雄出发时所需的最少 power 时多少。
n <= 1000, m <= 2000

开始以为是双连通分量 + 树 dp。。。但是其实可以直接二分答案，然后迭代，每次用 bfs() 找环即可。
每找到一个环就把环上的点全加到可访问集合里。我们甚至不需要维护访问到每个点时的最大 power，因为如果需要 relax… 说明已经出现环了。
逻辑上这个可访问的集合实际上可以看作是被并查集合并在一起形成的一个 super node，实现上要讨论一下找到的环是在外部，还是首位都是这个 super node，虽然逻辑很简单，但比较容易写疵。

BFS 找环

Posted by xiaodao
Category: 日常