zcmimi's blog

categories/刷题记录/共666篇文章

avatar
zcmimi
2020-06-09 16:22:00

DZY Loves Math

题意:

对于正整数n,定义f(n)n所含质因子的最大幂指数

例如f(1960)=f(2^3\cdot 5^1\cdot 7^2)=3,f(10007)=1,f(1)=0

给定正整数a,b,求$\sum\limits_{i=1}^a\s

avatar
zcmimi
2020-05-25 19:22:00

SPOJ的GSS系列是关于区间统计技巧的集合

非常适合锻炼码力

LG GSS1 | SPOJ GSS1

[LG GSS2](

avatar
zcmimi
2019-03-06 00:03:14

题目地址:

网络流24题真的好有质量~\ (\ge \le ) /~!

进度: $\frac

avatar
zc
2020-12-02 17:48:25

查看原题

点击跳转

设有a1,b2

f_i为剩下i1的方案数

f_i=f_{i-1}+(i-1)\times f_{i-2}

接着考虑剩下2的情况

我们把2次交换的限制看成一次主动交换和一次被动交换

那我们就可以让b2都先使用一次主动交换

那么第一个2可以从n个中选一个

第二个2可以从n-1中选一个

第三个2可以从n-2中选一个

...以此类推

这样b次交换后会剩下正好a1

ans=f_a\times \prod_{i=1}^b (n-i+1)

avatar
zc
2020-12-01 15:32:24

查看原题

点击跳转

avatar
zc
2020-12-01 10:42:49

查看原题

点击跳转

f_i=f_j+\max(a_{j+1},a_{j+2},\dots,a_i), s_i-s_j\le m

对于转移方程可行的ja_{j+1}\le \max(a_{j+2},\dots,a_i),f_j+\max(a_{j+1},\dots,a_i)f_{j+1}+\max(a_{j+2},\dots,a_i)后半段相同,f_j\le f_{j+1},所以前者更优

推广可得最优转移一定在a_{q_1}>a_{q_2}>a_{q_3}>a_{q_4}>\dots>a_{q_j}

f_{a_{q_j}}+a_{q_{j+1}}取得(对于a_{q_1},有f_{st}+a_{q_1},st是最大的使a_{st}+\dots+a_i>m

维护一个可查询最大值的单调队列

维护一个中点,向两端维护单调栈,如果左右端点超过中点就重构单调栈

avatar
zc
2020-11-27 19:40:50

查看原题

点击跳转

首先可以全走一遍回到起点,然后贪心地消掉还能走的边,这样就得到了回到原点的最大步数。

接下来考虑再走到每个点。

dfs一遍,如果父节点还有剩余流量就直接走过来,否则需要退掉向父节点走的边,然后再检查一下多出来的流量能否和儿子走来回。注意需要回溯。

avatar
zc
2020-11-25 11:32:22

查看原题

点击跳转

转自: https://www.cnblogs.com/RiverHamster/p/sol-lg6672.html

简化题意

w_i 全部减 1,则问题变成一个序列,其中给定有 n 个正数 w_i,其余都是 −1,和是 0,前缀和均非负,求排列方案数。

做法

如果和是 1,且要求前缀和全为正数,有结论:每个排列的所有循环移位只有 1 种合法,所以计数圆排列数即可,《具体数学》7.5 章有详细证明,其实就是每次必须要取最后一个最小值位置作为起点,使得其他最小值位置跨过序列结尾,前缀和为 1,否则如果有两个相等最小值而取前一个作为起点,第二个最小值位置前缀和是 0

本题前缀和可以为 0,因此每个最小值都能取,分析失效。

证 Catalan 数时,可以在开头放个 1,但本题中有多种不等价的正数,这种做法是无效的。

在结尾放个 −1,问题变成前 m 个元素前缀和非负,且总和为 −1

类似地,所有循环移位中现在只能取第一个最小值位置作为起点了,否则跨过序列结尾,之前的最小值位置前缀和会变成 −1

m+1 个点共有 m! 种圆排列,而序列中有 m−n+1等价−1 只能取额外放置的 1 个放在结尾(结尾一定是 −1),因此答案 \frac{m!}{m−n+1}

P.S. 对于第一个结论,如果和为 s,那么有 s 种循环移位。

avatar
zc
2020-11-25 09:44:26

查看原题

点击跳转

avatar
zc
2020-11-20 18:35:46

查看原题

点击跳转

1/67
Search
search