Dylan's Blog

BZOJ3036 绿豆蛙的归宿 [概率期望DP]

Posted on 2018-08-01 Edited on 2022-06-05 In 题解

问题描述：

给出一个有向无环的连通图，起点为$1$终点为$N$，每条边都有一个长度。绿豆蛙从起点出发，走向终点。

到达每一个顶点时，如果有$K$条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 $1/K$ 。

现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入：

第一行: 两个整数 $N$,$M$，代表图中有$N$个点、$M$条边第二行到第$1+M$行: 每行3个整数$a,b,c$，代表从$a$到$b$有一条长度为$c$的有向边

输出：

从起点到终点路径总长度的期望值，四舍五入保留两位小数

思路：

这个的期望按照套路应该反着求，所以我们反向建边，从终点开始进行概率DP。对于DAG上的DP当然要基于拓扑排序啦，然后DP之类的都很简单，看代码就好了。

代码：

#include <bits/stdc++.h>
#define MAXN 200005
#define LL long long
using namespace std;

int n, m, cnt, head[MAXN], deg[MAXN],temp[MAXN];
double dis[MAXN];

struct Edge {int next, to, dis;} edge[MAXN];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    deg[to]++;
    head[from]=cnt;
}


void topsort()
{
    queue<int> q;
    q.push(n);
    while(!q.empty())
    {
        int tot=0;
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            dis[to]+=(dis[x]+edge[i].dis)/temp[to];
            //printf("%d %d %lf %lf!!!\n", x, to, temp[to], dis[to]);
            if(deg[to]<=0) continue;
            deg[to]--;
            if(!deg[to]) q.push(to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(y, x, z);
    }
    memcpy(temp, deg, sizeof(deg));
    topsort();
    printf("%.2lf\n", dis[1]);
}

BZOJ3054 Rainbow的信号 [概率期望DP]

Posted on 2018-08-01 Edited on 2022-06-05 In 题解

问题描述：

在1~N这N个数中，等概率地选取两个数l、r，如果l>r，则交换l、r。把信号中的第l个数到第r个数取出来，构成一个数列P。

A部分对话的密码是数列P的xor和的数学期望，B部分对话的密码是数列P的and和的期望，C部分对话的密码是数列P的or和的期望。你需要求出A，B，C三部分对话的密码。

输入：

第一行一个正整数N 第二行N个自然数

输出：

一行三个实数，分别表示xor和、and和、or和的期望，四舍五入保留3位小数

思路：

比较考验思维的一道题呢。因为操作都是位运算，所以我们可以分别考虑每一位的期望值，从而计算出对答案的贡献。我们把这$n$个数的第$i$位拿出来存在数组$b$中，$b[k]$就是第$k$个数的第$i$位。

一共有$n^2$种情况，选出长度为1区间的概率为$1/n^2$，选出其余区间的概率为$2/n^2$。我们可以先统计长度为1区间对答案的贡献，再计算其余区间的贡献。因为有三种操作，所以我们要对每一种操作分别计算：

and操作：这个比较简单，我们从左到右枚举右端点，用last记录上一次0的出现位置。那么以$r$为右端点and值为1的区间有$(r-last-1)$个，然后乘上概率，再求和就可以求出这这一位的期望了。
or操作：这个和上一个类似也比较容易，用last记录上一次1的出现位置。如果位置$r$的数为1，就有$r-1$个区间or值为1；如果位置为$r$为0，就有$last$个区间为1，不要忘了乘上概率。
xor操作：这个稍微复杂，我们先前缀异或一下，然后分别记录位置$r$前前缀异或值的数量记为$cnt[0],cnt[1]$。设位置$r$的前缀异或值为$c[r]$，那么xor值为1的区间就有$cnt[c[r]^1]$个。类似的，我们也可以算出期望。

最后，我们对每一位对期望就一个和就可以算出答案了。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define INF 1e18
#define LB long double
#define MAXN 2000005
using namespace std;

int n, a[MAXN], b[MAXN], c[MAXN];
LL ans[4];

LL getxor()
{
    LL sum=0, cnt[2]={0};
    memcpy(c, b, sizeof(b));
    for(int i=1; i<=n; i++) sum+=c[i];
    for(int i=1; i<=n; i++)
    {
        c[i]^=c[i-1];
        sum+=2*cnt[c[i]^1];
        cnt[c[i-1]]++;
    }
    return sum;
}

LL getand()
{
    LL sum=0, last=0;
    for(int i=1; i<=n; i++) sum+=b[i];
    for(int i=1; i<=n; i++)
    {
        if(b[i]==0) last=i;
        else sum+=2*(i-last-1);
    }
    return sum;
}

LL getor()
{
    LL sum=0, last=0;
    for(int i=1; i<=n; i++) sum+=b[i];
    for(int i=1; i<=n; i++)
    {
        if(b[i]==0) sum+=2*last;
        else sum+=2*(i-1), last=i;
    }
    return sum;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=0; i<=30; i++)
    {
        for(int j=1; j<=n; j++) b[j]=(a[j]>>i)&1;
        ans[1]+=getxor()*(1<<i);
        ans[2]+=getand()*(1<<i);
        ans[3]+=getor()*(1<<i);
    }
    printf("%.3Lf %.3Lf %.3Lf", (LB)ans[1]/(1LL*n*n), (LB)ans[2]/(1LL*n*n), (LB)ans[3]/(1LL*n*n));
}

BZOJ2115 最大XOR和路径 [线性基]

Posted on 2018-07-30 Edited on 2022-06-05 In 题解

问题描述：

考虑一个边权为非负整数的无向连通图，节点编号为$1$到$N$，试求出一条从 $1$号节点到$N$号节点的路径，使得路径上经过的边的权值的 XOR 和最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数。

输入：

第一行包含两个整数$N(n<=50000)$和$M(m<=100000)$，表示该无向图中点的数目与边的数目。接下来$M$行描述$M$条边，每行三个整数$S_i,T_i,D_i$，表示$S_i$与$T_i$之间存在一条权值为$D_i$的无向边（图中可能有重边或自环）

输出：

仅包含一个整数，表示最大的 XOR 和

思路：

这种玄学的做法自然的想不到的啦。。。

首先异或路径有一个很有趣的地方就是你可以“瞬移”到任何地方，严谨的说就是你从$x$到$y$，再从$y$回到$x$这一段路径对答案的贡献为0。所以你从1到n的路径可以看成是：一条1到n的简单路径加上图中的一些环。形象的说就是你可以瞬移到环上一点绕一圈再瞬移回来。

如果只有一条1到n的路径，我们就可以直接利用线性基求出它们的最大异或和就好了。但如果有多条路径该如何维护？其实这也很简(xuan)单(xue)，随意选任意一条就好了！！因为这多条路径其实是构成了多个环的，如果你选了一条使答案更小路径，那么你再选这个路径构成的环就好了。那条小的路径走了两遍，相当于你走了另一条路径。所以你可以随意选一条路径，同样用线性基维护就好了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100005
#define LL long long
using namespace std;

int n, m, cnt, tot, head[MAXN];
LL ans, dis[MAXN], cir[MAXN], base[MAXN];
bool vis[MAXN];

struct Edge {int next, to; LL dis;} edge[MAXN*2];

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void insert(LL x)
{
    for(int i=62; i>=0; i--)
    {
        if(!(x>>i)) continue;
        if(!base[i])  {base[i]=x; break;}
        x^=base[i];
    }
}

void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to])
        {
            dis[to]=dis[x]^edge[i].dis;
            dfs(to);
        }
        else insert(dis[to]^edge[i].dis^dis[x]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    dfs(1);
    ans=dis[n];
    for(int i=62; i>=0; i--)
        if((ans^base[i])>ans) ans=ans^base[i];
    printf("%lld\n", ans);
}

Codeforces Round #500 解题报告

Posted on 2018-07-30 Edited on 2022-06-05 In 解题报告

7月30号 Codeforces Round #500 题目链接：http://codeforces.com/contest/1013

A - Piles With Stones

过水，不说。

B - And

思路： 首先可以发现答案只能是-1,0,1,2，所以我们一个一个判断。如果已经有重复元素，答案就是0；如果与x后有重复元素，答案就是1；如果两个元素与x后相等，答案就是2；其余的情况答案就是-1。然后就是一些细节注意处理。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define INF 0x3f3f3f3f
#define MAXN 1000005
#define LL long long
#define LB long double
using namespace std;

int n, k, a[MAXN], vis1[MAXN], vis2[MAXN];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), vis1[a[i]]++;
    for(int i=1; i<=n; i++) if(vis1[a[i]]>=2)
    {
        printf("0\n");
        return 0;
    }
    for(int i=1; i<=n; i++)
        if(a[i]!=(a[i]&k)) vis2[a[i]&k]++;
    for(int i=1; i<=n; i++) if(vis2[a[i]]>=1) 
    {
        printf("1\n");
        return 0;
    }
    for(int i=1; i<=n; i++) if(vis2[a[i]&k]>=2)
    {
        printf("2\n");
        return 0;
    }
    printf("-1\n");
    return 0;
}

C - Photo of The Sky

思路： 蛮神奇的一题。我们可以先将这些坐标排序，并将它们分为两类，横坐标集合与纵坐标集合。可以发现横坐标集合一定是连续的n个，如果你随意交换一对使它不连续，那么纵坐标的极差不变，很坐标的极差增大了，而答案就是两个极差之积。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define INF 1e18+5
#define MAXN 100005
#define LL long long
#define LB long double
using namespace std;

int n;
LL ans=INF, a[MAXN*2];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n*2; i++) scanf("%lld", &a[i]);
    sort(a+1, a+2*n+1);
    for(int i=1; i<=n; i++)
    {
        LL x=a[i+n-1]-a[i], y;
        if(i==1) y=a[2*n]-a[n+1];
        else y=a[2*n]-a[1];
        if(x*y<ans) ans=x*y;
    }
    printf("%lld\n", ans);
}

D - Chemical table

思路： 首先用类似于连二分图的方法连边，把行和列作为节点。那么可以发现，我们要做的就是使整个图变为一个联通块。于是我们可以统计联通块个数，每加一个点就相当于连一条边，所以我们只需要加联通块个数-1个点就好了。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 500005
using namespace std;

int n, m, q, cnt, ans, head[MAXN], x[MAXN], y[MAXN];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to]) dfs(to);
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=q; i++)
    {
        scanf("%d%d", &x[i], &y[i]);
        addedge(x[i], y[i]+n);
        addedge(y[i]+n, x[i]);
    }
    for(int i=1; i<=n+m; i++)
        if(!vis[i]) dfs(i), ans++;
    printf("%d\n", ans-1);
}

E - Hills

思路： 就是一个DP，首先我们设$f[i][j][k]$为第i个位置，建了j座房子所花的代价，$k$表示在位置$i$有没有建房子。然后我可以把位置$i$造房子的代价拆成两个：把左边变的更低的代价$l[i]$，把右边变得更低的代价$r[i]$。

然后就按照DP来，转移方程就看代码吧（懒得写了）。其中有一些细节要注意：如果两座房子中间之隔了一个，那么前一座房子的代价$r[i]$与这一座房子的代价$l[i]$有重合，于是我们特别地把这时的代价记为$val$，于是转移时还要特别考虑这个情况。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 5005
#define INF 0x3f3f3f
using namespace std;

int n, a[MAXN], l[MAXN], r[MAXN], f[MAXN][MAXN][2];

int main()
{
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));
    f[0][0][0]=0;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++)
    {
        l[i]=max(0, a[i-1]-a[i]+1);
        r[i]=max(0, a[i+1]-a[i]+1);
    }
    for(int i=1; i<=n; i++)
    {
        f[i][0][0]=f[i-1][0][0];
        for(int j=1; j<=(i+1)/2; j++)
        {
            int val= i<=2 ? INF:f[i-2][j-1][1]+max(0, a[i-2]-a[i])+r[i];
            f[i][j][0]=min(f[i-1][j][0], f[i-1][j][1]);
            f[i][j][1]=min(f[i-1][j-1][0]+l[i]+r[i], val);
        }
    }
    for(int i=1; i<=(n+1)/2; i++) printf("%d ", min(f[n][i][0], f[n][i][1]));
}

POJ2311 Cutting Game [SG函数]

Posted on 2018-07-30 Edited on 2022-06-05 In 题解

问题描述：

给你一个$W*H$的矩形网格，两个人轮流水平或垂直地剪去一部分，如果轮到某个人只剩下1*1的网格时，则认为那个人输了。

输入：

有多组数据，每组数据两个数$W,H(2<=W,H<=200)$

输出：

每组数据一行，如果先手能赢输出”WIN”，否则”LOST”

思路：

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 205
using namespace std;

int x[MAXN][MAXN], tag[MAXN<<3];

int sg(int n, int m)
{
    if(x[n][m]!=-1) return x[n][m];
    memset(tag, 0, sizeof(tag));
    for(int i=2; i<=n/2; i++) tag[sg(i, m)^sg(n-i, m)]=1;
    for(int i=2; i<=m/2; i++) tag[sg(n, i)^sg(n, m-i)]=1;
    for(int i=0; ;i++) if(tag[i]==0) {x[n][m]=i; return i;}
}

int main()
{
    int n, m;
    memset(x, -1, sizeof(x));
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        if(sg(n, m)) printf("WIN\n");
        else printf("LOSE\n");
    }
}