阶乘
题目大意：给出
n
n
n、
b
a
s
e
base
base，求
n
!
n!
n!在
b
a
s
e
base
base进制下末尾连续0的个数。
soluiton：考虑到答案其实就是最大的
k
k
k，使得
n
!
?
m
o
d
?
b
a
s
e
k
=
0
n!\bmod base^k=0
n!modbasek=0。
将
b
a
s
e
base
base分解质因数为：
p
1
l
1
+
p
2
l
2
+
?
+
p
n
l
n
p_1^{l_1}+p_2^{l_2}+\cdots+p_n^{l_n}
p1l1??+p2l2??+?+pnln??。
我们设
M
a
x
n
=
p
1
a
1
+
p
2
a
2
+
?
+
p
n
a
n
Maxn=p_1^{a_1}+p_2^{a_2}+\cdots+p_n^{a_n}
Maxn=p1a1??+p2a2??+?+pnan??，且
M
a
x
n
Maxn
Maxn为
n
n
n的因数，那么答案即为
m
i
n
{
?
a
i
/
l
i
?
∣
i
∈
[
1
,
n
]
}
min\{\lfloor a_i/l_i\rfloor|i\in[1,n]\}
min{?ai?/li??∣i∈[1,n]}
a
a
a数组如何求解？
a
i
=
∑
n
>
0
?
n
/
p
i
?
a_i=\sum_{n>0}\lfloor n/p_i\rfloor
ai?=n>0∑??n/pi??
答案即为上述。
时间复杂度：
O
(
T
b
a
s
e
log
?
n
)
O(T\sqrt{base}\log n)
O(Tbase
?logn)。
石油储备
题目大意：给定一棵树，每个结点都有对应的
s
i
s_i
si?，问如何分配
s
s
s使得其方差最小的最小代价。
solution：最小费用最大流
考虑非平衡度最小时的情况：
若
s
u
m
?
m
o
d
?
n
=
0
sum\bmod n=0
summodn=0，则答案为
?
s
u
m
n
?
\lfloor\dfrac{sum}n\rfloor
?nsum??；
若
s
u
m
?
m
o
d
?
n
≠
0
sum\bmod n\neq0
summodn?=0，则答案为
?
s
u
m
n
?
\lfloor\dfrac{sum}n\rfloor
?nsum??或
?
s
u
m
n
?
+
1
\lfloor\dfrac{sum}n\rfloor+1
?nsum??+1。
建图：
1、源点往所有点连一条流量为油桶数量，费用为0的边；
2、所有点往回电连一条流量为
?
s
u
m
n
?
\lfloor\dfrac{sum}n\rfloor
?nsum??，费用为0的边；
3、对于读入的点，连一条流量为
+
∞
+\infin
+∞，费用为读入的边；
然后跑一遍最小费用最大流。
随后把所有连向汇点的边流量加一（使得剩余流量跑完），再做一遍费用流。
两次答案之和即为答案。
小纪的作业题
题目大意：给定序列
a
a
a，对于每次询问
q
u
e
r
y
(
l
,
r
)
query(l,r)
query(l,r)，在子串
a
i
∣
i
∈
[
l
,
r
]
a_i|i\in[l,r]
ai?∣i∈[l,r]中求出：对于每个不同的
x
x
x，如果它在子串中出现了
f
(
x
)
f(x)
f(x)次，结果为
∑
x
f
(
x
)
\sum x^{f(x)}
∑xf(x)。
solution：莫队。
先将读入的数分块，暴力求出第一个区间的答案。
暴力在每个块内转移即可。
时间复杂度：
O
(
n
n
)
O(n\sqrt n)
O(nn
?)。
拯救莫莉斯
题目大意：给定一个
n
×
m
n\times m
n×m的矩阵，每个点可以放
0
/
1
0/1
0/1。要满足对于点
(
x
,
y
)
(x,y)
(x,y)，
e
x
,
y
,
e
x
?
1
,
y
,
e
x
+
1
,
y
,
e
x
,
y
?
1
,
e
x
,
y
+
1
e_{x,y},e_{x-1,y},e_{x+1,y},e_{x,y-1},e_{x,y+1}
ex,y?,ex?1,y?,ex+1,y?,ex,y?1?,ex,y+1?，中一个为1。
solution：状压
d
p
dp
dp。
设
f
i
,
j
,
k
f_{i,j,k}
fi,j,k?表示对于前
i
i
i行，第
i
?
1
i-1
i?1行状态为
j
j
j，第
i
i
i行状态为
k
k
k，并且对于任意一行
x
∣
x
<
i
x|x<i
x∣x<i，该行城市满足题目要求的最小代价。
辅助数组
g
i
,
j
,
k
g_{i,j,k}
gi,j,k?表示油库数量。
f
i
+
1
,
s
,
X
=
m
i
n
{
f
i
,
j
,
k
+
c
o
s
t
i
+
1
,
X
}
f_{i+1,s,X}=min\{f_{i,j,k}+cost_{i+1,X}\}
fi+1,s,X?=min{fi,j,k?+costi+1,X?}。
答案：
m
a
x
{
f
n
+
1
,
x
,
0
}
max\{f_{n+1,x,0}\}
max{fn+1,x,0?}。
时间复杂度：
O
(
2
3
m
n
)
O(2^{3m}n)
O(23mn)。
|