NationalDay3

Veröffentlicht am | Edited on

关于WQS二分 ， 是用来解决这样一类问题

强制选k个某属性的物品，要求最优方案。

[国家集训队2]Tree I

题目描述

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。

题目保证有解。

输入输出格式

输入格式：

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行

每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

输出格式：

一行表示所求生成树的边权和。

输入输出样例

输入样例#1：

1
2
3
2 2 1
0 1 1 1
0 1 2 0

输出样例#1：

1
2

说明

0:V<=10

1,2,3:V<=15

0,..,19:V<=50000,E<=100000

所有数据边权为[1,100]中的正整数。

By WJMZBMR

题解

这道题是WQS二分的经典题目

我们二分白边边权增量，对于每次二分后排序做Kruskal最小生成树。边权相同优先让白边靠前。

这样显然减少增量白边会多，增加增量白边会少。

我这样写后交上去并不对，代码如下

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
// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#define maxn 50500
int cnt , x , y , d , n , m , c , need , f[maxn] , tot , Wcol , mst , ans;
struct E{
    int from , to , dis , col;
}q[maxn * 4] , p[maxn * 4];
int find(int x)
{
    if(f[x] != x) return f[x] = find(f[x]);
    return f[x];
}
inline bool cmp(E x , E y)
{
    if(x.dis == y.dis) return x.col < y.col;
    return x.dis < y.dis;
}
int main()
{
    scanf("%d%d%d",&n,&m,&need);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d%d%d",&q[i].from , &q[i].to , &q[i].dis , &q[i].col) , ++ q[i].from , ++ q[i].to;
    int l = -150 , r = 150;
    while(l <= r)
    {
        // printf("l = %d r = %d\n", l , r);
        int mid = l + r >> 1;//the addition
        cnt = 0 , tot = 0 , Wcol = 0 , mst = 0;
        for(int i = 1 ; i <= n ; ++i)
            f[i] = i;
        for(int i = 1 ; i <= m ; ++i)
            p[i] = q[i];
        for(int i = 1 ; i <= m ; ++i)
            if(!p[i].col)
                p[i].dis += mid;
        std::sort(p+1,p+m+1,cmp);
        for(int i = 1 ; i <= m && tot < n - 1 ; ++i)
        {
            int fx = find(p[i].from) , fy = find(p[i].to);
            if(fx != fy)
            {
                f[fx] = fy;
                mst += p[i].dis;
                if(!p[i].col) ++Wcol;
                ++tot;
            }
        }
        if(Wcol > need) l = mid + 1;// Wcol will decrease
        else if(Wcol == need)   {ans = mst - need * mid ; l = mid + 1;}
        else r = mid - 1; // Wcol will be larger
        // putchar(10);
    }
    printf("%d\n",ans);
}

但是这会有一个问题，白边优先意味着当前状况可能尽管白边数大于黑边数，但是完全可以用黑边替换白边。那么我们可以只要当前白边数够大就更新答案。

为什么这个做法是正确的呢？因为我们在白边数大的时候还会给白边更大的增量，假如依然白边数>=指定边数，那么说明原来那种是不能用黑边替换的或者和原来的情况一样或者比原来的情况更优。不管怎么样都能更新答案，只要一直保证白边数不小于黑边，就能确保最后的答案是正好need条白边（由数据保证）。

Code:

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
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#define maxn 50500
int cnt , x , y , d , n , m , c , need , f[maxn] , tot , Wcol , mst , ans;
struct E{
    int from , to , dis , col;
}q[maxn * 4] , p[maxn * 4];
int find(int x)
{
    if(f[x] != x) return f[x] = find(f[x]);
    return f[x];
}
inline bool cmp(E x , E y)
{
    if(x.dis == y.dis) return x.col < y.col;
    return x.dis < y.dis;
}
int main()
{
    scanf("%d%d%d",&n,&m,&need);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d%d%d",&q[i].from , &q[i].to , &q[i].dis , &q[i].col) , ++ q[i].from , ++ q[i].to;
    int l = -150 , r = 150;
    while(l <= r)
    {
        int mid = l + r >> 1;//the addition
        cnt = 0 , tot = 0 , Wcol = 0 , mst = 0;
        for(int i = 1 ; i <= n ; ++i)
            f[i] = i;
        for(int i = 1 ; i <= m ; ++i)
            p[i] = q[i];
        for(int i = 1 ; i <= m ; ++i)
            if(!p[i].col)
                p[i].dis += mid;
        std::sort(p+1,p+m+1,cmp);
        for(int i = 1 ; i <= m && tot < n - 1 ; ++i)
        {
            int fx = find(p[i].from) , fy = find(p[i].to);
            if(fx != fy)
            {
                f[fx] = fy;
                mst += p[i].dis;
                if(!p[i].col) ++Wcol;
                ++tot;
            }
        }
        if(Wcol >= need) ans = mst - need * mid  , l = mid + 1;
        else r = mid - 1; // Wcol will be larger
        // putchar(10);
    }
    printf("%d\n",ans);
}

[SHOI2014]概率充电器

题目描述

著名的电子产品品牌SHOI 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器：

“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决 定！SHOI 概率充电器，您生活不可或缺的必需品！能充上电吗？现在就试试看 吧！”

SHOI 概率充电器由n-1 条导线连通了n 个充电元件。进行充电时，每条导 线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率 决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行 间接充电。

作为SHOI 公司的忠实客户，你无法抑制自己购买SHOI 产品的冲动。在排 了一个星期的长队之后终于入手了最新型号的SHOI 概率充电器。你迫不及待 地将SHOI 概率充电器插入电源——这时你突然想知道，进入充电状态的元件 个数的期望是多少呢？

输入输出格式

输入格式：

第一行一个整数：n。概率充电器的充电元件个数。充电元件由1-n 编号。

之后的n-1 行每行三个整数a, b, p，描述了一根导线连接了编号为a 和b 的 充电元件，通电概率为p%。

第n+2 行n 个整数：qi。表示i 号元件直接充电的概率为qi%。

输出格式：

输出一行一个实数，为能进入充电状态的元件个数的期望，四舍五入到小 数点后6 位小数。

输入输出样例

输入样例#1：

1
2
3
4
3
1 2 50
1 3 50
50 0 0

输出样例#1：

1
1.000000

输入样例#2：

1
2
3
4
5
6
5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40

输出样例#2：

1
4.300000

说明

对于30%的数据，n≤5000。

对于100%的数据，n≤500000，0≤p,qi≤100。

题解

这道题是道不错的概率DP入门题

显然对于每个点，我们要考虑它自己亮的概率，被它父亲点亮的概率，被他孩子点亮的概率.

为了高效率，显然我们可以进行树形DP

显然这个题概率不好正着推，WZX大佬说这题随便正着推，真是太强啦！

我们设

表示x不被子树节点点亮的概率，不被子树外点亮的概率。

比较好推

其中

表示子节点连向父亲的导线通电的概率。

对于

转移,我想了好久，其实十分的简单。

我们先求出父亲不被外部点亮的概率

这就是一个点最终对于孩子节点没有电的概率。

因此

类似刷表法的down过程就结束了

这就是树形dp的 up and down

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
int  n , head[maxn] , cnt , fa[maxn];
double f[maxn] , v[maxn] , g[maxn];
struct edge{
    int next , to ;
    double dis;
}e[maxn * 2];
inline void add(int x , int y , double d)
{
    e[++cnt].next = head[x] ;
    e[cnt].to = y ;
    e[cnt].dis = d;
    head[x] = cnt;
}

void up(int x , int fx)
{
    f[x] = 1 - v[x];
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            up(e[i].to , x) , f[x] *= f[e[i].to] + (1 - f[e[i].to]) * (1 - e[i].dis);
}
void down(int x , int fx)
{
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
        {
            double DarkX = g[x] * f[x] / (f[e[i].to] + (1 - f[e[i].to]) * (1 - e[i].dis));
            g[e[i].to] = DarkX + (1 - DarkX) * (1 - e[i].dis);
            down(e[i].to , x);
        }
}
int main()
{
    scanf("%d",&n);
    int x , y ;
    double d;
    for(int i = 1 ; i <= n - 1; ++i)
        scanf("%d%d%lf",&x,&y,&d) , add(x,y,d/100) , add(y,x,d/100);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lf",&v[i]) , v[i] /= 100;
    up(1 , 1);
    g[1] = 1;//the
    down(1 , 1);
    double ans = 0;
    for(int i = 1 ; i <= n ; ++i)
        ans += 1 - f[i] * g[i];
    printf("%.6lf",ans);

}

多人背包

题目描述

求01背包前k优解的价值和

输入输出格式

输入格式：

第一行三个数K、V、N

接下来每行两个数，表示体积和价值

输出格式：

前k优解的价值和

输入输出样例

输入样例#1：

1
2
3
4
5
6
2 10 5
3 12
7 20
2 4
5 6
1 1

输出样例#1：

1
57

说明

对于100%的数据,

题解

这是道好题。

对于背包问题，显然每件物品是独立的子问题。

很容易发现,我们需要记录用其他物品来填充背包是否能得到更优解.

因此我们需要记录一个变量c1表示体积为j的时候的第c1优解能否被更新.

再去记录一个变量c2表示体积为j-v[i]的时候的第c2优解.

更新到k就可以的（雾

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 205
#define maxk 55
#define maxm 5005
int f[maxm][maxk] , n , m , k , ans , w[maxn] , v[maxn] , now[maxn];
int main()
{
    scanf("%d%d%d",&k,&m,&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d%d",&w[i],&v[i]);
    std::memset(f,-70,sizeof(f));
    f[0][1] = 0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = m ; j >= w[i] ; --j)
        {
            std::memset(now,0,sizeof(now));
            int c1 = 1 , c2 = 1 , cnt = 0;
            while(cnt <= k)
            {
                if(f[j - w[i]][c1] + v[i] > f[j][c2])
                    now[++cnt] = f[j - w[i]][c1] + v[i] , ++c1;
                else now[++cnt] = f[j][c2] , ++c2;
            }
            for(int c = 1 ; c <= k ; ++c) f[j][c] = now[c];
        }
    for(int i = 1 ; i <= k ; ++i)
        ans += f[m][i];
    printf("%d",ans);
}

[SCOI2003]严格N元树

递推的好题

题目描述

如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：

给出n, d，编程数出深度为d的n元树数目。

输入输出格式

输入格式：

仅包含两个整数n, d(0<n<=32, 0<=d<=16)。输入数据保证你不需要考虑某一层多于1024个节点的树（即nd<=1024）。提示：答案保证不超过200位十进制数。

输出格式：

仅包含一个数，即深度为d的n元树的数目。

输入输出样例

输入样例#1：

1
2 2

输出样例#1：

1
3

输入样例#2：

1
2 3

输出样例#2：

1
21

输入样例#3：

1
3 5

输出样例#3：

1
58871587162270592645034001

题解

这个题有巧妙地构造递推方式，也有相当理性的组合数学方法，主要考虑巧妙地构造方式。

很好想的想到深度不超过d的数量设为

, 最后答案是

然后很好想到每次深度多一我们只需要在最上面加一个根，那么根上还得有(n-1)颗子树。因此

于是很简单地就AC了

Code:

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 55000
using namespace std;
struct bign{
    int d[maxn], len;

    void clean() { while(len > 1 && !d[len-1]) len--; }

    bign()          { memset(d, 0, sizeof(d)); len = 1; }
    bign(int num)   { *this = num; }
    bign(char* num) { *this = num; }
    bign operator = (const char* num){
        memset(d, 0, sizeof(d)); len = strlen(num);
        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
        clean();
        return *this;
    }
    bign operator = (int num){
        char s[2000]; sprintf(s, "%d", num);
        *this = s;
        return *this;
    }

    bign operator + (const bign& b){
        bign c = *this; int i;
        for (i = 0; i < b.len; i++){
            c.d[i] += b.d[i];
            if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
        }
        while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
        c.len = max(len, b.len);
        if (c.d[i] && c.len <= i) c.len = i+1;
        return c;
    }
    bign operator - (const bign& b){
        bign c = *this; int i;
        for (i = 0; i < b.len; i++){
            c.d[i] -= b.d[i];
            if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
        }
        while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
        c.clean();
        return c;
    }
    bign operator * (const bign& b)const{
        int i, j; bign c; c.len = len + b.len;
        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)
            c.d[i+j] += d[i] * b.d[j];
        for(i = 0; i < c.len-1; i++)
            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
        c.clean();
        return c;
    }
    bign operator / (const bign& b){
        int i, j;
        bign c = *this, a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            c.d[i] = j;
            a = a - b*j;
        }
        c.clean();
        return c;
    }
    bign operator % (const bign& b){
        int i, j;
        bign a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            a = a - b*j;
        }
        return a;
    }
    bign operator += (const bign& b){
        *this = *this + b;
        return *this;
    }

    bool operator <(const bign& b) const{
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
            if(d[i] != b.d[i]) return d[i] < b.d[i];
        return false;
    }
    bool operator >(const bign& b) const{return b < *this;}
    bool operator<=(const bign& b) const{return !(b < *this);}
    bool operator>=(const bign& b) const{return !(*this < b);}
    bool operator!=(const bign& b) const{return b < *this || *this < b;}
    bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}

    string str() const{
        char s[maxn]={};
        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
        return s;
    }
};

istream& operator >> (istream& in, bign& x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream& out, const bign& x)
{
    out << x.str();
    return out;
}
bign f[20] , g;
int n , d;
int main()
{
    scanf("%d%d",&n,&d);
    f[0] = 1;
    for(int i = 1 ; i <= d ; ++i)
    {
        bign g = 1;
        for(int j = 1 ; j <= n ; ++j)
            g = g * f[i-1];
        // std::cout << g << endl;
        f[i] = g + 1;
    }
    std::cout<<f[d] - f[d-1];
}