zcmimi's blog

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

avatar
zc
2020-10-07 20:03:39

查看原题

点击跳转

题意:

n个节点的树,有r种属性,每个点属于一种属性.有q次询问,每次询问给r_1,r_2,问有多少对点(e_1, e_2)满足e_1属性为 r_1,e_2属性为r_2,且e_1e_2的祖先. (n,q \le 2 \times 10^5, r \le 25000,时限5s)

首先将询问离线

不管枚举e_1统计子树中e_2的数量

还是枚举e_2统计到根节点路径上e_1的数量

都是\mathcal O(nr)

可以考虑将两种方法结合,使用根号分治

r_2的总数目为S

S\ge \sqrt n,枚举e_2,统计e_1(不超过\sqrt n个),复杂度\mathcal O(q\sqrt n)

否则枚举e_1,统计e_2(子树中的r_2不会超过\sqrt n个),复杂度\mathcal O(n\sqrt n)

具体看代码

avatar
zc
2020-10-06 10:38:49

查看原题

点击跳转

可以发现除了x地图,其他地图都只有两种状态,

如果没有x地图,那就是2-sat裸题,

x地图最多只有8张,我们可以暴力枚举x地图

avatar
zc
2020-10-06 00:18:02

查看原题

点击跳转

首先每条边(x,y)至少有一个端点是关键点

条件 连边
x,y任选一个 \neg x\to y,\neg y\to x

接下来是对每部分进行连边

若将每个点向该部分中出它以外的所有点连边,复杂度为\mathcal O(n^2)

我们可以前缀优化建图

设该部分为a_1,a_2,\dots,a_w

对每个点a_i新增一个状态pre_{a_i}表示a_{1\sim i}中有没有被选为关键点

条件 连边
a_i,pre_{a_i}必须同时选 a_i\to pre_{a_i},\neg pre_{a_i}\to \neg a_i
pre_{a_{i-1}},pre_{a_i}必须同时选 pre_{a_{i-1}}\to pre_{a_i},\neg pre_{a_{i-1}}\to \neg pre_{a_i}
pre_{a_{i-1}},a_i不能同时选 pre_{a_{i-1}}\to \neg a_i,a_i\to \neg pre_{a_{i-1}}

这样就可以\mathcal O(n)连边了

avatar
zc
2020-10-05 16:10:20

查看原题

点击跳转

avatar
zc
2020-10-03 11:47:30

查看原题

点击跳转

avatar
zc
2020-09-29 12:40:52

查看原题

点击跳转

s_i为每个连通块点数

对每个连通块构建prufer序列

由于度数为边数两倍,\displaystyle \sum_{i=1}^k d_i=2k-2

对于给定d序列构造prufer序列的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1} = \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdot(d_k-1)!}

对于第i个连通块,它的连接方式有s_i^{d_i}种,对于给定d序列使图连通的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

枚举d序列:

\displaystyle \sum_{d_i\ge 1,\sum d_i=2k-2} {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

换元,设e_i=d_i-1:

\displaystyle \sum_{e_i\ge 0,\sum e_i=k-2} {k-2\choose e_1,e_2,\dots,e_k}\cdot \prod_{i=1}^k s_i^{e_i+1}

根据多元二项式定理:

\displaystyle (x_1+x_2+\dots+x_m)^p=\sum_{c_i\ge 0,\sum c_i=p} {p\choose c_1,c_2,\dots,c_m}\cdot \prod_{i=1}^m x_i^{c_i}

原式化简得:

\displaystyle (s_1+s_2+\dots+s_k)^{k-2}\cdot \prod_{i=1}^k s_i

\displaystyle n^{k-2} \cdot \prod_{i=1}^k s_i

avatar
zc
2020-09-28 20:30:29

查看原题

点击跳转

prufer序列应用模板

n个点的完全图有2^{n-2}棵生成树。

对于给定度数为d_{1\sim n}​的一棵无根树共有\dfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}​种情况

全部全排列方案数除以每个点i的排列方案数(除去重复的)

i个点度数为d_i​,会在prufer序列中出现d_i-1次,全排列方案数为(d_i-1)!

由于答案很大10^17并且爆long long,过程中有除法,所以使用python3自带高精度非常方便

python3代码:

n=int(input())
if n==1: # 特判
    print(1 if int(input())==0 else 0),exit()
# 阶乘
f=[1]*(n+1)
for i in range(1,n+1):f[i]=f[i-1]*i
# 计算
ans=f[n-2]
tot=0
for i in input().split():
    x=int(i)
    if x==0:print(0),exit()
    ans//=f[x-1]
    tot+=x-1
print(ans if tot==n-2 else 0) # 特判

为了避免除法,我们可以换一种统计方式,

依次把第i个点d_i-1个出现的数插入到prufer序列中,答案乘以方案数,空位数减去d_i-1

记得特判

c++代码

avatar
zc
2020-09-28 11:26:35

查看原题

点击跳转

假设当前有了i个瓶盖,还差n-i个瓶盖

再买一个瓶盖在差的n-i个中的概率为\frac 1{n-i},

期望再买\dfrac n{n-i}次后拥有i+1个瓶盖

全部加起来就是\displaystyle \sum_{i=0}^{n-1} \frac n{n-i}

最终就是\displaystyle \left( \frac nn + \frac n{n-1}+\frac n{n-2}+\dots+\frac n1\right)

\frac xy+\frac ni=\frac {xi+yn}{yi}

avatar
zc
2020-09-27 21:04:47

查看原题

点击跳转

首先至少需要m-1个空位,然后剩下的n-m+1个位置可以乱放

答案: A_{n-m+1}^m

avatar
zc
2020-09-27 18:39:00

查看原题

点击跳转

题意:

\displaystyle \sum_{i\mod 2=0} {n\choose i}

题解

  1. {n\choose 0}+{n\choose 1}+{n\choose 2}+\dots+{n\choose n}=0
  2. {n\choose 0}-{n\choose 1}+{n\choose 2}-\dots+(-1)^n{n\choose n}=0
  3. {n\choose 0}+{n\choose 2}+{n\choose 4}+\dots={n\choose 1}+{n\choose 3}+{n\choose 5}+\dots=2^{n-1}

证明

二项式定理:

(a+b)^n={n\choose 0}a^n+{n\choose 1}a^{n-1}b+\dots+{n\choose i}a^{n-i}b^i+\dots+{n\choose n}b^n

a=b=1时,可证明1,

a=-1,b=1时,可证明2,

1式+2式可证明3

4/66
Search
search