湖南省选 HNOI2015

2016.01.11 14:31 Mon| 14 visits oi_2016| 2016_刷题日常| Text

BZOJ4008 [HNOI2015]亚瑟王

设 f[i][j] 表示经过第 i 张卡牌 j 次的概率。由 f[i][j] 有可能扩展出 f[i][j] 和 f[i][j - 1] 两种情况,递推一次就可以求出来了。最后累计答案。

最开始写了一个设 f[i] 表示第 i 张卡牌的期望经过次数,发现答案错误。这是因为有乘方的操作,直接算 f[i] 次方会出现奇怪的东西。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 225

int test, n, r, d[N];
double p[N], f[N][N], ans;

int main()
{
    cin >> test;
    while (test--)
    {
        scanf("%d%d", &n ,&r);
        for (int i = 1; i <= n; ++i)
            scanf("%lf%d", &p[i], &d[i]);
        memset(f, 0, sizeof f);
        f[1][r] = 1;
        for (int i = 1; i < n; ++i)
            for (int j = 1; j <= r; ++j)
                f[i + 1][j] += f[i][j] * pow(1 - p[i], j),
                f[i + 1][j - 1] += f[i][j] * (1 - pow(1 - p[i], j));
        ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= r; ++j)
                ans += f[i][j] * d[i] * (1 - pow(1 - p[i], j));
        printf("%.10lf\n", ans);
    }
    return 0;
}

BZOJ4009 [HNOI2015]接水果

神转化,将盘子的管辖范围划定成了矩形。

注意到一个盘子能够接的水果的端点一定在盘子的端点两侧,而这两侧区域在 DFS 序上都是连续的(或是两半的),我们可以用一个矩形表示,其中矩形的横坐标表示对于这个盘子能够接的水果的左端点范围,纵坐标表示能够接的水果的右端点范围。枚举横坐标做扫描线,用主席树维护第 k 大值,O(NlogNlogC) 的时间内就可以解决问题了。

  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
153
154
155
156
157
158
159
160
161
162
163
#include <bits/stdc++.h>
using namespace std;

#define N 40005

int n, p, q, head[N], fa[N][18], id[N], id2[N], ans[N];
vector<pair<int, pair<int, int> > > v1[N], v2[N], vq[N];

struct node
{
    node *son[2]; int size;
    node() { son[0] = son[1] = NULL; size = 0; }
    void *operator new(size_t s);
};

void *node::operator new(size_t s)
{
    static node newnode[10000000], *p = newnode;
    return p++;
}

node *root[N];

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 dfs(int x)
{
    static int tot = 0;
    id[x] = ++tot;
    for (int i = head[x]; i; i = edge[i].next)
        if (!id[edge[i].to])
            fa[edge[i].to][0] = x, dfs(edge[i].to);
    id2[x] = tot;
}

void insert(node *&pos, int l, int r, int x, int y)
{
    if (pos == NULL) pos = new node();
    pos->size += y;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(pos->son[0], l, mid, x, y);
    else insert(pos->son[1], mid + 1, r, x, y);
}

int queryk(vector<node*> &v, int l, int r, int x)
{
    if (l == r) return l;
    int mid = (l + r) >> 1, sum = 0;
    for (int i = 0; i < (int)v.size(); ++i)
        if (v[i] && v[i]->son[0]) sum += v[i]->son[0]->size;
    if (sum >= x)
    {
        for (int i = 0; i < (int)v.size(); ++i)
            if (v[i]) v[i] = v[i]->son[0];
        return queryk(v, l, mid, x);
    }
    else
    {
        for (int i = 0; i < (int)v.size(); ++i)
            if (v[i]) v[i] = v[i]->son[1];
        return queryk(v, mid + 1, r, x - sum);
    }
}

void modify(int x, int y, int z)
{
    for (int i = x; i <= n; i += i & -i)
        insert(root[i], 0, 1000000000, y, z);
}

int query(int x, int y)
{
    vector<node *> v;
    for (int i = x; i; i -= i & -i)
        v.push_back(root[i]);
    return queryk(v, 0, 1000000000, y);
}

int find(int x, int top)
{
    for (int i = 17; i >= 0; --i)
        if (id[fa[x][i]] > id[top])
            x = fa[x][i];
    return x;
}

void solve()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < (int)v1[i].size(); ++j)
            modify(v1[i][j].second.first, v1[i][j].first, 1),
            modify(v1[i][j].second.second + 1, v1[i][j].first, -1);
        for (int j = 0; j < (int)vq[i].size(); ++j)
            ans[vq[i][j].second.second]
                = query(vq[i][j].first, vq[i][j].second.first);
        for (int j = 0; j < (int)v2[i].size(); ++j)
            modify(v2[i][j].second.first, v2[i][j].first, -1),
            modify(v2[i][j].second.second + 1, v2[i][j].first, 1);
    }
}

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 main()
{
    cin >> n >> p >> q;
    for (int x, y, i = 1; i < n; ++i)
        x = read(), y = read(), add(x, y), add(y, x);
    dfs(1);
    for (int j = 1; j <= 17; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    for (int x, y, z, i = 1; i <= p; ++i)
    {
        x = read(), y = read(), z = read();
        if (id[x] > id[y]) swap(x, y);
        if (id[y] <= id2[x])
        {
            int t = find(y, x);
            v1[1].push_back(make_pair(z, make_pair(id[y], id2[y]))),
            v2[id[t] - 1].push_back(make_pair(z, make_pair(id[y], id2[y])));
            if (id2[t] < n)
                v1[id[y]].push_back(make_pair(z, make_pair(id2[t] + 1, n))),
                v2[id2[y]].push_back(make_pair(z, make_pair(id2[t] + 1, n)));
        }
        else
        {
            v1[id[x]].push_back(make_pair(z, make_pair(id[y], id2[y]))),
            v2[id2[x]].push_back(make_pair(z, make_pair(id[y], id2[y])));
        }
    }
    for (int x, y, z, i = 1; i <= q; ++i)
    {
        x = read(), y = read(), z = read();
        if (id[x] > id[y]) swap(x, y);
        vq[id[x]].push_back(make_pair(id[y], make_pair(z, i)));
    }
    solve();
    for (int i = 1; i <= q; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

BZOJ4010 [HNOI2015]菜肴制作

让质量高的菜尽量先上,等同于让质量低的菜能后上就后上。实际上,将原图的边变成反向边,按照编号从大到小拓扑排序,再反着输出就好了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int test, n, m, head[N], cnt, in[N];

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

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

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;
}

priority_queue<int> q;
stack<int> ans;

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n >> m;
        memset(head, 0, sizeof head); cnt = 1;
        memset(in, 0, sizeof in);
        while (!ans.empty()) ans.pop();
        for (int x, y, i = 1; i <= m; ++i)
            x = read(), y = read(), add(y, x), ++in[x];
        for (int i = 1; i <= n; ++i)
            if (!in[i]) q.push(i);
        while (!q.empty())
        {
            int x = q.top(); q.pop(), ans.push(x);
            for (int i = head[x]; i; i = edge[i].next)
                if (!--in[edge[i].to]) q.push(edge[i].to);
        }
        bool flag = true;
        for (int i = 1; i <= n; ++i)
            if (in[i]) flag = false;
        if (!flag) printf("Impossible!");
        else while (!ans.empty()) printf("%d ", ans.top()), ans.pop();
        puts("");
    }
    return 0;
}

BZOJ4011 [HNOI2015]落忆枫音

读题的时候,我的手中不知为何出现了火把。

拓扑图的生成树形图个数等于非根节点的入度之积。

现在在拓扑图上多加了一个反向边,那么按照上面的方式计算就会将新出现的环也统计进去。现在考虑将环减掉,枚举每一条从 y 到 x 的路径,我们需要减掉不是根节点也不在这条路径上的结点的入度之积。通过 DP 或者记忆化搜索可以统计出来所有这样的路径的答案之和。

 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
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define N 100005

int n, m, u, v, head[N], in[N], vis[N];
long long f[N], ans = 1;

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;
}

long long power(long long a, long long b)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re = re * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return re;
}

void getans(int x)
{
    if (vis[x]) return; vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        getans(edge[i].to), f[x] = (f[x] + f[edge[i].to]) % mod;
    f[x] = f[x] * power(in[x], mod - 2) % mod;
}

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 main()
{
    cin >> n >> m >> u >> v;
    if (u != v) ++in[v];
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(), add(y, x), ++in[y];
    for (int i = 2; i <= n; ++i)
        ans = ans * in[i] % mod;
    if (v == 1 || u == v) { cout << ans << endl; return 0; }
    f[v] = power(in[v], mod - 2) % mod, vis[1] = vis[v] = 1;
    getans(u);
    cout << (ans - ans * f[u] % mod + mod) % mod << endl;
    return 0;
}

BZOJ4012 [HNOI2015]开店

树分治,见《树上问题总结》。

BZOJ4013 [HNOI2015]实验比较

按照输入的关系缩点建图,如果建出来了环,就说明无解,否则我们就会得到一个森林。

对于森林,我们不妨把每棵树的根节点连到一个新建节点上,于是就变成树了。对于树的每一个非叶子结点,它一定小于它所有的子结点,而它的子树之间大小关系相互独立。考虑合并每一个节点的子树,设 dp[i][j] 表示树的第 i 个结点的子树中,结点共有 j 种不同取值的方案数。对于每一个节点两两合并子树,推一推组合数公式就好了。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 105
#define mod 1000000007

int n, m, x[N], opt[N], y[N], p[N], head[N], in[N], vis[N];
int size[N], c[N][N], f[N][N], g[N], ans;

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

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

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '=') return 0; if (ch == '<') return 1;
        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 == p[x]) return x;
    return p[x] = find(p[x]);
}

bool check(int x)
{
    if (vis[x]) return false; vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!check(edge[i].to)) return false;
    return true;
}

void dfs(int x)
{
    for (int i = head[x]; i; i = edge[i].next)
    {
        dfs(edge[i].to);
        if (size[x] == 0)
        {
            size[x] += size[edge[i].to];
            for (int j = 1; j <= size[edge[i].to]; ++j)
                f[x][j] = f[edge[i].to][j];
            continue;
        }
        for (int j = 1; j <= size[x] + size[edge[i].to]; ++j)
            g[j] = 0;
        for (int j = 1; j <= size[x]; ++j)
            for (int k = 1; k <= size[edge[i].to]; ++k)
                for (int l = max(j, k); l <= j + k; ++l)
                    g[l] = (g[l] + 1ll * f[x][j] * f[edge[i].to][k] % mod
                            * c[l][j] % mod * c[j][l - k] % mod) % mod;
        size[x] += size[edge[i].to];
        for (int j = 1; j <= size[x]; ++j)
            f[x][j] = g[j];
    }
    if (x)
    {
        ++size[x];
        for (int i = size[x]; i >= 1; --i)
            f[x][i] = f[x][i - 1];
        if (size[x] == 1) f[x][1] = 1;
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        x[i] = read(), opt[i] = read(), y[i] = read();
        if (opt[i] == 0)
        {
            int fx = find(x[i]), fy = find(y[i]);
            if (fx != fy) p[fx] = fy;
        }
    }
    for (int i = 1; i <= m; ++i)
        if (opt[i] == 1)
        {
            if (find(x[i]) != find(y[i]))
                add(find(x[i]), find(y[i])), ++in[find(y[i])];
            else return puts("0"), 0;
        }
    for (int i = 1; i <= n; ++i)
        if (i == find(i) && !in[find(i)])
            add(0, find(i));
    if (!check(0)) return puts("0"), 0;
    for (int i = 1; i <= n; ++i)
        if (i == find(i) && !vis[i])
            return puts("0"), 0;
    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;
    }
    dfs(0);
    for (int i = 1; i <= n; ++i)
        ans = (ans + f[0][i]) % mod;
    cout << ans << endl;
    return 0;
}