zcmimi's blog

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

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的前缀和就是答案

avatar
zc
2020-09-18 14:08:00
查看原题

点击跳转

传统解法

暴力的思路是求出k个点两两之间最短路径

我们可以按二进制逐位对k个点染色(该位为1染为黑色,否则染为白色)

每次求出黑点到白点的最短距离,更新答案

这样可以保证k点中每对点 至少有一次被分别染色为黑和白

复杂度n \log n \log k

avatar
zc
2020-09-15 20:16:00
查看原题

点击跳转

g(n)为点数为n的无向图个数

g(n)=2^{n\choose 2}

f(n)为点数为n的简单无向连通图的数量

枚举连通块个数i可得

\displaystyle g(n)=\sum_{i=0}^n \frac{f(i)}{i!}

发现这个形式很眼熟(生成函数):

g=e^f

那么f=\ln g

求出g\ln就可以得到f

avatar
zc
2020-09-15 18:49:00
查看原题

点击跳转

给两个手环同时增加亮度,与给其中一个增/减亮度是一样的

同时旋转两个手环,旋转其中一个是一样的

设旋转后两个手环分别为a,b,其中一个加上x

那么就是让\sum_{i=1}^n (a_i-b_{i}+x)^2最小

\displaystyle \sum_{i=1}^n (a_i-b_{i}+x)^2\\ =\sum_{i=1}^n a_i^2+\sum_{i=1}^n b_i^2+nx^2+2x(\sum_{i=1}^n a_i-b_i)-2\sum_{i=1}^n a_ib_i

其中只有最后一项是变化的,前几项都可以直接求得

nx^2+2x(\sum_{i=1}^n a_i-b_i)是关于x的二次函数,直接求得最小值

考虑\sum_{i=1}^n a_ib_i

可以发现\sum_{i=1}^n a_{n-i+1}b_i是卷积的形式

那么我们把a倍长,把b翻转,然后再卷积,得到n+12n次项中的最大值就是\sum_{i=1}^n a_ib_i的最大值

avatar
zc
2020-09-15 06:56:00
查看原题

点击跳转

可以发现,每次变化后只有那些周围有与它同色的格子发生变化

也就是连通块发生变化

而每次连通块发生变化,又会并入一些单独的格子

我们只需要bfs找出每个方块什么时候被纳入连通块就可以了

查询时判断一下奇偶

avatar
zc
2020-09-14 16:17:00
查看原题

点击跳转

可以说是很水吧

缩点后每个环只需要环上最小的费用就可以保证环安全

一个环方案数为环上最小值的数量

总方案数为所有环方案数的乘积

(一个点也算一个环)

5/66
Search
search