[ECUSTOJ#4]果实计数

Description

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

Solution

快速幂裸题不解释

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$

Solution

$f[i][j]$表示前$i$个数填$j$个小于号的方案数,直接转移即可。
暂时不确定解是否具有closed form




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$

其实题目就是在求一个无向图中最短路径树的棵数。

Solution

最短路径树的定义:
选出$N-1$条边组成一棵树,对于给定的源点$S$,
若任何点$u$均满足在原图上$S$到点$u$的最短路$\mathrm{dis}(u)$等于在这棵树上$S$到$u$的最短路$\mathrm{disnew}(u)$,
则这棵树是一棵最短路径树。

对于这道题,每个点的$d_i$可以通过dijkstra求出来,现在考虑如何计数
我们枚举每条边,对于一条边$(i,j)$,如果$d_i+w_{i,j}=d_j$,那这条边就可以被选,就$++cnt_j$,代表可以到达$j$的路径可以增加一条
那么最后根据乘法原理把所有的$\mathrm{cnt}$乘起来就行了
时间复杂度$O(m \log n)$

0

[Codeforces 364D]GHD

Description

有一个数列,求最大的数,使得该数是数列中一半以上的数的因数。$n \leq 10^6, a_i \leq 10^{12}$

Solution

我们知道这个数字一定是这个数列中某个数的因数,因此我们需要选择一个数求它与其他数的最大公因数。这些公因数中的一个就是答案。求一遍公因数是
$O(n \logn)$的。
对于求出来的公因数,我们去从大到小找一个会成为超过一半数的因数的数字。具体做法是,选择一个因数,去找比它大的因数,如果它能整除大因数,说明大因数对应的数字也可以被这个数整除,应当把加到这个数的计数上。这个过程直观看上去是$O(n^2)$的,但是实际上我们不会对比当前最优解还小的因数计算,并且当计数超过$n$的一半的时候就可以停止计数并计入答案,在这样的处理下我们可以让这个计数的时间变得可接受。
答案肯定是这些数字中超过一半数的因数,因此每一次随机找到正确解的概率超过$\frac{1}{2}$。我们考虑重复找解的过程多次,这样错误的概率就是$\frac{1}{2} ^ \beta$的。

0

[ECUSTOJ#21]幂之和

Description

对于正整数$k$,可以定义$k$次方和
$$S _ { k } ( n ) = \sum _ { i = 1 } ^ { n } i ^ { k }$$
可以把它写成下面的形式,当$M$取最大可能的正整数时,所有的系数$a_i$都是确定的:
$$S _ { k } ( n ) = \frac { 1 } { M } \left( a _ { k + 1 } n ^ { k + 1 } + a _ { k } n ^ { k } + \ldots + a _ { 1 } n + a _ { 0 } \right)$$

现在给定整数$k$,输出$M , a _ { k + 1 } , a _ { k } , \dots , a _ { 1 } , a _ { 0 }$。$k \leq 20$

Solution

当然是Mathematica打表

表有点长,这里就不打了
这题的正解应该是拉格朗日插值
弄$k+1$个值出来然后带进去就ok
代码懒得敲了。。

0

[BZOJ2282][SDOI2011]消防

Description

某个国家有$n$个城市,这$n$个城市中任意两个都连通且有唯一一条路径,每条连通两个城市的道路的长度为$z_i(z_i \leq 1000)$。

这个国家的人对火焰有超越宇宙的热情,所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍(大量的消防经费开销)可是却又无可奈何(总统竞选的国民支持率),所以只能想尽方法提高消防能力。

现在这个国家的经费足以在一条边长度和不超过$s$的路径(两端都是城市)上建立消防枢纽,为了尽量提高枢纽的利用率,要求其他所有城市到这条路径的距离的最大值最小。

你受命监管这个项目,你当然需要知道应该把枢纽建立在什么位置上。

对于$20\%$的数据,$n \leq 300$。

对于$50\%$的数据,$n \leq 3000$。

对于$100\%$的数据,$n \leq 300000$,边长小等于$1000$。

Solution

显然肯定是在直径上选一段,直径两次$dfs$可得

答案一定不会小于所有点到直径的距离最大值,只要把直径上的边权设为$0$,任选直径上一点$dfs$可得

将最大值作为二分下界,二分直径左右端点的舍弃部分




0

明明的随机数

此题很好地考察了选手对 std::sortstd::unique 的使用

0