Codeforces Round #108 (Div. 2)

2024-10-10 22:14:42

Codeforces Round #108 (Div. 2)

C. Pocket Book

题意

给定\(N(N \le 100)\)个字符串，每个字符串长为\(M(M \le 100)\)。
每次选择\(i, j, k\)，然后交换串\(i\)和串\(j\)的长度为\(k\)的前缀。
操作可以做任意次，求最多能得到多少不同的字符串，\(modulo (10^9+7)\)。

思路

相当于每个位置的可选字符为该列的不同字符的数量。

代码

C. Pocket Book

D. Frames

题意

给定一个\(n \times m(3 \le n,m \le 1000)\)的矩阵，由'.'和'#'构成。
两个矩形框放入该矩阵，'#'表示格子被矩形框覆盖，且边长均不小于3。
两个矩形框的关系是任意的，重边、重叠，甚至完全重叠也是可以的。
判断原矩阵是否能由两个矩形框表示，若可以输出"YES"以及两个矩形框的左上角坐标和右下角坐标，否则输出"NO"。

思路

找出横向长度大于2的行号，显然只有最小值，次小值，最大值，次大值有可能成为矩形框的横坐标。
暴力枚举判定即可。

代码

D. Frames

E. Garden

题意

一个\(n \times m(1 \le n,m \le 100,n \cdot m \le 200)\)的网格，有\(k(k \le 7)\)的格子必须要覆盖，且任意两个格子之间要存在一条路径（相邻格子有一条公共边）。
覆盖格子\((i,j)\)的代价为\(a(i,j)\)。
求最小代价，并输出一种方案,'X'表示覆盖，'.'表示未覆盖。

思路

用\(f[u][mask]\)表示格子覆盖状态\(mask\)且集中到\(u\)的最小代价。
转移：\[f[u][mask]=min{f[u][submask] + f[u][mask \oplus submask] - v[u]}\]
\(v[u]\)表示点\(u\)的覆盖代价，即\(a[i = u / m][j = u \% m]\)
当状态\(mask\)集中到\(u\)之后，可以走到或者说扩展到其他点\(v\)，这个bfs一下即可。

代码

E. Garden

最新文章

热门文章