去某地方打了打酱油。。应机房同学的要(wei)求(bi)来写写题解。。根据我的估计,反正也没人看。。

arthur

题目大意

张卡牌,每张卡牌有一个攻击力和发动概率,一个游戏总共有轮,每一轮从1到考虑每张卡牌,若这张卡牌已经发动,则无视;否则以的概率发动,若发动则结束该轮,不发动则跳过这张牌。求这个游戏造成的期望伤害。有组数据。

思路

BZOJ上是什么鬼。。极其怀疑没有spj。。
首先,让我们来orz cyb(半小时AK HNOI)。。
由于期望的可加性,我们可以分解这个期望,所以现在模型转为求每张牌发动的概率。由于是对于每张牌,所以第几轮就不重要了,重要的只是它是否在某一轮发动了。
这个想法给了我们一个dp的思路,不妨再次抽出一个模型:一开始有次机会,然后一次考虑每个人,对于每次机会,有的概率给这个人,如果某次机会给了这个人,就跳过这个人,然后总的机会数目-1。求每个人分到一个机会的概率。
那么就可以令表示考虑完第个人还剩次机会的概率,初值是,转移就是转移到表示没有一次机会给这个人;以转移到。然后就可以顺便算出每张牌发动的概率。预处理之后的复杂度是

fruit

题目大意

给一棵树和树上条路径,每条路劲有一个权值。有若干组询问,每组询问给定一个路径,询问之前所有的条路径中,是路径的子路径的那些路径的第小权值。允许离线

思路

跪求在线算法(出题人忘了强制在线?)。。好吧已经有人告诉我了。。orz。。
小值的一个经典的离线算法就是整体二分,考虑二分一个答案,然后把条路径中所有权值比小的路径搞出来,那么对于每组询问就是询问这条路径包含了多少刚才搞出来的路径。随便选一个根,如果一条路径包含了另外一条给定的路径,那么这条路径的端点受到的限制一定形如:一定在某棵子树内或者一定不在某棵子树内。这两种限制在dfs序上都对应着一些区间,而由于是两个端点所以是二维的。所以我们可以把给出的条路径视为矩形,把询问视为点,现在问题变为:给定平面上一些点和一些矩形,统计每个点在多少个矩形内部。允许离线。应该是一个比较经典的扫描线。于是问题就在的时间内解决了。

dishes

题目大意

给出若干个限制,需要求一个排列。每个限制形如在排列中必须满足出现在的前面。要求求出的那个排列满足所有的限制,并最小化1的出现位置,在此基础上最小化2的出现位置,以此类推。

思路

乍一看很像一个贪心的水题,但是仔细一想发现这个贪心并不好做。如果我们要取出1,就要先取出1的所有前驱,然后一路取,这样模拟的复杂度是的,对于100000这样的数据显然无能为力。
我们虽然不能够快速地知道第一个数字该填什么,但是我们知道最后一个数字该填什么,所有没有出边的点就是有可能的最后一个数字。而根据之前的规则,显然应该选最大的!然后倒着用堆维护这个序列就好了。复杂度是

maple

题目大意

给一个DAG,保证1号点没有入边。现在在这个DAG中加入一条没有出现过的边,这是这个有向图可能就不是一个DAG了,需要求出这个有向图以1为根的树形图个数。模

思路

如果是一个DAG,它的树形图个数是比较好求的。直接把所有除1号点以外的点的入度乘起来就好了。因为给每个点选了一个入边,这些边不会成环,就一定是一个树形图。
我们不妨对新的图先把入度的乘积算出来,可能会算重。因为如果不考虑新加的边,树形图中存在一条从的路径,而的前驱又恰好是,那么这个时候是会得到一个环的,也就不是一个合法的树形图了。
刚才的分析意味着我们找到包含路径的树形图然后减掉就好了。如果我们强制要求一条路径上的点的入边只能有一种选择,那么这个限制下总的树形图个数就是,其中表示各个点入度的乘积。由于模数是个质数,所以可以显然地变为乘以逆元。然后使用dp就可以得到所有这样的树形图的和了,具体来说就是表示从的所有路径的对应树形图个数和,转移比较显然。

shop

题目大意

给一棵树,每个点有一个点权,每条边有一个边权。有若干组询问,每组询问给定三个参数,表示询问所有权值在区间之间的点到点的路径的权值和。一条路径的权值定义为这条路径上的边权和。强制在线

思路

czh好像有一个什么树链剖分+主席树的搞法跑得飞快的。我写的还是一个比较平常的动态边分治。
和qtree4一样的思想,我们维护一个边分治的结构,和点相关的结构就只有个。由于度数很小所以直接边分治就可以了。对于每个结构需要维护前缀和,表示权值小于等于的点到该结构的根的距离和,然后就可以在的时间内完成一次询问。预处理由于要排序所以是的。

pairwise

题目大意

给出一个森林,所有的树都是有根树,我们需要对这样的序列进行计数:1.满足所有的点出现恰好一次;2.任意两个相邻点之间可以填小于号或者等于号;3.对于森林中每一对父子关系,在这个序列中满足
求这样的序列个数,相等的元素如果交换位置算同一个序列。比如是同一个序列。模

思路

这个题目考试的时候简直毫无思路。。暴力都不会。。
首先把这个森林加个根搞成一棵树,对于所有没有祖孙关系的子树它们是独立的。
这个dp状态还是比较难想。。令表示把子树中所有点排成一个合法序列的方案数,这个序列中有个小于号(就是分成段的方案数)。现在的问题在于转移,即合并的两个子树。还是枚举表示中分了段,中分了段,中分了段,然后用更新。首先肯定有,其次可以想象一个有个空位的槽,现在有个无区别的红球,个无区别的黑球,要把这些球放到这个空位里面去,每个空位不能放一样的球,每个空位至少有一个球。这个模型的方案数明显是。所以这个就是转移系数啦。。就是。然后把根的dp值加起来就是答案了。看起来是的,但是。。跑的飞快。。而且绝对不会达到这个上限。

贴个代码。。数据不合法什么的就不管了。。

pairwise.cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 100, mod = (int)1e9 + 7;
typedef int arr[N + 10];

int n, m, tot, cnt, j, k, cm;
arr g, ufs, valid, edge[2], pt, nt, id, dp[N + 10], sz, c[N + 10], tdp;
char eqt[3];
bool ch[N + 10][N + 10], v[N + 10];

int Find(int x) { return ufs[x] ? ufs[x] = Find(ufs[x]) : x; }

void Merge(int x, int y) {
    x = Find(x), y = Find(y);
    if (x != y) ufs[x] = y;
}

void Link(int x, int y) {
    pt[++tot] = y, nt[tot] = g[x], g[x] = tot;
}

void Getvalidstatus() {
    for (int i = 1; i <= n; ++i) {
        int x = Find(i);
        if (!v[x]) v[x] = 1, valid[++cnt] = x, id[x] = cnt;
    }
    memset(v, 0, sizeof(v));
    for (int i = 1; i <= cm; ++i) {
        int x = Find(edge[0][i]), y = Find(edge[1][i]);
        if (x == y) { printf("0\n"); exit(0); }
        if (!ch[x][y]) Link(id[x], id[y]), ch[x][y] = 0, v[y] = 1;
    }
    for (int i = 1; i <= cnt; ++i) if (!v[valid[i]]) Link(cnt + 1, i);
    c[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
}

void Dp(int x) {
    int chs = 0; sz[x] = 0;
    for (int e = g[x]; e; e = nt[e]) {
        int p = pt[e];
        if (v[p]) { printf("0\n"); exit(0); }
        Dp(p);
        int s1 = sz[x], s2 = sz[p]; sz[x] += sz[p], ++chs;
        if (chs == 1) {
            for (int i = 1; i <= s2; ++i) dp[x][i] = dp[p][i];
            continue;
        }
        for (int i = 1; i <= s1 + s2; ++i) tdp[i] = 0;
        for (int j = 1; j <= s1; ++j) {
            for (int k = 1; k <= s2; ++k) {
                if (!dp[x][j] || !dp[p][k]) continue;
                for (int i = max(j, k); i <= j + k; ++i) {
                    (tdp[i] += (ll)c[i][k] * (ll)c[k][i - j] % mod * (ll)dp[x][j] % mod * (ll)dp[p][k] % mod) %= mod;
                }
            }
        }
        for (int i = 1; i <= sz[x]; ++i) dp[x][i] = tdp[i];
    }
    for (int i = sz[x] + 1; i >= 1; --i) dp[x][i] = dp[x][i - 1];
    ++sz[x];
    if (sz[x] == 1 && x != cnt + 1) dp[x][1] = 1;
}

int main() {
    freopen("pairwise.in", "r", stdin);
    freopen("pairwise.out", "w", stdout);

    scanf("%d%d\n", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%s%d\n", &j, eqt + 1, &k);
        if (eqt[1] == '=') Merge(j, k);
        else edge[0][++cm] = j, edge[1][cm] = k;
    }

    Getvalidstatus();
    memset(v, 0, sizeof(v));
    Dp(cnt + 1);

    int ans = 0;
    for (int i = 1; i <= sz[cnt + 1]; ++i) (ans += dp[cnt + 1][i]) %= mod;
    printf("%d\n", ans);
    return 0;
}