「JSOI2008」球形空间产生器-高斯消元

有一个球形空间产生器能够在 $n$ 维空间中产生一个坚硬的球体。现在,你被困在了这个 $n$ 维球体中,你只知道球面上 $n+1$ 个点的坐标,你需要以最快的速度确定这个 $n$ 维球体的球心坐标,以便于摧毁这个球形空间产生器。

提示:给出两个定义:

  1. 球心:到球面上任意一点距离都相等的点。
  2. 距离:设两个n为空间上的点A, B的坐标为$(a_1, a_2, \cdots , a_n)$ , $(b_1, b_2, \cdots , b_n)$,则 AB 的距离定义为:$dist = \sqrt{ \sum_{i=1}^{n}(a_i - b_i)^2 }$

「HNOI2011」XOR和路径-高斯消元

给定一个无向连通图,其节点编号为 $1$ 到 $N$,其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得该路径上经过的边的权值的 “ $\text{XOR}$ 和” 最大。该路径可以重复经过某些节点或边,当一条边在路径中出现多次时,其权值在计算 “$\text{XOR}$ 和” 时也要被重复计算相应多的次数。

直接求解上述问题比较困难,于是你决定使用非完美算法。具体来说,从 $1$ 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 $N$ 号节点为止,便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的,并且每条这样的路径的 “ $\text{XOR}$ 和” 也不一样。现在请你求出该算法得到的路径的 “ $\text{XOR}$ 和” 的期望值。

「HNOI2013」游走-期望方程

一个无向连通图,顶点从 $1$ 编号到 $N$ ,边从 $1$ 编号到 $M$ 。 小 Z 在该图上进行随机游走,初始时小 Z 在 $1$ 号顶点,每一步小 Z 以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 Z 到达 N 号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这 $M$ 条边进行编号,使得小 Z 获得的总分的期望值最小。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×