NO.-5

Veröffentlicht am | Edited on

P1921 赌博游戏

题目背景

赌场是暴利的。大赌场通过游戏规则控制游戏的公平来赚钱。虽然规则看似很公平，但实际上是稍微有点不公平的，而大赌场由于客流量大，资金流量大，这点稍微的不公平就被放大到能让赌场得到很可观的收入。同时，这些个不公平有时并不是规则的不公平，而是道具不公平。比如说灌铅的骰子，它和正常骰子不一样，它投出Q种点数的概率并不一样。有时，为了不让顾客察觉，他们每一次游戏结束后都有可能更换骰子。

题目描述

作弊的赌场有N个骰子，在这个赌场可能发生了M次游戏，每次游戏包括一个骰子投出的点数，我们并不知道这个骰子的编号，但知道第i次游戏投出的点数O(i)。

第i个骰子投出点数j的概率是A(i,j)，用完第i个骰子，下一次用第j个骰子的概率为B(i,j)。特别地，对于第一次游戏，用第i个骰子的概率为π(i)。

好奇的小v来问你，在这个赌场发生这M次游戏的概率。

输入输出格式

输入格式：

第一行两个正整数N，M，Q

第二行N个浮点数，表示π(i)

第三行至2+N行有N*Q个浮点数，第i+2行j列表示A(i,j)

第N+3至2N+2行有NN个浮点数，第N+2+i行j列表示B(i,j)

第2*N+3行有M个正整数，表示M次游戏的结果O[i]，也就是每次游戏投出的点数。

输出格式：

表示所求概率，保留四位位小数。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
3 10 3
1 0 0
0.03 0.03 0.94
0.02 0.02 0.96
0.99 0.005 0.005
0.01 0.99 0
0.05 0.05 0.90
0.98 0.002 0.008 
2 2 0 2 2 0 2 2 0 2

输出样例#1：

1
0.4483

说明

数据范围:

对于30%的数据：M<=100，1<=N，Q<=10

对于100%的数据：1<=M<=1000，1<=N，Q<=50

对于矩阵A，B，向量π都具备概率转移的特征条件

期望dp入门题,NOIp D1T2难度

首先我们能想到设计一个状态，使得可以转移到第m次游戏时完全匹配的概率，显然游戏的次数是一个状态维度。

而每次转移到下一次我们只需要知道上一次的骰子点数是多少，因此第二维我们就表示为结尾的骰子是什么。

转移就是

​

显然m次游戏后以任意骰子结尾都是合法的，因此

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#define maxn 55
#define maxq 55
#define maxm 1005
double pi[maxn] , A[maxn][maxq] , B[maxn][maxn] , f[maxm][maxn] ;
int res[maxm];
int  n , m , q;
double eps = 1e-6;
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lf",&pi[i]);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 0 ; j <= q-1 ; ++j)
            scanf("%lf",&A[i][j]);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            scanf("%lf",&B[i][j]);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d",&res[i]);
    for(int i = 1 ; i <= n ; ++i)
        f[1][i] = pi[i] * A[i][res[1]];
    for(int i = 2 ; i <= m ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            for(int k = 1 ; k <= n ; ++k)
                f[i][j] += f[i-1][k] * A[j][res[i]] * B[k][j];
    double ans = 0.00;
    for(int i = 1 ; i <= n ; ++i)
        ans += f[m][i];
    printf("%.4lf",ans);
}

P1613 跑路

题目描述

小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

输入输出格式

输入格式：

第一行两个整数n，m，表示点的个数和边的个数。

接下来m行每行两个数字u，v，表示一条u到v的边。

输出格式：

一行一个数字，表示到公司的最少秒数。

输入输出样例

输入样例#1：

复制

1
2
3
4
5
4 4
1 1
1 2
2 3
3 4

输出样例#1：

复制

1
1

说明

【样例解释】

1->1->2->3->4，总路径长度为4千米，直接使用一次跑路器即可。

【数据范围】

50%的数据满足最优解路径长度<=1000；

100%的数据满足n<=50，m<=10000，最优解路径长度<=maxlongint。

一看是

大致想到就是倍增了。

设

表示i,j之间的路径长度是否是

显然1也是2的次幂，所以每条边初始的时候就是

然后这些是

的都可以1s到达，所以再设dis跑最短路即可。

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 105
#define maxlog 45
bool f[maxn][maxn][maxlog];
int dis[maxn][maxn];
int n , m ,x , y;
int main()
{
    scanf("%d%d",&n,&m);
    std::memset(dis,30,sizeof(dis));//below the adjancent matrix!!!
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d",&x,&y);
        f[x][y][0] = true;//direct Graph !!! read carefully!
        dis[x][y] = 1;//init , do not forget!
    }
    for(int i = 1 ; i <= maxlog ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            for(int u = 1 ; u <= n ; ++u)
                for(int v = 1 ; v <= n ; ++v)
                    if(f[u][j][i-1] && f[j][v][i-1])
                        f[u][v][i] = true , dis[u][v] = 1;
    for(int k = 1 ; k <= n ; ++k)
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ; j <= n ; ++j)
                dis[i][j] = std::min(dis[i][j],dis[i][k] + dis[k][j]);
    printf("%d",dis[1][n]);

}

P1608 路径统计

题目描述

走一条从小镇1到小镇N花费最少的一条路，这个最少花费的路径有多少条？

输入输出格式

输入格式：

输入文件第一行为两个空格隔开的数N，E，表示这张地图里有多少个小镇及有多少边的信息。

下面E行，每行三个数I、J、C，表示从I小镇到J小镇有道路相连且花费为C.（注意，数据提供的边信息可能会重复，不过保证I<>J,1<=I,J<=n）。

输出格式：

输出文件包含两个数，分别是最少花费和花费最少的路径的总数.

两个不同的最短路方案要求：路径长度相同（均为最短路长度）且至少有一条边不重合。

若城市N无法到达则只输出一个(‘No answer’);

输入输出样例

输入样例#1：

1
2
3
4
5
5 4
1 5 4
1 2 2
2 5 2
4 1 1

输出样例#1：

1
4 2

说明

对于30%的数据 N<=20;

对于100%的数据 1<=N<=2000,0<=E<=N*(N-1), 1<=C<=10.

讲道理，真是4000000条边什么都跑不进一秒时限

最短路计数，SPFA或者DIJ都能完成。

SPFA最短路计数思想是，每更新一次就重置被更新点为当前点的数量，假如一样由加法原理就加上更新点的计数。

【算法思路】

我们直接对图跑一遍SPFA，只不过在修改每个点到起点的距离的同时，我们还需要使用一个cnt数组来记录到这个点的最短路径的路径数。并且当我们修改某个点到起点的最短距离时，需要进行一些额外的处理：

1.如果搜索到的点到起点的距离等于当前点到起点的距离加上这两点间的那条边的距离，那么我们就将搜索到的点的路径数加上当前点的路径数，即：

1
2
if(dis[i]==dis[k]+e[k][i])
    cnt[i]+=cnt[k];

2.如果我们更新了搜索到的点到起点的最短距离，那么我们将到达改点的路径数改为当前点的路径数，即：

1
2
3
4
if(dis[i]>dis[k]+e[k][i]){
    dis[i]=dis[k]+e[k][i];
    cnt[i]=cnt[k];
}

3.只有当一个点到起点的路径数不为0且未入队时，我们才将它放入队列。

【注意事项】

1、由于试题中存在重边（更详细的说应该是完全一样的边），并结合节点数小于等于2000这个数据范围，所以我们优先考虑使用邻接矩阵来保存边以方便预处理判重。

2、如果用于存边的二维数组定义的为int型，则初始化时建议不要将值设为2^31-1，否则有可能在中途比较的时候，算出来一些奇奇怪怪的东西。

3、如果搜索到的一条边的终点为n，那么我们应该跳过这一条边的搜索，而不是直接结束程序。

4、每次对取出来的点进行完搜索后，一定要将它的路径数清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
#include <bits/stdc++.h>
using namespace std;

int e[2010][2010],n,cnt[2010],dis[2010];
bool book[2010];

void spfa(int s,int t){
    queue <int> sta;
    sta.push(s);
    book[s]=1;
    cnt[s]=1;
    dis[s]=0;
    while(!sta.empty()){
        int k=sta.front();
        sta.pop();
        book[k]=0;
        if(k==t)
            continue;
        for(register int i=1;i<=n;i=-~i){
            if(dis[i]==dis[k]+e[k][i])
                cnt[i]+=cnt[k];
            if(dis[i]>dis[k]+e[k][i]){
                dis[i]=dis[k]+e[k][i];
                cnt[i]=cnt[k];
            }
            if(cnt[i] && !book[i]){
                book[i]=1;
                sta.push(i);
            }
        }
        cnt[k]=0;
    }
}

int main(){
    int x,y,z,i,j,k,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i=-~i)
        for(j=1;j<=n;j=-~j)
            e[i][j]=1000000000;
    while(m--){
        scanf("%d%d%d",&x,&y,&z);
        e[x][y]=min(e[x][y],z);
    }
    for(i=1;i<=n;i=-~i)
        dis[i]=1000000000;
    spfa(1,n);
    if(dis[n]==1000000000)
        printf("No answer");
    else
        printf("%d %d",dis[n],cnt[n]);
    return 0;
}

而我想的则是更加（稳定）好想的DIJ，由DIJ原理可知，当前出队的点一定是最短路了，这样更新其他点后也不用清空，而且一点也不玄学。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define pii std::pair<int,int>
#define mp(x,y) std::make_pair((x),(y))
#define maxn 2005
int g[maxn][maxn];
int head[maxn] , tot  , n , m , d[maxn];
struct edge{
    int next , to , dis;
}e[maxn*maxn];
inline void add(int x , int y , int d)
{
    e[++tot].next = head[x];
    e[tot].to = y;
    e[tot].dis = d;
    head[x] = tot;
}
namespace CNT{
    bool vis[maxn];
    long long cnt[maxn];
    inline void DIJCNT(int s)
    {
        std::priority_queue<pii,std::vector<pii> , std::greater<pii> > q;
        std::memset(d,0x7f,sizeof(d));
        d[s] = 0 , cnt[s] = 1;
        q.push(mp(d[s],s));
        while(!q.empty())
        {
            int k = q.top().second;
            q.pop();
            if(vis[k]) continue;
            vis[k] = true;
            for(int i = head[k] ; i ; i = e[i].next)
            {
                if(d[k] + e[i].dis < d[e[i].to])
                {
                    d[e[i].to] = d[k] + e[i].dis;
                    cnt[e[i].to] = cnt[k];
                    q.push(mp(d[e[i].to],e[i].to));
                }
                else if(d[k] + e[i].dis == d[e[i].to])
                    cnt[e[i].to] += cnt[k];
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int x , y , dis;
    std::memset(g,0x7f,sizeof(g));
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d%d",&x,&y,&dis);
        g[x][y] = std::min(g[x][y],dis) ;
    }
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            if(i != j && g[i][j])
                add(i,j,g[i][j]);
    CNT::DIJCNT(1);
    if(d[n] > 80000000)
    {
        puts("No answer");
        return 0;
    }
    printf("%d %lld", d[n] , CNT::cnt[n]);
}

关于如何使用unordered_map

1
2
#include <tr1\unordered_map>
std::tr1::unordered_map<int,int> mapa;

有时间练练这个好东西qwq

P1342 请柬

题目描述

给定一个有向图，求源点到所有点的最短路之和与所有点到源点的最短路之和。

输入输出格式

输入格式：

第1行有两个整数n、m，n是点数，m是有向边数。

输出格式：

输出一行，表示所求答案。

数据范围

题解：

首先从源点跑一边单源最短路，然后计算源点到各点的最短路距离之和。

接下来显而易见的做法是从每个点跑单源最短路到源点，但那样显然会超时。

我们这么想，假设s - > v 的单源最短路是从v得到的，那我们反向建边是不是还是能的到最短路呢？

答案是肯定的，显然原图和反向图的任意一条路径都可以一一对应，因此原先从v ->s的最短路就对应s->v的最短路。这样我们再跑一遍最短路就可以了

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define pii std::pair<int,int>
#define mp(x,y) std::make_pair((x),(y))
#define maxn 1000005
#define ll long long
ll head[maxn] , cnt , d[maxn] , n , m , x , y ,dis;
bool vis[maxn];
std::priority_queue<pii , std::vector<pii> , std::greater<pii> > q;
struct edge{
    ll next , to , dis;
}e[maxn*2];
struct getE{
    ll from , to , dis;
}g[maxn*2];
inline void SPDIJ(int s)
{
    std::memset(d,0x7f,sizeof(d));
    std::memset(vis,false,sizeof(vis));
    d[s] = 0;
    q.push(mp(d[s],s));
    while(!q.empty())
    {
        ll k = q.top().second;
        q.pop();
        if(vis[k])  continue;
        vis[k] = true;
        for(int i = head[k] ; i ; i = e[i].next)
             if(d[k] + e[i].dis < d[e[i].to])
                d[e[i].to] = d[k] + e[i].dis , q.push(mp(d[e[i].to],e[i].to));
    }
}
inline void add(ll x, ll y , ll dis)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].dis = dis;
    head[x] = cnt;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%lld%lld%lld",&x,&y,&dis) , add(x,y,dis) , g[i].from = x , g[i].to = y , g[i].dis = dis;
    SPDIJ(1);
    unsigned ll ans = 0;
    for(int i = 1 ; i <= n ; ++i)
        ans += d[i];
    cnt = 0;
    std::memset(head,0,sizeof(head));
    std::memset(e,0,sizeof(e));
    for(int i = 1 ; i <= m ; ++i)
        add(g[i].to,g[i].from,g[i].dis);
    SPDIJ(1);
    for(int i = 1 ; i <= n ; ++i)
        ans += d[i];
    printf("%llu",ans);
}

题目描述

给定序列A，给定数k，求序列长度<=k的区间中的最大子段和是多少。

对20%的数据，N≤100。

对100%的数据，N≤500000，|Pi|≤500。 答案保证在2^31-1之内。

题解

一道挺不错的单调队列的题（当然不卡常的数据优先队列也能过）

首先考虑枚举右端点r，左端点的范围是[r-k+1,r-1]，显然对于所有以当前点为右端点的区间，我们只需要找出最小的左端点范围的前缀，这样一减就是最大的。如何求那个最小的左端点的前缀决定了程序效率，单调队列均摊每次O1，效率最高。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
// #include <tr1\unordered_map>
#define maxn 500005
#define maxlog 28
#define pii std::pair<int,int>
int t[maxn] , n , m , ans = -0x7ffffff , s[maxn];
std::deque<int> q;
// std::tr1::unordered_map<int,int> mapa;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&t[i]);
    for(int i = 1 ; i <= n ; ++i)
        s[i] = s[i-1] + t[i];
    for(int i = 1 ; i <= m ; ++i)
    {
        while(!q.empty() && s[q.back()] > s[i]) q.pop_back();
        q.push_back(i);
        ans = std::max(ans , s[q.front()]);
    }
    for(int i = m + 1 ; i <= n ; ++i)
    {
        while(!q.empty() && s[q.back()] >= s[i]) q.pop_back();
        while(!q.empty() && q.front() < i - m) q.pop_front();
        q.push_back(i);
        ans = std::max(ans,s[i] - s[q.front()]);
    }
    printf("%d",ans);
}

简单题意

要求单次查询森林的某树链最小边logn

题解：

倍增优化 +　最大生成树

显然我们尽可能使两点间的边最大就可以，因为题意是两点路径中的最小边，不难想是最大生成树，由Kruskal的贪心思想也能想到 ， 因为一条边不在最大生成树上要么是已经选了n-1条边，这条边肯定没有用，要么是这条边连接的两点已经被前面更大的边联通，这条边依然没用。

然后在最大生成树上倍增即可。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 10005
#define min(a,b) (a) < (b) ? (a) : (b)
int f[maxn][16] , depth[maxn] , n , m , cnt , q , x , y , z , g[maxn][16] , u , v , fr , head[maxn] , pedge , uf[maxn] , tot = 1 , lg[maxn];
struct edge{
    int next ,to ,dis;
}mst[maxn*2+5];
struct pic{
    int from , to , dis;
}p[maxn*10];
inline bool cmp(pic a , pic b){return a.dis > b.dis;}
inline void add(int from , int to , int dis)
{
    mst[++cnt].next = head[from];
    mst[cnt].to = to;
    mst[cnt].dis = dis;
    head[from] = cnt;
}
int find(int x)
{
    if(uf[x] != x) uf[x] = find(uf[x]);
    return uf[x];
}
void dfs(int x , int fa , int dis)
{
    depth[x] = depth[fa] + 1;
    f[x][0] = fa;
    g[x][0] = dis;
    for(int i = head[x] ; i ; i = mst[i].next)
        if(mst[i].to != fa)
             printf("%d -- %d[label = \"%d\"]\n" , x,mst[i].to) ,dfs(mst[i].to,x,mst[i].dis);
}
inline void optimacal()
{
    for(int i = 1 ; i <= n ; ++i)
        lg[i] = lg[i-1] + (1<<lg[i-1] == i);
    for(int j = 1 ; j <= 15 ; ++j)
        for(int i = 1 ; i <= n ; ++i)
            f[i][j] = f[f[i][j-1]][j-1];
    for(int j = 1 ; j <= 15 ; ++j)
        for(int i = 1 ; i <= n ; ++i)
            g[i][j] = min(g[f[i][j-1]][j-1],g[i][j-1]) ;//, printf("g[%d][%d] = %d\n",i,j,g[i][j])
 
}
inline int LCA(int x , int y)
{
    int ans = 0x7fffffff;
    if(depth[x] < depth[y]) std::swap(x,y);
    while(depth[x] > depth[y])
         ans = min(ans,g[x][lg[depth[x]-depth[y]]-1]) , x = f[x][lg[depth[x]-depth[y]]-1] ;
    if(x == y) return ans;
    for(int i = lg[depth[x]] ; i >= 0 ; --i)
        if(f[x][i] != f[y][i])
            ans = min(ans,min(g[x][i],g[y][i])) , x = f[x][i] , y = f[y][i] ;
    return min(ans,min(g[x][0],g[y][0]));
}
 
int main()
{
    // freopen("graph.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        p[++pedge].from = x , p[pedge].to = y ;
        p[++pedge].from = y , p[pedge].to = x ;
        p[pedge].dis = p[pedge-1].dis = z;
    }
    std::sort(p+1,p+2*m+1,cmp);
    for(int i = 1 ; i <= n ; ++i)
        uf[i] = i;
    for(int i = 1 ; tot < n && i <= 2*m; ++i)
    {
        int fx = find(p[i].from) , fy = find(p[i].to);
        if(fx != fy)
        {
            add(p[i].from,p[i].to,p[i].dis) , add(p[i].to,p[i].from,p[i].dis);
            // printf("%d %d\n",p[i].from,p[i].to);
            uf[fx] = fy;
            ++tot;
        }
     }
    for(int i = 1 ; i <= n ; ++i)
        if(find(i) != find(i-1))
            dfs(i,0,0);
    printf("1");
    printf("tot = %d\n",tot);
    optimacal();
    scanf("%d",&q);
    for(int i = 1 ; i <= q ; ++i)
    {
        scanf("%d%d",&u,&v);
        int ans = LCA(u,v);
        if(!ans)
        {
            printf("-1\n");
            continue;
        }
        printf("%d\n",ans);
    }
 
}