程序算法题解大全：洛谷与CF经典题目详解

需积分: 5 98 浏览量更新于2024-06-20 收藏 1.11MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

CF398B题解

题目描述

有一个的网格，其中格子涂上了色。每次随机选择一个格子n × n n \times n n × n m m m

有可能是涂过色的格子涂色，求让网格每一行每一列都至少有一个格子涂了色的操作( ( ( ) ) )

次数期望。

算法分析

考虑进行DP，设表示剩行，列没有涂色，将f [ i ] [ j ] f[i][j] f[i][j] i i i j j j

网格全部涂上色的期望次数。

先来看预处理的部分，也就是当或者的情况。这两种情况本i = 0 i=0 i = 0 j = 0 j=0 j = 0

质上是一样的，下面讲解如何求出的情况。i = 0 i=0 i = 0

i = 0 i=0 i = 0 的时候，我们就可以剩掉这一维，因为一直是。下面讲解两种方i i i 0 0 0

法。

设表示已经涂了个格子，将格子全涂满的期望步数。显然 d p [ i ] dp[i] dp[i] i i i d

，我们要求的答案是，所以是逆推。p [ n ] = 0 dp[n] = 0 dp[n] = 0 d p [ 0 ] dp[0] dp[0]

有的概率涂到已经涂过色的格子，此时仍然需要涂 i n \frac{i}{n} ni d p [ i ] dp[i] dp[

次；有的概率涂到还没有被涂色的格子，此时需要涂 i] n i n \frac{n-i}{n} nni d p [ i

次。所以转移式为 + 1 ] dp[i+1] dp[i + 1] d p [ i ] = i n × d p [ i ] + n i n × d p

[ i + 1 ] + 1 dp[i] = \frac{i}{n} \times dp[i] + \frac{n-i}{n} \times dp[i+1] + 1 dp

，这里的表示这一次涂色的代价。把式子化简[i] = ni × dp[i] + nni × dp[i + 1] + 1 + 1 +1 +1

一下，就变成了 d p [ i ] = d p [ i + 1 ] + n n i dp[i] = dp[i+1] + \frac{n}{n-i} dp

。最后整理一下会发现变成了 [i] = dp[i + 1] + nin d p [ 0 ] = ∑ i = 1 n n i dp[0] = \sum_

。{i=1}^n \frac{n}{i} dp[0] = i=1n in

考虑当已经涂了个格子，从剩下的格子中随机选一个涂，概率是 i 1 i-1 i 1 n i + 1 n

，期望为 \frac{n-i+1}{n} nni+1 1 p = n n i + 1 \frac{1}{p} = \frac{n}{n-i+1} p1 = ni+

。所以总期望为 1n ∑ i = 1 n n n i + 1 = ∑ i = 1 n n i \sum_{i=1}^n \frac{n}{n-

。i+1} = \sum_{i=1}^n \frac{n}{i} i=1n ni+1n = i=1n in

所以我们要的就为 f [ i ] [ 0 ] f[i][0] f[i][0] f [ i 1 ] [ 0 ] + n i f[i-1][0] +

，为 \frac{n}{i} f[i 1][0] + in f [ 0 ] [ i ] f[0][i] f[0][i] f [ 0 ] [ i 1 ] + n i f

。[0][i-1] + \frac{n}{i} f[0][i 1] + in

然后来看DP的部分。我们看可以从哪几种情况转移。f [ i ] [ j ] f[i][j] f[i][j]

剩下行，列，表示这一次涂色涂的格子正好使新的行和 i 1 i-1 i 1 j 1 j-1 j 1 1 1 1

列被涂。一共有个格子，满足该条件的格子有 1 1 1 n × n n \times n n × n i × j i

个可以想象一下，此时抽象为一个的网格，\times j i × j ( ( ( i × j i \times j i × j

∑

∑ ∑

CF398B题解

第 6 页 /共

42 页

这个网格里面的每一个位置都满足可以使行和列被涂，此时的期望为 1 1 1 1 1 1 ) ) ) f

[ i 1 ] [ j 1 ] × i × j n 2 f[i-1][j-1] \times \frac{i \times j}{n^2} f[i 1][j 1

。] × n2i×j

剩下行，列，表示这一次涂色涂的格子可以使新的行被涂，而且i 1 i-1 i 1 j j j 1 1 1

该位置对应的列已经被涂过色了，有行，列的网格中的每一个位置满足i i i n j n-j n j

条件，此时的期望为 f [ i 1 ] [ j ] × i × ( n j ) n 2 f[i-1][j] \times \frac{i

。\times (n-j)}{n^2} f[i 1][j] × n2i×(nj)

剩下行，列，表示这一次涂色涂的格子可以使新的列被涂，而且i i i j 1 j-1 j 1 1 1 1

该位置对应的行已经被涂过色了，有行，列的网格中的每一个位置满足n i n-i n i j j j

条件，此时的期望为 f [ i ] [ j 1 ] × ( n i ) × j n 2 f[i][j-1] \times \frac{(n-

。i) \times j}{n^2} f[i][j 1] × n2(ni)×j

剩下行，列，表示这一次涂色不能使新的行或者新的列图上色。i i i j j j 1 1 1 1 1 1

有行，列的网格中的每一个位置满足条件，此时的期望为 n i n-i n i n j n-j n j f [ i

] [ j ] × ( n i ) × ( n j ) n 2 f[i][j] \times \frac{(n-i) \times (n-j)}{n^2} f[

。i][j] × n2(ni)×(nj)

所以总的转移式为 f [ i ] [ j ] = f [ i 1 ] [ j 1 ] × i × j n 2 + f [ i 1 ] [ j

] × i × ( n j ) n 2 + f [ i ] [ j 1 ] × ( n i ) × j n 2 + f [ i ] [ j ] × (

n i ) × ( n j ) n 2 + 1 f[i][j] = f[i-1][j-1] \times \frac{i \times j}{n^2} + f[i-

1][j] \times \frac{i \times (n-j)}{n^2} + f[i][j-1] \times \frac{(n-i) \times j}

{n^2} + f[i][j] \times \frac{(n-i) \times (n-j)}{n^2} + 1 f[i][j] = f[i 1][j 1] × n2i

× j + f[i 1][j] × n2i × (n j) + f[i][j 1] × n2(n i) × j + f[i][j] × n2(n i) × (n j) + 1

这里的和上面的相同，也是表示这一次涂色的代价。由于等式右面也有 + 1 +1 +1 f [ i ] [

，我们移项，进行花间。最后的转移式为 j ] f[i][j] f[i][j] f [ i ] [ j ] = n 2 + i ×

j × f [ i 1 ] [ j 1 ] + i × ( n j ) × f [ i 1 ] [ j ] + ( n i ) × j × f [

i ] [ j 1 ] n 2 ( n i ) × ( n j ) f[i][j] = \frac{n^2 + i \times j \times f[i-1]

[j-1] + i \times (n-j) \times f[i-1][j] + (n-i) \times j \times f[i][j-1]}{n^2 - (n-

i) \times (n-j)} f[i][j] = n2 (n i) × (n j)n2 + i × j × f[i 1][j 1] + i × (n j) × f[i 1]

[j] + (n i) × j × f[i][j 1]

到这里，这道题也就结束了，真是一道期望的好题！

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

#define re register

#define rep a b c re b a c a( , , ) for( int a( ) ; <= ; ++ )

#define drep a b c re b a c a( , , ) for( int a( ) ; >= ; -- )

stdusing namespace ;

inline int read(){

x f chint =0, =1;char =getchar();

ch ch ch f chwhile( <'0'|| >'9'){if( == '-') =-1 ; =getchar();}

ch ch x x x ch chwhile( >='0'&& <='9'){ =( <<1)+( <<3)+( ^48) ; =getchar();}

x freturn * ;

CF398B题解

第 7 页 /共

42 页

剩余43页未读，继续阅读

kbv516

粉丝: 0
资源: 35

会员权益专享

程序算法题解大全：洛谷与CF经典题目详解

解答、算法题.pdf

程序员实用算法.pdf

算法面试题实用知识库分享

noip历年真题题解.pdf

结构力学学习指导及题解大全.pdf

算法艺术与信息学竞赛题解pdf

汤小丹《计算机操作系统(第4版)》学习指导与题解 含实验.pdf

leetcode算法题的pdf版题解

中山大学acm模板.pdf

信息学奥赛一本通题解目录 alex

算法竞赛宝典三部曲pdf

国际大学生程序设计竞赛例题解 合集pdf

Java刷题网站推荐

冯象初数值分析题解pdf资源

数字图像处理学习指导与题解 pdf

数学分析题解精粹第三版pdf

算法导论 第三版pdf

高畅leecode11 pdf

高等代数精选题解杨子胥pdf

细胞生物学复习纲要与题解pdf版

会员权益专享

最新资源

汤小丹《计算机操作系统(第4版)》学习指导与题解含实验.pdf

国际大学生程序设计竞赛例题解合集pdf

算法导论第三版pdf