BZOJ5093:[Lydsy1711月赛]图的价值 – 题解

主要思路

算是个简单题吧。

首先列个暴力式子:

\[ \sum_G \sum_{i = 1}^n d_i^k \]

发现很不现实。我们考虑把点拆开来考虑,因为全集里面可以直接独立的来算。考虑某个点度数为 \(x\) 的方案数,就变成了:

\[ n \sum_{x = 0}^{n – 1} x^k f(x) \]

其中 \(f(x)\) 代表的是一个图某个点的度数为 \(x\) 的方案数。其实稍微思考下就知道,我们可以把这个点剥离出来,强制连边之后再生成一个图即可:

\[ \begin{aligned} f(x) &= {n – 1 \choose x} 2^{n – 1 \choose 2} \\ ans &= n \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} 2^{n – 1 \choose 2} \\ &= n2^{n – 1 \choose 2} \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} \end{aligned} \]

继续阅读BZOJ5093:[Lydsy1711月赛]图的价值 – 题解

「USACO 2018.12 Platinum」解题报告

A – The Cow Gathering

首先,如果没有限制的话,其实从叶子结点来抽是一定有解的,可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边,初步思考可以把每个点都作为最后一个节点,然后来看新的图有没有环,这样是 \(\Theta(n^2)\)。

继续阅读「USACO 2018.12 Platinum」解题报告

BZOJ4361:isn 题解

解法

这道题很有意思。首先搞一个 \(DP\) 来算出不同长度的不降子序列的个数,方程为:

\[ f[i, j] = \sum_{k < i, a_k \leq a_i} f[k, j – 1] \]

发现可以用树状数组优化,所以这里的复杂度为\(O(n^2 \log n)\)。设\(g[i] = \sum_{i = 1} f[i, n]\),考虑对答案的贡献。对于一个\(i\),有\(g[i] * (n – i)!\)种方案做变换,但是考虑这\((n – i)!\)中包含了提前变换完成的可能,也就是在我们从合法序列中删去了合法元素的可能,这样肯定是不行的。考虑进行容斥,贡献就是\(g[i](n-i)! – g[i+1](n – i – 1)!(i + 1)\),表示在这些里选择\(i+1\)个合法元素的方案。

继续阅读BZOJ4361:isn 题解

P2154:[SDOI2009]虔诚的墓主人题解

解法

这道题很有意思啊。如果暴力枚举,答案式子:

\[ans = \sum_{x}^n \sum_{y}^m {up_{x,y} \choose k} {left_{x,y} \choose k} {right_{x,y} \choose k} {down_{x,y} \choose k}\]

其中\(up, left, right, down\)代表上下左右的常青树棵树。如何降低复杂度?

首先,我们可以考虑进行离散化:上下左右只要有为\(0\)的情况是不可能对答案有贡献的。然后,发现空隙中上下的部分:

继续阅读P2154:[SDOI2009]虔诚的墓主人题解

[Fortuna OJ]Mar 4th – Group A 解题报告

A – 漆黑列车载运数个谎言

这道题应该是并查集域的裸题,不讲。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    while (m--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0)
            unite(x, y), unite(x + n, y + n);
        else if (opt == 1 || opt == 2)
            unite(x, y + n), unite(x + n, y);
        else if (find(x) == find(y) || find(x + n) == find(y + n))
            puts("1");
        else
            puts("0");
    }
    return 0;
}

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