专栏文章

题解：CF398B Painting The Wall

CCryn_Frog195
CF398B题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipgn1g2
此快照首次捕获于
2025/12/03 11:41
3 个月前
此快照最后确认于
2025/12/03 11:41
3 个月前
查看原文
都九年级了，还没法搞定马尔科夫链就有问题了，这就是中学生现状。

题意

在 n×n(1≤n≤2000)n \times n(1 \le n \le 2000) 的网格图上，进行所有格子等概率打标记，问期望几次后每行每列都有标记格。

多一手

由于每个格子都是等概率的，我们不妨在里面掺一步：每次标记后将标记格子通过行交换和列交换移到左下角，这样不仅不会改变分析的正确性，还能将有标记格的行和列都移到一边，便于分析。

马尔科夫链和动态规划

由于题目是一道求期望的题，考虑使用马尔科夫链作为接下来的分析方式。
作为初中高等数学，马尔科夫链并不困难，其原理是：
  1. 设状态，及一种状态到一类结束状态的期望或概率；
  2. 根据下一步的状态情况得出求此状态的方程式；
  3. 若通过转方程得到的转移关系图为有向无环图则用动规，否则上高斯消元。
接下来，我们走一遍流程。
设 dpi,jdp_{i,j} 表示已经有 ii 行 jj 列存在标记格，问标记到每行每列都被标记的期望次数。
接下来分析下一个标记的可能情况：
  1. 标记落入红区，对应行对应列都已有标记格，(i,j)→(i,j)(i,j) \to (i,j)，概率为 ijn2\frac{ij}{n ^ 2}。
  2. 标记落入黄区，对应行已被标记，对应列在这次标记后有标记格，(i,j)→(i,j+1)(i,j) \to (i,j + 1)，概率为 i(n−j)n2\frac{i(n - j)}{n ^ 2}。
  3. 标记落入蓝区，对应列已被标记，对应行在这次标记后有标记格，(i,j)→(i+1,j)(i,j) \to (i + 1,j)，概率为 (n−i)jn2\frac{(n - i)j}{n ^ 2}。
  4. 标记落入绿区，对应列、对应行在这次标记后有标记格，(i,j)→(i+1,j+1)(i,j) \to (i + 1,j + 1)，概率为 (n−i)(n−j)n2\frac{(n - i)(n - j)}{n ^ 2}。
得到转移方程：
dpi,j={0i=n∧j=n1+ijn2dpi,j+j(n−i)n2dpi+1,j+i(n−j)n2dpi,j+1+(n−i)(n−j)n2dpi+1,j+1i≠j∨j≠ndp_{i,j} = \begin{cases} 0 & i = n\land j = n \\ 1 + \frac{ij}{n ^ 2}dp_{i,j} + \frac{j(n - i)}{n ^ 2}dp_{i + 1,j} + \frac{i(n - j)}{n ^ 2}dp_{i,j + 1} + \frac{(n - i)(n - j)}{n ^ 2}dp_{i + 1,j + 1} & i \neq j \lor j \neq n \\ \end{cases}
对 (i,j)≠(n,n)(i,j) \neq (n,n) 的情况，有：
dpi,j=1+ijn2dpi,j+j(n−i)n2dpi+1,j+i(n−j)n2dpi,j+1+(n−i)(n−j)n2dpi+1,j+1dp_{i,j} = 1 + \frac{ij}{n ^ 2}dp_{i,j} + \frac{j(n - i)}{n ^ 2}dp_{i + 1,j} + \frac{i(n - j)}{n ^ 2}dp_{i,j + 1} + \frac{(n - i)(n - j)}{n ^ 2}dp_{i + 1,j + 1}
即
(1−ijn2)dpi,j=1+j(n−i)n2dpi+1,j+i(n−j)n2dpi,j+1+(n−i)(n−j)n2dpi+1,j+1(1 - \frac{ij}{n ^ 2})dp_{i,j} = 1 + \frac{j(n - i)}{n ^ 2}dp_{i + 1,j} + \frac{i(n - j)}{n ^ 2}dp_{i,j + 1} + \frac{(n - i)(n - j)}{n ^ 2}dp_{i + 1,j + 1}
成功处理掉自环，接下来由于转移关系为有向无环图，可以用 O⁡(n2)\operatorname{O}(n ^ 2) 动态规划解决。
最后对于部分格子已涂的情况，根据这些格子影响的行列数定位状态即可。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,cntx,cnty;
bool vis1[2009],vis2[2009];
double dp[2009][2009];
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= m; i ++){
		scanf("%d %d",&x,&y);
		if(!vis1[x])
			vis1[x] = true,cntx++;
		if(!vis2[y])
			vis2[y] = true,cnty++;
	}
	dp[n][n] = 0;
	for(int i = n; i >= cntx; i --){
		for(int j = n; j >= cnty; j --){
			if(i == n && j == n)
				continue;
			dp[i][j] = 1;
			if(i < n)
				dp[i][j] += dp[i + 1][j] * (n - i) * j / (n * n);
			if(j < n)
				dp[i][j] += dp[i][j + 1] * (n - j) * i / (n * n);
			if(i < n && j < n)
				dp[i][j] += dp[i + 1][j + 1] * (n - i) * (n - j) / (n * n);
			dp[i][j] = dp[i][j] * (n * n) / (n * n - i * j); 
		}
	}
	printf("%.7lf\n",dp[cntx][cnty]);
}
2025/7/23:修正转移方程。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...