team2012-D3-2C

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 0031 ===
{{{
    先以P点为根dfs一遍求出所有割点，在求的过程中，维护两个变量：sum 和 lose
    sum是指整棵子树的权值和
    lose是指：如果该节点是割点，那么把它去掉之后，所有与根节点P不相连的子树的权值之和
    然后保护lose值最大的k个点，所以第k+1大的lose值即最后的答案
}}}

=== 0032 ===
{{{
首先在不考虑旋转的情况下，计算出一个长度为k的环中，相邻的点颜色不同的方案数：
f[0] = c, f[1] = 0, f[i] = f[i-1]*(c-2) + f[i-2]*(c-1)
然后仍然在不考虑旋转的情况下，计算出最多一组相邻顶点颜色相同的情况：
ans = f[n]+f[n-1]*n; // f[n]:相邻都不同  f[n-1]*n:枚举一对相邻顶点使其颜色相同
现在考虑旋转的情况：
构造一个1对n的关系： 最终的每个方案数对应于n个不计旋转的方案数（就是将其旋转1，2，。。。，n个位置）
遗憾的是可能旋转之后会发生重复，于是我们只需要加上这些重复的情况，最后除以n即可
    旋转等价：
    {{{
            for (int i = 1; i < n; ++i) { // rotate i position
                int z = gcd(n, i);
                ans = (ans + f[z]) % MOD;
            }
    }}}
    但是这样TLE了。。。
    于是换个方法： 枚举可能的gcd(n,i)，计算其个数，也就是欧拉函数，这个可以预处理
    {{{
        for (int k = 2; k <= n / 2; ++k) { // k=gcd(n,i)
            if (n % k == 0) { // 1 = gcd(n/k,i/k), cnt=euler(n/k);
                int cnt = euler[n / k];
                ans = (ans + cnt * f[k] % MOD) % MOD;
            }
        }
    }}}
}}}

=== 0034 ===
{{{
二分：
二分去买dishes的时间t，然后判断该情况下的happiness值
如果happy < P，说明去得太晚了
如果happy > Q，说明去得太早了
如果happy in [P, Q]，则符合要求，然后考虑怎样尽量减少耗费的时间：
    如果函数单调递增，说明越晚去等待的时间越长，因此应当尽早
    如果函数单调递减，说明越晚去越不用排队，因此应当尽量晚去
}}}

0031

 先以P点为根dfs一遍求出所有割点，在求的过程中，维护两个变量：sum 和 lose
    sum是指整棵子树的权值和
    lose是指：如果该节点是割点，那么把它去掉之后，所有与根节点P不相连的子树的权值之和
    然后保护lose值最大的k个点，所以第k+1大的lose值即最后的答案

0032

首先在不考虑旋转的情况下，计算出一个长度为k的环中，相邻的点颜色不同的方案数：
f[0] = c, f[1] = 0, f[i] = f[i-1]*(c-2) + f[i-2]*(c-1)
然后仍然在不考虑旋转的情况下，计算出最多一组相邻顶点颜色相同的情况：
ans = f[n]+f[n-1]*n; // f[n]:相邻都不同  f[n-1]*n:枚举一对相邻顶点使其颜色相同
现在考虑旋转的情况：
构造一个1对n的关系： 最终的每个方案数对应于n个不计旋转的方案数（就是将其旋转1，2，。。。，n个位置）
遗憾的是可能旋转之后会发生重复，于是我们只需要加上这些重复的情况，最后除以n即可
    旋转等价：
    {{{
            for (int i = 1; i < n; ++i) { // rotate i position
                int z = gcd(n, i);
                ans = (ans + f[z]) % MOD;
            }
    }}}
    但是这样TLE了。。。
    于是换个方法： 枚举可能的gcd(n,i)，计算其个数，也就是欧拉函数，这个可以预处理
    {{{
        for (int k = 2; k <= n / 2; ++k) { // k=gcd(n,i)
            if (n % k == 0) { // 1 = gcd(n/k,i/k), cnt=euler(n/k);
                int cnt = euler[n / k];
                ans = (ans + cnt * f[k] % MOD) % MOD;
            }
        }
    }}}

0034

二分：
二分去买dishes的时间t，然后判断该情况下的happiness值
如果happy < P，说明去得太晚了
如果happy > Q，说明去得太早了
如果happy in [P, Q]，则符合要求，然后考虑怎样尽量减少耗费的时间：
    如果函数单调递增，说明越晚去等待的时间越长，因此应当尽早
    如果函数单调递减，说明越晚去越不用排队，因此应当尽量晚去