【DEF题十连测A】[Codeforces 895D]String Mark

Description

给出等长的$AB$串,问有多少$A$串的重排列得到的串字典序大于$A$串,小于$B$串。
继续阅读 【DEF题十连测A】[Codeforces 895D]String Mark

3+

[BZOJ1177][Apio2009]Oil

Description

$Siruseri$政府决定将石油资源丰富的$Navalur$省的土地拍卖给私人承包商以建立油井。被拍卖的整块土地为一个矩形区域,被划分为$M×N$个小块。 $Siruseri$地质调查局有关于$Navalur$土地石油储量的估测数据。这些数据表示为$M×N$个非负整数,即对每一小块土地石油储量的估计值。 为了避免出现垄断,政府规定每一个承包商只能承包一个由$K×K$块相连的土地构成的正方形区域。 $AoE$石油联合公司由三个承包商组成,他们想选择三块互不相交的$K×K$的区域使得总的收益最大。 例如,假设石油储量的估计值如下:
$1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\\1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\\1\ 8\ 8\ 8\ 8\ 8\ 1\ 1\ 1\\1\ 8\ 8\ 8\ 8\ 8\ 1\ 1\ 1\\1\ 8\ 8\ 8\ 8\ 8\ 1\ 1\ 1\\1\ 1\ 1\ 1\ 8\ 8\ 8\ 1\ 1\\1\ 1\ 1\ 1\ 1\ 1\ 8\ 8\ 8\\1\ 1\ 1\ 1\ 1\ 1\ 9\ 9\ 9\\1\ 1\ 1\ 1\ 1\ 1\ 9\ 9\ 9$
如果$K = 2$, $AoE$公司可以承包的区域的石油储量总和为$100$, 如果$K = 3$, $AoE$公司可以承包的区域的石油储量总和为$208$。 $AoE$公司雇佣你来写一个程序,帮助计算出他们可以承包的区域的石油储量之和的最大值。

继续阅读 [BZOJ1177][Apio2009]Oil

0

[BZOJ4671]异或图

Description

定义两个结点数相同的图$G_1$与图$G_2 $的异或为一个新的图$G$, 其中如果$(u, v) $在$G_1$与$G_2$中的出现次数之和为$1$, 那么边$(u, v)$在$G$中, 否则这条边不在$G$中.

现在给定$s $个结点数相同的图$G_{1 \sim s}$, 设$S = \{G_1, G_2, \cdots , G_s\}$, 请问$S$有多少个子集的异或为一个连通图?

第一行为一个整数$s$, 表图的个数.

接下来每一个二进制串, 第$i$行的二进制串为$g_i$,其中$g_i$是原图通过以下伪代码转化得到的. 图的结点从$1$开始编号, 下面设结点数为$1$.


继续阅读 [BZOJ4671]异或图

0

[ECUSTOJ#4]果实计数

Description

淘淘家有棵奇怪的苹果树,这棵树共有$n+1$层,标号为$0 \sim n$。这棵树第$0$层只有一个节点,为根节点。已知这棵树为$b$叉树,且保证是一颗满$b$叉树。
现在,该树第$n$层的每个节点上都结出了一个苹果,淘淘想知道共结了多少苹果。由于数量可能很大,答案要求输出$\bmod\ k$后的结果。
继续阅读 [ECUSTOJ#4]果实计数

0

[ECUSTOJ#45]不等数列

Description

将$1$到$n$任意排列,然后在排列的每两个数之间根据他们的大小关系插入$>$和$<$。

问在所有排列中,有多少个排列恰好有$k$个$<$。答案对$2012$取模。 例如:排列$1~4~3~2~5$,插入$>$和$<$后变成:$1 < 4 > 3 > 2 < 5$

多组数据,$1 \leq n \leq 1000,0 \leq k < n$
继续阅读 [ECUSTOJ#45]不等数列

0

[ECUSTOJ#68]黑暗城堡

Description

你知道黑暗城堡有$ N $个房间,$M $条可以制造的双向通道,以及每条通道的长度。
城堡是树形的并且满足下面的条件:
设$ D_i $为如果所有的通道都被修建,第$ i $号房间与第$ 1 $号房间的最短路径长度;
而$ S_i​​$为实际修建的树形城堡中第$ i $号房间与第$ 1 $号房间的路径长度;
要求对于所有整数$ i (1 \leq i \leq N)$,有$ S_i=D_i​$​成立。

你想知道有多少种不同的城堡修建方案。当然,你只需要输出答案对$ 2^{31} $取模之后的结果就行了。
$1 \leq N \leq 1000,1 \leq M \leq \frac{N(N-1)}{2},1 \leq l \leq 200$

其实题目就是在求一个无向图中最短路径树的棵数。
继续阅读 [ECUSTOJ#68]黑暗城堡

0