BZOJ 1854: [Scoi2010]游戏

一个武器可以看成连接对应两个属性值的一条边
可以证明如果一个联通块中出现一个环
则整个联通块都可以取
否则会有一个点不能取
显然这个不取的点是最大的那个点= =
然后扫一遍看能取到哪就行了
找环和维护最大可以用并查集做

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 1000005;
 
int n, fa[maxn], is[maxn];
 
int getfa(int now)
{
    return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        u = getfa(u), v = getfa(v);
        if (u == v) is[u] = is[v] = 1;
        else
        {
            if (u < v)swap(u, v);
            if (is[u] || is[v]) is[u] = is[v] = 1;
            fa[v] = u;
            is[v] = 1;
        }
    }
    for (int i = 1; i < maxn; ++i)
        if (!is[i])
        {
            cout << i - 1;
            break;
        }
}

BZOJ 1576: [Usaco2009 Jan]安全路经Travel

先构出最短路径树(题目说唯一)
对于一个非树边(u,v) 一定使树构成一个环
并且使环上的点(除了lca(u,v))都有了一个次短路
对于点i 这个所谓次短路的长度就是dist[u]+dist[v]+value[u,v]-dist[i]
可以发现次短路大小长度跟u,v有关 跟i无关
所以对于一个非树边(u,v)设它的权值为dist[u]+dist[v]+value[u,v]
把这个权值按从小到大排序 每次把环上没被赋值过的点赋上值
快速实现上面那个 可以用并查集(不用多说了吧=v=)

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 100005;
 
struct line
{
    int to, next, v;
}li[maxn * 10];
 
struct wtf
{
    int v, cost;
    wtf(int a, int b) : v(a), cost(b) {}
};
 
struct hh
{
    int u, v, va;
}t[maxn * 5];
 
int be[maxn], dist[maxn], fa[maxn], f[maxn], d[maxn], tot, ans[maxn], l, n, m, b[maxn];
priority_queue<wtf> q;
 
bool operator<(wtf a, wtf b)
{
    return a.cost > b.cost;
}
 
bool cmp(hh a, hh b)
{
    return a.va < b.va;
}
 
void makeline(int fr, int to, int v)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
}
 
int getfa(int now)
{
    return (!f[now]) ? now : f[now] = getfa(f[now]);
}
 
void re_ans(int u, int v, int va)
{
    int lastu = -1, lastv = -1;
    while (getfa(u) != getfa(v))
    {
        if (d[getfa(u)] < d[getfa(v)]) swap(u, v), swap(lastu, lastv);
        if (ans[u] == -1)
        {
            ans[u] = va - dist[u];
            if (lastu != -1)
                f[lastu] = u;
        }
        else
            if (lastu != -1)
                f[lastu] = getfa(u);
        lastu = getfa(u);
        u = fa[lastu];
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int fr, to, v;
        scanf("%d%d%d", &fr, &to, &v);
        makeline(fr, to, v);
        makeline(to, fr, v);
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    d[1] = 1;
    q.push(wtf(1, 0));
    while (!q.empty())
    {
        while (!q.empty() && b[q.top().v]) q.pop();
        if (q.empty()) break;
        int now = q.top().v;
        b[now] = 1;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (b[to] || dist[to] <= dist[now] + li[i].v) continue;
            fa[to] = now;
            d[to] = d[now] + 1;
            dist[to] = dist[now] + li[i].v;
            q.push(wtf(to, dist[to]));
        }
    }/*
    for (int i = 1; i <= n; ++i)
        printf("%d\n", dist[i]);
    printf("\n\n");*/

    for (int i = 1; i <= n; ++i)
        for (int j = be[i]; j; j = li[j].next)
        {
            int to = li[j].to;
            if (to >= i || fa[to] == i || fa[i] == to) continue;
            t[tot].u = i, t[tot].v = to, t[tot].va = dist[i] + dist[to] + li[j].v;
            ++tot;
        }
    memset(ans, -1, sizeof(ans));
    sort(t, t + tot, cmp);
    for (int i = 0; i < tot; ++i)
        re_ans(t[i].u, t[i].v, t[i].va);
    for (int i = 2; i <= n; ++i)
        printf("%d\n", ans[i]);
}

BZOJ 1016: [JSOI2008]最小生成树计数

求一个无向图(n,m)的生成树数可以构造下面一个矩阵
矩阵大小:(n * n)
对于一个位置(i,j)
如果i==j则上面的数为点i的度数
否则为i到j的边数的相反数
如一个图1<->2,2<->3点数为3
则矩阵为
1 -1 0
-1 2 -1
0 -1 1
吧这个矩阵的第i行和第i列去掉(1<=i<=n i取任意值都可) 然后叫这个剩下来的矩阵n-1阶余子式 求这个矩阵的行列式的绝对值即为该图的生成树数 (我不知道行列式是什么啊QAQ 我就只知道能这么用QvQ 虽然听起来不像是一个值 但是就这么用吧QvQ) 求一个矩阵的行列式就是先用高斯消元把这个矩阵消成上三角矩阵 然后ans=π(f[i][i]) 对于求生成树数这个矩阵 ans最后会是一个整数 但是中间步骤可能是小数 最小生成树计数怎么做呢=、= 先把边按权值从小到大排序 从小到大遍历 对于边权相同的一些边取出来 对于这些边的每个联通子图求生成树数(自环要无视) ans=π每个联通子图求生成树数 最后把每个联通块用并查集分别并为一个点 然后再做下一个边权的边集即可 这题的ans可能很大 如果直接开double或long double都可能爆(其实long double不会=-=) 这题有mod一个数 如果可以让ans中间过程也是整数就非常好 考虑对一个矩阵的某行减掉某行的某倍 这个矩阵的行列式是不会变的 则我们可以用一个类似辗转相除的方法 让这个矩阵在保证每个元素仍是整数的情况下变为上三角矩阵(详见代码) 【周冬《生成树的计数及其应用》】

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf = 31011;
const ll maxn = 105;

struct lin
{
    ll fr, to, v;
}p[10005];

struct line
{
    ll next, to;
}li[10005];

ll be[maxn], fa[maxn], l, to[maxn], tot, ans, n, m;
ll v[maxn][maxn];
queue<ll> q;

bool cmp(lin a, lin b)
{
    return a.v < b.v;
}

void makeline(ll fr, ll to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

ll bfs(ll now)
{
    for (to[now] = tot = 1, v[1][1] = 0, q.push(now); !q.empty(); )
    {
        ll now = q.front();
        q.pop();
        for (ll i = be[now]; i; i = li[i].next)
        {
            ll _to = li[i].to;
            if (_to == now) continue;
            if (!to[_to])
            {
                to[_to] = ++tot;
                for (ll j = 1; j <= tot; ++j)
                    v[j][tot] = v[tot][j] = 0;
                q.push(_to);
            }
            v[to[now]][to[now]] += 1;
            v[to[now]][to[_to]] -= 1;
        }
    }
    if (tot == 1) return 1;
    ll ans = 1;
    for (ll i = 1; i < tot; ++i)
    {
        if (!v[i][i])
        {
            ll ans = -1;
            for (ll j = i + 1; j < tot; ++j)
                if (ans == -1 || abs(v[j][i]) > abs(v[ans][i]))
                    ans = j;
            for (ll j = i; j < tot; ++j)
                swap(v[i][j], v[ans][j]);
        }
        for (ll j = i + 1; j < tot; ++j)
            while (v[j][i])
            {
                ll t = v[i][i] / v[j][i];
                for (ll k = i; k < tot; ++k)
                    v[i][k] -= t * v[j][k],
                    swap(v[j][k], v[i][k]);
            }
        ans = (ans * v[i][i]) % inf;
    }
    return ans % inf;
}

ll getfa(ll now)
{
    return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}

int main()
{
    ans = 1;
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; ++i)
        scanf("%lld%lld%lld", &p[i].fr, &p[i].to, &p[i].v);
    sort(p, p + m, cmp);
    ans = 1;
    for (ll i = 0; i < m;)
    {
        l = 0;
        memset(be, 0, sizeof(be));
        memset(to, 0, sizeof(to));
        ll j;
        for (j = i; j < m && p[i].v == p[j].v; ++j)
            makeline(getfa(p[j].fr), getfa(p[j].to)),
            makeline(getfa(p[j].to), getfa(p[j].fr));
        ll t = j;
        for (ll j = 1; j <= n; ++j)
            if (!to[getfa(j)])
                ans = (ans * bfs(getfa(j))) % inf;
        for (ll j = i; j < t; ++j)
            if (getfa(p[j].fr) != getfa(p[j].to))
                fa[getfa(p[j].fr)] = getfa(p[j].to);
        i = t;
    }
    for (int i = 1; i <= n; ++i)
        if (getfa(i) != getfa(1))
        {
            cout << 0;
            return 0;
        }
    cout << abs(ans);
}

博物馆(museum)

这题求的是到某个点为终点的概率
以某个点为终点的概率可以是这个状态被进入的期望次数
即f[i][j]表示第一个人到i点 第二个人到j点的进入这个状态的期望次数
12
p是停留在某个点的概率 d是某个点的度数 S1 S2是初始状态
这个方程有环
所以用高斯消元做
把每个fij看成一个元 拿去解方程 即可出解

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

struct line
{
    int to, next;
}li[1005];

int n, m, a, b, be[25], d[25], to[1005][2], fr[25][25], tot, l;
double p[25], v[405][405], ans[405];

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 0; i < m; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
        ++d[fr], ++d[to];
    }
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            fr[i][j] = tot;
            to[tot][0] = i, to[tot][1] = j;
            ++tot;
        }
    for (int i = 0; i < tot; ++i)
    {
        int u1 = to[i][0], u2 = to[i][1];
        v[i][i] = -1 ;
        if (u1 == u2) continue;
        v[i][i] += p[u1] * p[u2];
        double va1 = p[u1] * (1 - p[u2]) / d[u2],
                     va2 = (1 - p[u1]) * p[u2] / d[u1],
                     va = (1 - p[u1]) * (1 - p[u2]) / d[u1] / d[u2];

        for (int j1 = be[u2]; j1; j1 = li[j1].next)
            v[fr[u1][li[j1].to]][i] = va1;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            v[fr[li[j1].to][u2]][i] = va2;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            for (int j2 = be[u2]; j2; j2 = li[j2].next)
                v[fr[li[j1].to][li[j2].to]][i] = va;
    }
    v[fr[a][b]][tot] = -1;/*
    for (int i = 0; i < tot; ++i)
    {
        for (int j = 0; j <= tot; ++j) printf("%.2f ", v[i][j]);
        printf("\n");
    }*/

    for (int i = 0; i < tot; ++i)
    {
        int t = -1;
        for (int j = i; j < tot; ++j)
            if (t == -1 || abs(v[j][i]) > abs(v[t][i]))
                t = j;
        for (int j = 0; j <= tot; ++j)
            swap(v[i][j], v[t][j]);
        for (int j = i + 1; j < tot; ++j)
        {
            double va = v[j][i] / v[i][i];
            for (int k = i; k <= tot; ++k)
                v[j][k] -= va * v[i][k];
        }
    }
    for (int i = tot - 1; i >= 0; --i)
    {
        for (int j = i + 1; j < tot; ++j)
            v[i][tot] -= ans[j] * v[i][j];
        ans[i] = v[i][tot] / v[i][i];
    }/*
    for (int i = 0; i < tot; ++i)
        printf("%.6f ", ans[i]);
        printf("\n");*/

    for (int i = 1; i <= n; ++i)
        printf("%.6f ", ans[fr[i][i]] + 1e-8);
    fclose(stdin);fclose(stdout);
}

BZOJ 3451: Tyvj1953 Normal

考虑两个点a,b
a对b的删除时间有1的贡献当且仅当
在a到b的路径上的所有点中a是第一个删除的
这个有1/dist(a,b)的概率 对答案的贡献是1
所以这题就是求Σ1/(u,v)
这个可以用树分治做(233)
然后树分治合并两棵子树的f的时候要n^2的时间
这个可以fft优化到nlogn
总复杂度nlog^2n

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 300005;
const int P = (1 << 21) * 479 + 1;
const int G = 3;

struct line
{
    int to, next;
}li[maxn * 2];

int be[maxn], mx[maxn], f[maxn], b[maxn], fa[maxn], is[maxn], g[maxn][2], gt[maxn][2], d[maxn], br[maxn];
ll t1[maxn], t2[maxn], tt1[maxn], tt2[maxn];
int l, n, tot, tot1;
ld ans;
queue<int> q;
stack<int> s;
vector<int> v;

int getz(int now)
{
    int tot = 0, as = -1;
    for (q.push(now), b[now] = 1, fa[now] = -1; !q.empty(); )
    {
        int now = q.front();
        ++tot;
        q.pop();
        s.push(now);
        f[now] = mx[now] = 0;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (is[to] || b[to]) continue;
            fa[to] = now;
            b[to] = 1;
            q.push(to);
        }
    }
    for (; !s.empty(); )
    {
        int now = s.top();
        s.pop();
        b[now] = 0;
        ++f[now];
        if (fa[now] != -1)
            f[fa[now]] += f[now],
            mx[fa[now]] = max(mx[fa[now]], f[now]);
        mx[now] = max(mx[now], tot - f[now]);
        if (as == -1 || mx[as] > mx[now])
            as = now;
    }
    return as;
}

bool cmp(int a, int b)
{
    return f[a] < f[b];
}

int bitre(int a, int n)
{
    int ans = 0;
    for (int i = 0; i < n; ++i)
        ans += (1 << i) * ((a & (1 << (n - i - 1))) ? 1 : 0);
    return ans;
}

ll power(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1) ans = (ans * a) % P;
        a = (a * a) % P;
        n >>= 1;
    }
    return ans;
}

void fnt(ll y[], const ll b[], ll n, ll rev = 1)
{
    ll len = 1 << n;
  for (ll i = 0; i < len; ++i)
    y[i] = b[bitre(i, n)];
    for (int i = 1; i <= n; ++i)
    {
        ll m = 1 << i;
        ll wn = power(G, (P - 1) / m);
        for (int j = 0; j < len; j += m)
        {
            ll w = 1;
            for (int k = j; k < j + m / 2; ++k)
            {
                ll u = y[k], v = (w * y[k + m / 2]) % P;
                y[k] = (u + v) % P, y[k + m / 2] = (u - v) % P;
                w = (w * wn) % P;
            }
        }
    }
    if (rev == 1) return;
    ll re = power(len, P - 2);
    for (int i = 0; i < len; ++i)
        y[i] = (y[i] * re % P + P) % P;
    reverse(y + 1, y + len);
}

void calc2(int v)
{
    int n, len;
    for (n = 0; (1 << n) < (v + 1) * 2; ++n);
    len = 1 << n;
    for (int i = 0; i < len; ++i)
        t1[i] = g[i][0] != tot1 ? 0 : g[i][1],
        t2[i] = gt[i][0] != tot ? 0 : gt[i][1];
    fnt(tt1, t1, n);
    fnt(tt2, t2, n);
    for (int i = 0; i < len; ++i) tt1[i] = (tt1[i] * tt2[i]) % P;
    fnt(t1, tt1, n, -1);
    for (int i = 2; i < len; ++i)
        ans += 1.0 / i * t1[i];
}

void calc(int now)
{
    getz(now);
    while (!v.empty()) v.pop_back();
    for (int i = be[now]; i; i = li[i].next)
        if (!is[li[i].to])
            v.push_back(li[i].to);
    sort(v.begin(), v.end(), cmp);
    ++tot1;
    for (int k = 0; k < v.size(); ++k)
    {
        int to = v[k];
        ++tot;
        for (q.push(to), br[to] = tot, d[to] = 1; !q.empty();)
        {
            int now = q.front();
            q.pop();
            if (gt[d[now]][0] != tot)
                gt[d[now]][0] = tot,
                gt[d[now]][1] = 0;
            ++gt[d[now]][1];
            for (int i = be[now]; i; i = li[i].next)
            {
                int to = li[i].to;
                if (br[to] == tot || is[to]) continue;
                br[to] = tot;
                d[to] = d[now] + 1;
                q.push(to);
            }
        }
        for (int i = 1; i <= f[to]; ++i)
        {
            if (gt[i][0] != tot) break;
            ans += 1.0 / (i + 1) * gt[i][1];
        }
        calc2(f[to] + 1);
        for (int i = 1; i <= f[to]; ++i)
        {
            if (g[i + 1][0] != tot1)
                g[i + 1][0] = tot1,
                g[i + 1][1] = 0;
            if (gt[i][0] != tot) break;
            g[i + 1][1] += gt[i][1];
        }
    }
}

void solve(int now)
{
    int z = getz(now);
    is[z] = 1;
    calc(z);
    for (int i = be[z]; i; i = li[i].next)
        if (!is[li[i].to])
            solve(li[i].to);
}

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
    }
    solve(0);
    printf("%.4f", n + (double)ans * 2);
    fclose(stdin);fclose(stdout);
}

BZOJ 3450: Tyvj1952 Easy

对于连续的一段o
考虑第i个o
贡献的权值是2i-1
这样Σvi=n^2(1<= i <= n) 对所有n都有效 f[i]表示考虑前i个按键 期望收益是多少 问题是怎么转移呢0.0 显然f[i] = f[i - 1] + (i的期望收益) (根据期望可加) i的期望收益 枚举所有?的选择 设第j种选择最后有连续len[j]个o 一共m种选择 则i的期望收益为: ----------------------------- Σ(len[j] * 2 - 1) / m = (Σ(len[j]) / m) * 2 - 1 ----------------------------- Σ(len[j]) / m其实考虑前i位 最后连续的o的期望长度 这样就很简单了 g[i]表示前i为最后连续o的期望长度 然后就可以推了 但是如果长度为0 则按那个公式期望收益为0*2-1 = -1 显然是错的 要特判掉 怎么弄呢= = 可以从g[i - 1]转移 如果s[i] == 'x'就不管了 f[i] = f[i - 1] 如果s[i] == 'o'也不会有0的情况 直接转移即可 f[i] = f[i - 1] + g[i] * 2 - 1 如果s[i] == '?'那么有1/2的概率会长度为0则 f[i] = f[i - 1] + (g[i - 1] * 2 + 1) / 2即可(有1/2概率没收益)

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 300005;
 
ld f[maxn], g[maxn];
int n;
 
int main()
{
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++i)
    {
        char c = getchar();
        if (c == 'x') f[i] = f[i - 1], g[i] = 0;
        if (c == 'o') g[i] =  g[i - 1] + 1, f[i] = f[i - 1] + g[i - 1] * 2 + 1;
        if (c == '?') g[i] = (g[i - 1] + 1) / 2, f[i] = f[i - 1] + g[i - 1] + 0.5;
    }
    printf("%.4f", (double)f[n]);
}

BZOJ 3437: 小P的牧场

这题一看就是奇怪的dp啊╮(╯_╰)╭
f[i]表示考虑前i个牧场 且第i个有取的最小代价
但是把这个方程列出来 会发现这个方程有一部分的系数是一个公差为1的等差数列
这就很蛋疼
不能以一个项数为O(1)级的多项式表示i取j决策的代价

怎么办呢
所谓正难则反
首先设答案为类似只在n+1号位置取一个观察站 的代价
如果这时候在i位置取一个观察站 则答案会减少(sum[i] * (n – i) – a[i])
f[i]表示考虑i~n的牧场 最多可以扣掉多少代价 且i有取
方程为
f[i] = max(a[i] + f[j] + sum[i] * (j – i))
sum[i]表示Σ(b[j])(1 <= j <= i) 这个方程拿去斜率优化一下即可 另外这个系列的数据范围巨坑无比 n的范围是100w 他写变成n <= 1000000,0 后面加了个,0不知道作何心态=-=

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const ll maxn = 1000 * 1000 + 5;
 
struct poll
{
    ll x, y;
    poll(ll a = 0, ll b = 0) : x(a), y(b) {}
};
 
poll q[maxn];
ll f[maxn], n, a[maxn], b[maxn], sum[maxn], h, t;
ll ans;
 
ll xj(poll a, poll b, poll c)
{
    return ((ll)b.x - a.x) * (c.y - a.y) - ((ll)b.y - a.y) * (c.x - a.x);
}
 
ll calc(ll i, poll j)
{
    return -a[i] + j.y + sum[i] * (j.x - i);
}
 
int main()
{
    scanf("%lld", &n);
    for (ll i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    for (ll i = 0; i < n; ++i)
    {
        scanf("%lld", &b[i]);
        ans += ((ll)n - i) * b[i];
        if (!i) sum[i] = b[i];
        else sum[i] = sum[i - 1] + b[i];
    }
    f[n - 1] = sum[n - 1] - a[n - 1];
    h = t = 0;
    q[0] = poll(n - 1, f[n - 1]);
    ll as = f[n - 1];
    for (ll i = n - 2; i >= 0; --i)
    {
        while (h < t && calc(i, q[h]) <= calc(i, q[h + 1])) ++h;
        f[i] = calc(i, q[h]);
        while (h < t && xj(q[t - 1], q[t], poll(i, f[i])) <= 0) --t;
        q[++t] = poll(i, f[i]);
        as = max(as, f[i]);
    }
    printf("%lld", ans - as);
}

BZOJ 3439: Kpm的MC密码【论splay的正确姿势】

这题本身很简单
就是把串反过来做trie+区间k大即可
但是这题主席树做空间不够(应该是不够吧0.0)
于是就按拓扑序做启发式合并平衡树
刚好早上被黄神神d模板过长 于是orz了贵校的模板 学习了下
这是spaly的一些函数的科学写法

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
void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

然后这题的全题代码0 0
我只能说要是用我原来的模板得多100行=-=

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
164
165
166
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;

struct node
{
    int ch[26], sum, fa;
    vector<int> to;
}tr[maxn];

struct nodes
{
    int c[2], fa, sum;
}t[maxn];

int n, d[maxn], totr, root[maxn], ans[maxn], k[maxn];
string s;
queue<int> q;

void inss(int no)
{
    for (int i = s.length() - 1, now = 1; i >= 0; --i)
    {
        int to = tr[now].ch[s[i] - 'a'];
        ++tr[now].sum;
        if (!to)
        {
            to = tr[now].ch[s[i] - 'a'] = ++totr;
            tr[to].fa = now;
            ++d[now];
        }
        if (!i) tr[to].to.push_back(no), ++tr[to].sum;
        now = to;
    }
}

void up(int now)
{
    t[now].sum = t[t[now].c[0]].sum + t[t[now].c[1]].sum + 1;
}

void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

int dfs(int now, int root)
{
    if (!now) return root;
    root = dfs(t[now].c[0], root);
    root = dfs(t[now].c[1], root);
    root = ins(root, now);
    return root;
}

int merge(int u, int v)
{
    if (!u) return v;
    if (!v) return u;
    if (t[u].sum < t[v].sum) swap(u, v);
    return dfs(v, u);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    totr = 1;
    for (int i = 1; i <= n; ++i)
    {
        s = "";
        char c = getchar();
        while (!(c >= 'a' && c <= 'z')) c = getchar();
        while (c >= 'a' && c <= 'z')
        {
            s += c;
            c = getchar();
        }
        inss(i);
    }
    for (int i = 1; i <= n; ++i)
        scanf("%d", &k[i]);

    for (int i = 1; i <= totr; ++i)
        if (!d[i])
            q.push(i);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i)
        {
            int to = tr[now].ch[i];
            if (!to) continue;
            root[now] = merge(root[now], root[to]);
        }
        for (int i = 0; i < tr[now].to.size(); ++i)
            root[now] = ins(root[now], tr[now].to[i]);
        for (int i = 0; i < tr[now].to.size(); ++i)
        {
            int to = tr[now].to[i];
            if (k[to] > tr[now].sum) ans[to] = -1;
            else root[now] = ans[to] = query(root[now], k[to]);
        }
        if (!--d[tr[now].fa]) q.push(tr[now].fa);
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    fclose(stdin);fclose(stdout);
}

BZOJ 3218: a + b Problem【当网络流遇上可持久化线段树】

首先搞二元关系
这个本来的关系是一坨点 是否有一个点选择了白 这个不好弄
可以转换成 是否全部选择了黑

对每个点i新建一个点i’
含义是 点i之前的a值在li~ri范围的点 是不是全部选了黑色
i’选择了全部选黑且范围内某个点选了白的代价是inf
i’选择了不是全部选择了黑且i选择了黑的代价是pi

这样就可以得到correct ans了

但是这个的边数是n^2级的 too大to过
把上面的方程解了可以发现 范围内的点要向i‘连inf的边 这个的边数是n^2的 这个就是瓶颈

怎么办呢=-=
经过黄神的提醒(边数是nlogn级的
突然想到了这题是不是可以用可持久化线段树= =
线段树的权值表示a的权值
线段树的一个节点都代表了网络流的一个节点
一个节点[t, l, r]表示1~t号节点中 a值在l~r的都向这个点直接或间接的连了inf的边
查询就是把线段树中代表1~i-1中的a值在li~ri间的节点向当前的i’连边 可以知道最多log个节点
插入就是 对于一个新的点i 权值为ai 在可持久化线段树中插入到ai位置
对于经过的新建的点t last_t->t连inf的边 i->t连inf的边 last_t是上个线段树t位置的这个节点
每次新建也是log个点 log条边
所以总边数、点数都是nlogn

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
164
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;
const int inf = 0x3fffffff;
const int inf2 = 1000 * 1000 * 1000;

//===========================NetworkFlow===============

const int NFmaxn = 1000005;
const int NFmaxm = 1000005;
const int NFinf = 0x3fffffff;

struct NF_Line
{
  int to, next, v, opt;
};

struct Network_Flow
{
  NF_Line li[NFmaxm];
  int be[NFmaxn], l, s, t, n, num[NFmaxn], note[NFmaxn];

  void makeline(int fr, int to, int v)
  {
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
    li[l].opt = l + 1;

    ++l;
    li[l].next = be[to];
    be[to] = l;
    li[l].to = fr;
    li[l].v = 0;
    li[l].opt = l - 1;
  }

  void create(int N)
  {
    n = N;
  }

  int sap(int now, int maxf)
  {
    if (now == t) return maxf;
    int mi = n, tot = 0;
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (li[i].v && note[to] + 1 == note[now])
      {
        int k = sap(to, min(maxf - tot, li[i].v));
        li[i].v -= k;
        tot += k;
        li[li[i].opt].v += k;
        if (note[s] >= n || tot == maxf) return tot;
      }
      if (li[i].v) mi = min(mi, note[to]);
    }
    if (!tot)
    {
      if (!--num[note[now]])
      {
        note[s] = n;
        return 0;
      }
      ++num[note[now] = mi + 1];
    }
    return tot;
  }

  int query(int S, int T)
  {
    s = S, t = T;
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
    num[0] = n;
    int ans = 0;
    while (note[s] < n) ans += sap(s, NFinf);
    return ans;
  }

  void clear()
  {
    l = s = t = n = 0;
    memset(be, 0, sizeof(be));
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
  }
}nf;

//===========================NetworkFlow===============

struct node
{
    int l, r;
}t[maxn];

int n, m, root[maxn], tot, tot2, s, T, ans;

void query(int now, int l, int r, int lf, int rt, int p)
{
    if (!now) return;
    if (l >= lf && r <= rt)
    {
        nf.makeline(now, p, inf);
        return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) query(t[now].l, l, mid, lf, rt, p);
    if (rt >= mid + 1) query(t[now].r, mid + 1, r, lf, rt, p);
}

int ins(int no, int l, int r, int lr, int p)
{
    int now = ++tot;
    t[now] = t[no];
    if (no) nf.makeline(no, now, inf);
    nf.makeline(p, now, inf);
    if (l == r) return now;
    int mid = (l + r) / 2;
    if (lr <= mid) t[now].l = ins(t[no].l, l, mid, lr, p);
    else t[now].r = ins(t[no].r, mid + 1, r, lr, p);
    return now;
}

int main()
{
    scanf("%d", &n);
    s = ++tot, T = ++tot;
    for (int i = 1; i <= n; ++i)
    {
        int a, b, w, l, r, p, tp = ++tot, now = ++tot;
        scanf("%d%d%d%d%d%d", &a, &b, &w, &l, &r, &p);
        nf.makeline(tp, now, p);
        nf.makeline(s, now, w);
        nf.makeline(now, T, b);
        ans += w + b;
        query(root[i - 1], 0, inf2, l, r, tp);
        root[i] = ins(root[i - 1], 0, inf2, a, now);
    }
    nf.create(tot);
    printf("%d", ans - nf.query(s, T));
}

最小割小结

《浅析一类最小割问题(pty)》
这算是个解决最小割问题比较统一的方法吧 感觉是很厉害O.O
这个就是把最小割模型都转化成二元关系:(x,y)
x,y都取 代价为v1
x,y都不取 代价为v2
x取y不取 代价为v3
x不取y取 代价为v4
对于这个图233

a + b = v1
c + d = v2
a + d + f = v3
b + c + e = v4

令K = v3 + v4 – v1 – v2

如果 K < 0 那么关系图要是二分图就能做 把一侧的定义相反即可(这个的题目很少 不详写= = 首先要保证边权是非负的 K >= 0 e和f一定是非负的
可以看到每个等式中都出现了a、c中的一个 b、d中的一个
如果a、c中有边权是负的 可以把它们同时加上一个数 最后再扣掉
b、d同理
还有最好保证他们都是整数
如果出现小数 可以把所有边权都*=分母的最小公倍数 最后再除掉 (这个最小公倍数一般是2什么的= =)
然后就可以直接建图了

对于一些一元关系 某个点取有多少获利 不取有多少获利什么的 最后直接建边即可
这里对每对二元和一元关系的建边是独立的 最后再把边权加起来作为边权(不加也可以) 而不是比如对于每个二元关系s->p的权值都是一样的

注意这里求的是最小割 是最小值 有的题目求的是最大获利
有两种转化方法
一是把权值取负 然后求最小获利
二是比如你取了某个点 说明你不能不取这个点 就失去了不取这个点能获得的获利 这样就变成了最小代价了 然后最后把权值和-最小代价就是最大收益
↑其实这两个方法好像是等价的 看你怎么理解罢了=-=

==========BZOJ 3438: 小M的作物===========
这题是一个多元关系 但是也可以转成一元的
对于每个作物 s到它的边表示这个作物选择A 到t的边表示选择b
对于每个组合 新建两个点
一个点表示这些点是否全部选了A 这个点选择是的收益是c1i 否的收益是0
另外一个表示这些点是否全部选了B 这个点选择是的收益是c2i 否的收益是0
s到第一个点的边表示 是全部取A 到第二个点的边表示 不是全部取B
第一个点到t的边表示 不是全部取A 第二个点到t的边代表 是全部取B
如果第一个点选择了全部取了A 但是组合里的某个作物选择了B 这样的代价就是inf 因为是不可行的= =
对于B同理
这样就把多元关系转成了二元关系 很多多元关系的题目都可以用这个思路
然后把这个方程列啊列 最后建出来的图是一个类似最大权闭合子图的东西O.O

==========BZOJ 2127: happiness===========
这个就是非常模板的题
说一点0 0
在很多情况下可以设e=f(比如这题)
但是也有的时候设两个变量比较方便(比如上面那题) 自己看着办吧233

==========BZOJ 3218: a + b Problem===========
这题是厉害啊 我决定为这题独立开一篇文章 以表(pian)敬(I)意(P)