A管道维修
和刚才普及组的一道题一样，这个题要考虑曼哈顿距离。一个格子如果需要清理至少一次，说明它是堵塞格子。如果需要清理两次，说明它和四周的格子都是堵塞的。依此类推，如果需要清理k次，说明它和周围的一个菱形区域 （曼哈顿距离小于等于k的区域）都是堵塞的。这样我们就可以计算出一个格 子需要清理至少k次的几率了。可以用n^3的时间预处理所有这些概率（类似 部分和）。
算出这个几率以后，我们可以进一步算一个格子需要被清理恰好k次的几率，这个几率是之前的至少k次的几率乘以距离为k+1的那些格子至少有一个是干净的的几率。至少一个干净就相当于1减掉全部堵塞。同样可以n^3的时间预处理。
如果我们只能算出一个格子需要清理至少k次的几率，不会算恰好k次的概率，也可以做。一个格子需要清理的次数的期望等于需要清理至少1次的概率加需要清理至少2次的概率加需要清理至少3次的概率加…。这样代码更简单。
算出这个几率以后，我们可以进一步算一个格子需要被清理恰好k次的几率，这个几率是之前的至少k次的几率乘以距离为k+1的那些格子至少有一个是干净的的几率。至少一个干净就相当于1减掉全部堵塞。同样可以n^3的时间预处理。
如果我们只能算出一个格子需要清理至少k次的几率，不会算恰好k次的概率，也可以做。一个格子需要清理的次数的期望等于需要清理至少1次的概率加需要清理至少2次的概率加需要清理至少3次的概率加…。这样代码更简单。
B公平竞赛
本题给定了一个有向图，要求找出一个环，其中可以有重点但是不能有重边， 且环上的边方向是交错的。
我们可以把每个点拆成两个点a赢和a输，分别表示这个点在环上是作为赢两次的点出现或者输两次的点出现。那么一场比赛a赢了b，就相当于从a赢连到b输的一条边，或者从b输连到a赢的一条边。原来的一个环可以对应到拆 点以后的一个环。
现在我们得到了一个二分图，而且是无向的。无向图找最小环可以用bfs解决。 暴力可以得100分，即从每个点开始找到最小环就break（可以证明如果一个 无向图的平均度数至少是8，那么它一定包含一个环。所以bfs时只要搜索最多5000*8条边，一定会找到环并break。）。
我们可以把每个点拆成两个点a赢和a输，分别表示这个点在环上是作为赢两次的点出现或者输两次的点出现。那么一场比赛a赢了b，就相当于从a赢连到b输的一条边，或者从b输连到a赢的一条边。原来的一个环可以对应到拆 点以后的一个环。
现在我们得到了一个二分图，而且是无向的。无向图找最小环可以用bfs解决。 暴力可以得100分，即从每个点开始找到最小环就break（可以证明如果一个 无向图的平均度数至少是8，那么它一定包含一个环。所以bfs时只要搜索最多5000*8条边，一定会找到环并break。）。
C急开锁
本题题意是有一堆石子，先手可取任意数量的石子但是无法直接全部取走， 此后每个人可取前一个人取走的k倍以内任意数量的石子（不能不取），取走最后一个石子的赢，问先手是否必胜。
我们首先打表找规律，可以发现k等于2时，先手输当且仅当l为斐波那契数。 可得30分。继续观察可以发现无论k是多少，先手如果在l=n时会输，那么我 们找一个
的最小的使得先手输的m，先手在l=n+m的时候也只能输掉。（在n和n+m之间都是获胜的）
找到规律后很好实现，O(klog(l)log(klog(l)))（每次二分查找m）就可以通过。
归纳证明： 如果l在n和n+m之间，先手将石子数变为n即可。这时后手面对l=n的情况， 且限制更强了（本来能随便拿，现在只能拿先手拿的k倍以内），只能输掉。 如果l是n+m，先手不能直接拿走m个，因为m太大了，后手下一步直接获胜。现在后手可以先按照玩m个石子的游戏的策略，保证自己拿走m个石子中的最后一个。先手就会被留下n个石子，只能输掉。
我们首先打表找规律，可以发现k等于2时，先手输当且仅当l为斐波那契数。 可得30分。继续观察可以发现无论k是多少，先手如果在l=n时会输，那么我 们找一个
找到规律后很好实现，O(klog(l)log(klog(l)))（每次二分查找m）就可以通过。
归纳证明： 如果l在n和n+m之间，先手将石子数变为n即可。这时后手面对l=n的情况， 且限制更强了（本来能随便拿，现在只能拿先手拿的k倍以内），只能输掉。 如果l是n+m，先手不能直接拿走m个，因为m太大了，后手下一步直接获胜。现在后手可以先按照玩m个石子的游戏的策略，保证自己拿走m个石子中的最后一个。先手就会被留下n个石子，只能输掉。
std
全部评论
(0) 回帖