OJ题目

未分类

SRM 581 YetAnotherBoardGame

一天Fin在操作一个01矩阵。
Fin可以对一个格子进行两种操作。
1. 翻转与其相邻的所有格子
2. 翻转其本身和与其相邻的所有格子
对于同一列被操作的格子，它们的操作必须是同一种。
对于同一行被操作的格子，它们的操作必须是同一种。
给定矩阵的初始状态，求Fin将其变为纯黑至少需要多少步。

SRM 583 RandomPaintingOnABoard

一天Fin在一个人在一个$n\times m(n,m\leqslant 20)$的棋盘上摆车。
一个车可以攻击同一行和同一列的棋子。
每一轮Fin会随机选一个格子，若上面此前没有车，就摆一个。
给定每个格子被随机选中的概率，问期望摆了多少轮以后棋盘上每个格子要么上面有一个车要么可以被一个车攻击到。

SRM 589 FlippingBitsDiv1

Fin在操作一个01序列$a$，他的目标是使$a[1:n-m]=a[m+1:n]$，他可以进行两种操作：
1. 翻转任意一位
2. 翻转前$k\cdot m(k\in \mathbb{N})$位
问Fin最少需要的操作次数。

SRM 590 FoxAndCity

Sanction王国有$n$座城市，可以通过$m$条双向道路（长度均为$1$）互相到达，$1$号城市是首都，每个城市都有一个对到首都最短距离的期望值$b_i(b_1=0)$。现在国王要修建道路，使得$\sum_{i=1}^n (b_i-d_i)^2$最小，其中$d_i$是修建道路后每个城市到首都的实际最短距离。

SRM 697 ConnectedStates

有一个有$n$个模块的机器，第$i$个模块上有$a_i$个接线口，模块与模块之间用线缆连接，一条线缆的两端插在两个不同模块的接线口上，一个接线口可以插无限条线缆。一个有效连接方案是用$n-1$条线缆将它们连通的方案，一个有效连接方案的稳定度是所有模块的度数（即有多少个其他模块和它用线缆直接相连）之积。给定$a$，求所有有效连接方案的稳定度之和。