zcmimi's blog
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

avatar
zc
2020-09-27 14:05:00

查看原题

点击跳转

统计方法类似扫描线

lp排序,按顺序枚举

l的时候更新,在r之后还原(p已经不在区间[l,r]中了,不受影响)

以时间为下标,维护某个时间段内大于等于y的数个数

需要一个数据结构维护区间中大于等于某个数的个数(带修改),可以想到分块

avatar
zc
2020-09-25 20:03:00

查看原题

点击跳转

根号分治论文题

题意

给一个序列序列A,单点修改,

查询\displaystyle \sum_{i\mod p=k} A_i

avatar
zc
2020-09-23 21:26:00

查看原题

点击跳转

使用ida*

首先将数组离散化为1,2,\dots,n

一次翻转最多只能改变一对相邻数的差,

因此对于一个序列,有多少对相邻的数差不为1,就至少要翻转多少次。

估价函数:

a[n+1]=n+1;
int h(){
    int cnt=0;
    for(int i=1;i<=n;++i)cnt+=(a[i]!=a[i+1]+1&&a[i]!=a[i+1]-1);
    return cnt;
}
avatar
zc
2020-09-23 16:31:00

查看原题

点击跳转

记录每段区间操作后:

向上k级祖先,向下d级孩子,该层向右的第i个孩子

线段树维护即可

avatar
zc
2020-09-22 22:01:00
查看原题

点击跳转

链上的情况

情况一

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树统计即可

情况二

考虑每个点对答案的贡献,分类讨论

  1. i\in [1,A]

    那么满足的y\in (pre_i,i],x\in [i,A]

    x\in (pre_i,i],y\in [i,B]

    总贡献为\sum (i-pre_i)\times(A+B-2i+2)-1

    (-1为了避免[i,i]被重复计算)

    拆下式子: (A+B+2)(\sum i-pre_i)-2(\sum i(i-pre_i))-\sum 1

    可以发现这种情况可以直接前缀和维护

  2. i\in (A,B],满足pre_i<A

    那么满足的x\in (pre_i,A],y\in [i,B]

    总贡献为\sum (A-pre_i)\times(B-i+1)

    拆下式子(A\sum 1-\sum pre_i)(B+1)-A\sum i+\sum ipre_i

    可以发现这种情况可以用主席树维护

树上情况

观察数据形成方式:

  • p个点形成一条主链,其他点随机向主链连边
    所以树上任意点对的\texttt{lca}距离他们期望为\mathcal O(\log n)
  • 每个点的颜色在[1,n]中随机,每种颜色数目期望为1

pre_ii的祖先中颜色与i相同的深度最大的点

第一问

xyx\texttt{lca}(x,y)更近

首先求出y\texttt{lca}链上的颜色总数,

然后再暴力枚举x\texttt{lca}链上的颜色更新答案

第二问

ABA\texttt{lca}(A,B)更近

分类讨论:

  1. x\in [1,\texttt{lca}],y\in [1,B],与链上的情况相同
  2. x\in [\texttt{lca},A],y\in [1,\texttt{lca}]

    x\in [1,A],y\in [1,\texttt{lca}]的答案减去

    x,y\in [1,\texttt{lca})的答案\sum (2(i-pre_i)(\texttt{lca}-i)-1)

    拆下式子: 2\texttt{lca}\sum (i-pre_i) - 2\sum i(i-pre_i)-\sum 1

  3. x\in [\texttt{lca},A],y\in [\texttt{lca},B]

    先求出i\in [\texttt{lca,B}]的贡献\sum (B-i+1)(A-\texttt{lca}+1)

    拆下式子: (A-\texttt{lca}+1)(\sum B+1 - \sum i)

    然后用i\in (\texttt{lca},A]更新

    pre_i\le\texttt{lca},设j[\texttt{lca},B]中第一个与它颜色相同的点

    贡献: (A-i+1)(j-\texttt{lca})

avatar
zc
2020-09-21 21:09:00

查看原题

点击跳转

解法

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树

#include<bits/stdc++.h>
const int N=1000011;
int n,q,lst[N],RT[N],sz,s[N*20],ls[N*20],rs[N*20];
void build(int&x,int l,int r){
    x=++sz;
    if(l==r)return;
    int m=l+r>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
void ins(int&x,int pre,int p,int l,int r){
    s[x=++sz]=s[pre]+1;
    if(l==r)return;
    ls[x]=ls[pre],rs[x]=rs[pre];
    int m=l+r>>1;
    if(p<=m)ins(ls[x],ls[pre],p,l,m);
    else ins(rs[x],rs[pre],p,m+1,r);
}
int ask(int x,int y,int R,int l,int r){
    if(r<=R)return s[y]-s[x];
    int m=l+r>>1;
    return ask(ls[x],ls[y],R,l,m)+(R>m?ask(rs[x],rs[y],R,m+1,r):0);
}
void read(int&x){
    x=0;char c=getchar();
    for(;c<'0'||'9'<c;c=getchar());
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-48;
}
int main(){
    read(n);
    int x,l,r;
    build(RT[0],1,n);
    for(int i=1;i<=n;++i)
        read(x),
        ins(RT[i],RT[i-1],lst[x]+1,1,n),
        lst[x]=i;
    read(q);
    while(q--)
        read(l),read(r),
        printf("%d\n",ask(RT[l-1],RT[r],l,1,n));
}

主席树理论上是可以过的,可是为了卡莫队,主席树也TLE了

R.I.P

树状数组

还是求[l,r]pre_i<l的个数

离线处理

询问按右端点从小到大排序

枚举区间,将[1,r]中的点,i位置+1,pre_i位置-1(i之前pre_i已经贡献过了)

那么r减去l-1的前缀和就是答案

12/74
Search
search