模拟赛 - NOI 模拟七

2016.01.11 11:11 Mon| 10 visits oi_2016| 2016_竞赛日常| Text

BZOJ3640 JC的小苹果

发现 hp 让原图变成了一个分层图。正常每一层都需要用高斯消元求出来对于每一个安全的节点,它的概率是周围点的概率除度数。然而发现高斯消元可以预处理,求个逆矩阵就好了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

#define N 155

int n, m, hp, a[N], out[N], mp[N][N];
double d[N][N], num[N][N], temp[N], f[10005][N], ans;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void gauss()
{
    for (int i = 1; i <= n; ++i)
    {
        int t = 0;
        for (int j = i; j <= n; ++j)
            if (fabs(d[j][i]) > 1e-10) { t = j; break; }
        for (int j = 1; j <= n; ++j)
            swap(d[i][j], d[t][j]), swap(num[i][j], num[t][j]);
        double tt = d[i][i];
        for (int j = 1; j <= n; ++j)
            d[i][j] /= tt, num[i][j] /= tt;
        for (int j = 1; j <= n; ++j)
        {
            if (j == i) continue;
            tt = d[j][i];
            for (int k = 1; k <= n; ++k)
                d[j][k] -= tt * d[i][k], num[j][k] -= tt * num[i][k];
        }
    }
}

int main()
{
    cin >> n >> m >> hp;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int x, y, i = 1; i <= m; ++i)
    {
        x = read(), y = read();
        ++out[x], ++mp[x][y];
        if (x != y) ++out[y], ++mp[y][x];
    }
    for (int i = 1; i < n; ++i)
        for (int j = 1; j <= n; ++j)
            if (!a[j]) d[j][i] -= 1.0 * mp[i][j] / out[i];
    for (int i = 1; i <= n; ++i)
        ++d[i][i], num[i][i] = 1;
    gauss();
    f[hp][1] = 1;
    for (int i = hp; i; --i)
    {
        for (int j = 1; j < n; ++j)
            for (int k = 1; k <= n; ++k)
                if (a[k] && i + a[k] <= hp)
                    f[i][k] += f[i + a[k]][j] * mp[j][k] / out[j];
        for (int j = 1; j <= n; ++j)
            temp[j] = f[i][j];
        for (int j = 1; j <= n; ++j)
        {
            if (a[j]) continue;
            f[i][j] = 0;
            for (int k = 1; k < n; ++k)
                if (a[k] || k == 1) f[i][j] += num[j][k] * temp[k];
        }
        ans += f[i][n];
    }
    cout << fixed << setprecision(8) << ans << endl;
    return 0;
}

BZOJ3648 寝室管理

发现对于 50% 的数据,是树分治傻题(周老师竟然管树分治叫暴力,天怒人怨)。

对于后 50% 的数据,是基环树。将环拆开,用树分治先求一个不经过拆开的边的方案数,再加上经过这条边的方案数,就是答案了。

怎么求呢?枚举链扩展到左面的位置和右面的位置的分界线,用树状数组维护一下到链的距离,每一次求个后缀和就好了。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, m, k, f[N], pox, poy;
int head[N], size[N], maxs[N], vis[N];
long long ans;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void getroot(int &root, int sum, int x, int fa)
{
    size[x] = 1, maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(root, sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] <= maxs[root]) root = x;
}

void getdist(vector<int> &v, int x, int fa, int d)
{
    v.push_back(d);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getdist(v, edge[i].to, x, d + 1);
}

long long getans(int x, int d)
{
    static vector<int> v;
    v.resize(0);
    getdist(v, x, 0, d);
    sort(v.begin(), v.end());
    long long re = 0;
    int l = 0, r = v.size() - 1;
    while (l < r)
        if (v[l] + v[r] < k - 1) re += r - l, ++l;
        else --r;
    return re;
}

long long solve(int x)
{
    vis[x] = 1;
    long long re = getans(x, 0);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            re -= getans(edge[i].to, 1);
            int root = 0;
            getroot(root, size[edge[i].to], edge[i].to, 0);
            re += solve(root);
        }
    return re;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int find(int x)
{
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

int deep[N], fa[N], bit[N];

void modify(int x, int y)
{
    for (int i = x; i; i -= i & -i)
        bit[i] += y;
}

int query(int x)
{
    int re = 0;
    for (int i = x; i <= n; i += i & -i)
        re += bit[i];
    return re;
} 

void dfs(int x)
{
    deep[x] = deep[fa[x]] + 1;
    modify(deep[x], 1);
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x])
            fa[edge[i].to] = x, dfs(edge[i].to);
}

void dfs2(int x)
{
    modify(deep[x], -1);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa[x])
            dfs2(edge[i].to);
}

void update(int p, int x)
{
    int t = deep[x] - deep[p] + deep[poy] - deep[p];
    ans += query(max(k - t - 1, 1));
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa[x])
            update(p, edge[i].to);
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    for (int x, y, i = 1; i <= m; ++i)
    {
        x = read(), y = read();
        if (find(x) == find(y)) pox = x, poy = y;
        else add(x, y), add(y, x), f[find(x)] = find(y);
    }
    maxs[0] = 0x3f3f3f3f;
    int root = 0; getroot(root, n, 1, 0);
    ans = 1ll * n * (n - 1) / 2 - solve(root);
    if (m == n - 1) { cout << ans << endl; return 0; }
    memset(vis, 0, sizeof vis);
    dfs(pox);
    for (int i = poy; i; i = fa[i]) vis[i] = 1;
    for (int i = poy; i != pox; i = fa[i])
        dfs2(i), update(i, i);
    cout << ans << endl;
    return 0;
}

ZCC Loves Nesting

问题描述

ZCC学习了函数的嵌套,他决定练习一下。于是在纸上写下了两个数列a和b,有写下了一个排列c,他把a和c嵌套起来形成了新的数列a(c(i)),再把c和b嵌套起来形成了一个新的数列c(b(i))。这时,ZCC惊讶地发现这两个数列竟然是完全一样的。他非常想知道如果写出了a和b,那么有几个排列满足条件。

输入

输入文件名为(nesting.in)。

输入包含多组数据,每组数据的第一行为n,表示a,b数列的长度,两个数列长度相同。

接下来的两行分别包含n个正整数,表示a,b数列。

输出

输出文件名为(nesting.out)。

对于每组数据,如果不存在满足条件的排列c,那么直接输出“biubiu”。

否则输出“Get t”,t表示排列c的种数,种数有可能会非常多,所以需要对109+7取模。并在接下来的一行中输出任意一个满足条件的排列。

样例输入

6

5 1 1 5 5 5

4 5 5 5 5 4

2

1 2

样例输出

2 2 Get 4

2 4 6 1 5 3

biubiu

数据范围与约定

对于5%的数据:n<=10。

对于10%的数据:n<=17。

对于另外20%的数据,a,b都是排列。

对于另外5%的数据,a是排列。

对于另外25%的数据,n<=100。

对于另外10%的数据,n<=10000。

对于另外15%的数据,n<=50000。

对于所有的数据,n<=100000。

真正的数据范围

对于所有的大数据,a,b都是排列。

题解

将两个排列分别按照置换的循环形式建图,然后我们就可以分别得到好多好多环,将这两张图叫做 A 图和 B 图。考虑 B 图中的一条边 i->b(i),应该在 A 图中存在一条 c(i)->a(c(i)),即 c(i)->c(b(i)) 的边。

然后发现只需要判断 A 图和 B 图是否同构就好了。实际上就是数一数多大的环的个数,方案数就是乘以乘阶乘什么的。输出方案应该就是相同大小的环放在一起遍历,输出