zcmimi's blog

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

avatar
zc
2020-10-19 21:49:55

查看原题

点击跳转

f[sta]为死了的猪状态为sta时最少需要多少鸟

f[sta|line(i,j)]=\min(f[sta]+1)(line(i,j)表示经过i,j的抛物线能杀死的🐖的集合)

f[sta|(1<<i)]=\min(f[sta]+1)

优化:

若令x为满足sta\&(1<<(x-1))=0的最小正整数,则由sta扩展的转移的所有线都要经过x

avatar
zc
2020-10-19 19:55:41

查看原题

点击跳转

f(i,j,0),f(i,j,1)表示:

i个时间段,已经用了j个机会,选择c_i与选择d_i(换/不换教室)的最小期望

dis(i,j)表示i,j之间最短距离

转移方程:

f(i,j,0)=\min \begin{cases} f(i-1,j,0)+dis(c_{i-1},c_i)\\ \begin{aligned} f(i-1,j,1) &+dis(d_{i-1},c_i)\times k_{i-1}\\ &+dis(c_{i-1},c_i)\times(1-k_{i-1}) \end{aligned} \end{cases}

f(i,j,1)=\min \begin{cases} \begin{aligned} f(i-1,j-1,0) &+dis(c_{i-1},d_i)\times k_i\\ &+dis(c_{i-1},c_i)\times (1-k_i) \end{aligned}\\ \begin{aligned} f(i-1,j-1,1) &+dis(d_{i-1},d_i)\times k_{i-1}\times k_i\\ &+dis(c_{i-1},d_i)\times (1-k_{i-1})\times k_i\\ &+dis(d_{i-1},c_i)\times k_{i-1}\times (1-k_i)\\ &+dis(c_{i-1},c_i)\times (1-k_{i-1})\times (1-k_i)\\ \end{aligned} \end{cases}

avatar
zc
2020-10-19 16:24:55

查看原题

点击跳转

n个位置中选出m个位置后剩余n-m个位置错排

{n\choose m}\cdot D_{n-m}

avatar
zc
2020-10-17 11:25:38

查看原题

点击跳转

x构造一个矩阵满足a(i,j+1)=2a(i,j),a(i+1,j)=3a(i,j)

对于这个矩阵,我们不能选相邻的数,也就是说答案为不选相邻的数的方案数

这个矩阵长\log_2 n(不超过17),宽\log_3 n(不超过12),因此可以用状压dp解决

我们只需要对不是2,3倍数的数都构造一个矩阵就可以覆盖所有的数,容易发现每个矩阵互不相同,所以根据乘法原理把答案相乘即可

avatar
zc
2020-10-16 21:05:56

查看原题

点击跳转

s_i为已经确定的m人中编号不小于i的个数

若存在s_i>n-i+1,显然无解

考虑动态规划,设f(i,j)表示剩下n-m个人中有j个人编号不小于i

\displaystyle f(i,j)=\sum_{k=0}^j f(i+1,j-k)\cdot {j\choose k}, 其中j\le n-s_i-i+1

最终答案为f(1,n-m)

avatar
zc
2020-10-16 13:31:15

查看原题

点击跳转

编号在[L,R]的同学添加第x位同学为自己的观察对象。保证x<L\le R

从左到右考虑,如果当前这个人没有观察在他之前的人,那么就必须让他听到指令

否则他观察的人在之前已经考虑过了

所以需要听到指令的人就是没有观测的人

那么用线段树维护区间就可以了

avatar
zc
2020-10-15 22:15:41

查看原题

点击跳转

首先可以用并查集判断每个1操作是否有效

接下来很容易可以想到树剖+线段树优化建图

很可惜,出题人卡了这种大常数做法

考虑直接在树上倍增优化建图

和倍增lca差不多,一直向上连边

而每个点又拆为入点和出点

每次构建传送门时新建一个点,

连边时只需要[u_1,v_1]所在的块出点连接新建点,新建点连接[u_2,v_2]所在的块入点

详细见代码

avatar
zc
2020-10-14 18:06:50

查看原题

点击跳转

结论: \gcd(f_n,f_m)=f_{\gcd(n,m)},然后矩阵快速幂加速即可

证明:

m>n

引理:

  • \gcd(f_n,f_{n+1})=1

    根据辗转相减法, \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n+1}-f_n)=\gcd(f_n,f_{n-1})

    所以 \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n-1})=\dots=\gcd(f_2,f_1)=1

  • f_{n+m}=f_nf_{m-1}+f_{n+1}f_m

    数学归纳法:

    1. n=m=1时,成立
    2. 假设m,n\le k时成立,当n=k+1时:

      \begin{aligned} f_{n+m} &=f_{m+(k+1)}=f_{k+(m+1)}\\ &=f_mf_{k-1}+f_{m+1}f_k\\ &=f_mf_{k-2}+f_{m+1}f_k + f_{m+1}f_{k-1}+f_{m+2}f_k\\ &=f_{m+1}(f_{k}+f_{k-1})+f_{m}(f_{k-1}+f_{k-2})\\ &=f_kf_m+f_{k+1}f_{m+1} \end{aligned}

  • \gcd(f_{n+m},f_n)=\gcd(f_n,f_m)

    \begin{aligned} \gcd(f_{n+m},f_n) &=\gcd(f_nf_{m-1}+f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1},f_n)\cdot\gcd(f_m,f_n)\\ &=\gcd(f_m,f_n) \end{aligned}

\begin{aligned} \gcd(f_n,f_m) &=\gcd(f_n,f_{m-n+n})\\ &=\gcd(f_n,f_{m-n}f_{n-1}+f_{m-n+1}f_n)\\ &=\gcd(f_n,f_{m-n}f_{n-1}) \end{aligned} \\ \because \gcd(f_{n},f_{n+1})=1\\ \therefore \gcd(f_n,f_{m-n}f_{n-1})=\gcd(f_n,f_{m-n})

这样一直碾转相减下去,就是f_{\gcd(n,m)}

avatar
zc
2020-10-13 21:50:58

查看原题

点击跳转

很容易想出普通的dp

不过n \le 10^{18},所以要构造加速矩阵,使用矩阵快速幂

avatar
zc
2020-10-13 21:01:06

查看原题

点击跳转

首先将所有RNA序列插入trie

然后用病毒模版片段trie上搜索

对于?,可以匹配任意一种

对于*,可以选择

  1. 不匹配,*当作没有
  2. 匹配,下一个停止用*匹配
  3. 匹配,下一个继续用*匹配
2/66
Search
search