Early's Blog

题目链接

题意

对于任意一个 $n$ 行 $m$ 列、由 S 与 E 组成的矩阵，由上至下、由左至右地对于每个格子进行以下操作：

• 如果该格子已被覆盖，直接跳过。
• 尝试覆盖这个格子与另一个：若该格子为 S 则覆盖下面的格子，为 E 则覆盖右边的格子。如果要覆盖的格子已被覆盖或不在矩阵内，则跳过。
• 尝试向另一个方向覆盖。如果也不行则不覆盖。

对于所有可能的 $2^{nm}$ 个矩阵，求出矩阵被覆盖的次数总和。

对于 $60\%$ 的数据，$m\leq16$。
对于 $100\%$ 的数据，$n\leq12,m\leq30$。

题目链接

写在前面

又快到省选季了呢。

Early 认为他需要练习一些 DP 题。

题意

给定长度为 $n$ 的数组 $l,r$，表示 $a_i$ 在 $[l_i,r_i]$ 中随机生成。

求 $a$ 单调不增的概率。

题目链接

题意

求长度为 $n$、满足以下条件的整数序列 $A$ 的个数：

• $\forall i\in[1,n),A_i\leq A_{i+1}$；
• $\forall k\in[1,n)$，任意 $k$ 个 $A$ 中的数之和都严格小于任意 $k+1$ 个 $A$ 中的数之和。

题目链接

题意

给出网格图，每格有一个团子。可以按「粉 - 白 - 绿」在八个方向串成一串团子。每个团子只能被串至多一次。最大化串出的团子串数。

题意

求把一个凸多边形划分为 $n$ 个边数为 $k$ 的凸多边形的方案数。

希望，永远都在。

题目链接

题意

给定一个仙人掌图，问有多少种方法移动一条边使新图还是仙人掌图。

题目链接

题意

$n$ 个均匀的物体，进行 $k(k\leq2)$ 次切割后再把 $n+k$ 个物品分为两组，最小化：

$\epsilon=\frac{\mid\sum_{i\in S}V_i-\sum_{i\in T}V_i\mid}{\sum_{i=1}^{n+k}V_i}+\frac{\mid\sum_{i\in S}m_i-\sum_{i\in T}m_i\mid}{\sum_{i=1}^{n+k}m_i}$

题目链接

题意

给定一个 $n$ 个点、$m$ 条有向边的图，点有点权，边有通过这条边所用的时间，不能在点上停留。每次到达一个点都会获得相当于点权的贡献。另外有 $k$ 个事件，每个均描述了第 $t$ 天编号为 $x$ 的点权值会增加 $v$。最大化从 $1$ 号点出发、在 $T$ 天后回到 $1$ 的总贡献。

在自己出的一道题里，写下了这么两句话：

「橙色的段服，真的很好看呢。」
「可惜，在时代的三年再也回不去了呢。」