UOJ Logo ydc的博客

博客

HAOI2015

2015-04-25 21:16:48 By ydc

写在前面

这场考试我参与了出题

大概是这样的,有三题是某横竖哥出的,我参与了验题,其中有两道正解一道暴力

然后我抄了ZJOI一道题,并向vfk借了一道题

所以我会做4道题

我不知道每道题目的题目名……所以,咳咳咳

一个树形dp题

题意

有一棵$n$个点的边代权树,每个点都是白点,然后你要选择$k$个点将其染黑

一棵树的价值是白点两两间的距离和加黑点两两间的距离和

最大化价值

$n \le 2000$

题解

首先我们要知道的是,这么一份伪代码的复杂度是$O(n^2)$的

void Tree_Dp(int p)
{
    size[p]=1;
    each(x,son[p])
    {
        Tree_Dp(x);
        for(int i=0;i<=size[p];++i)
            for(int j=0;j<=size[x];++j)
                update dp[p][i+j];
        size[p]+=size[x];
    }
}

复杂度的证明?考虑那个二重循环,可以看做分别枚举两棵子树的每个点。你会发现,点对$(u,v)$,只会在Tree_Dp($lca(u,v)$)处被考虑到,所以复杂度是$O(n^2)$

换句话说,$i$所考虑到的点的DFS序一定小于$j$所考虑到的点

于是我们就可以$dp_{i,j}$表示子树$i$选了$j$个黑点,然后转移暴力枚举子树里选了几个黑点,复杂度还是$O(n^2)$的,关键是怎么转移

其实说白了还是设状态的问题,如果设他是子树$i$选了$j$个黑点,子树内的同色点对距离和的话,是不好转移的对吧……所以我们要把他们往子树外连的也考虑进来

这么讲吧,假设我们把任意一对同色点之间的路径给标一下,那么$dp_{i,j}$记录的就是,子树$i$选了$j$个黑点,子树内的所有被标过的路径权值和,这样就能转移了

简单地说,就是改变一下状态定义,就能让他不仅考虑子树$i$内部的和,把子树外的延伸到子树内的那些边也考虑了

这是我验题的代码

void update(LL &a,LL b)
{
    if(a<b)
        a=b;
}
void DFS(int p,int fa)
{
    static LL tmp[maxn];
    fill(dp[p]+2,dp[p]+n+1,-INF);
    size[p]=1;
    for(int i=start[p];i;i=next[i])
        if(to[i]!=fa)
        {
            int q=to[i];
            DFS(to[i],p);
            fill(tmp,tmp+size[p]+size[q]+1,-INF);
            for(int j=0;j<=size[p];++j)
                for(int k=0;k<=size[q];++k)
                    update(tmp[j+k],dp[p][j]+dp[q][k]+len[i]*(k*(m-k)+(size[q]-k)*(n-m-(size[q]-k))));
            size[p]+=size[q];
            for(int j=0;j<=size[p];++j)
                dp[p][j]=tmp[j];
        }
}

一个数据结构题

题意

一棵$n$个点带权的树,$m$个操作,分别是:单点加、子树加、查询点到根的链的权值和

题解

这题是超级良心送分题啦~考验基础数据结构水平

(算了还是卖卖萌把这题讲讲)

算贡献

假设点$u$的子树加了$x$,点$v$在点$u$的子树内,那么对$v$到根的链的权值和会带来$(dep_v-dep_u+1)x$的贡献

假设点$u$加了$x$,点$v$在点$u$的子树内,那么对$v$到根的链的权值和会带来$x$的贡献

$dep$数组是常量,我们设一个点$i$到根的链的权值和为$k_idep_i+b_i$

那么子树加操作就是把整棵子树里每个点的$k$值和$b$值加上同一个数,单点加操作就是把整棵子树的$b$值加上同一个数

子树可以转为DFS序的一段区间,所以用两个树状数组分别维护每个点的$k,b$数组就行了

str

题意

你有一个长度为$n$的数字串。

定义$f(S)$为将$S$拆分成若干个$1 \sim m$的数的和的方案数,比如$m=2$时,$f(4)=5$,分别为:

$4=1+1+2,4=1+2+1,4=2+1+1,4=2+2,4=1+1+1+1$

你要将这个数字串分割成若干个数字(允许前导0),将他们加起来,求$f$,并求和,和为$g$。

比如$g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。

已知字符串和$m$后求答案对$998244353(7×17×223+1$,一个质数$)$取模后的值。

字符串长度不超过$500$,$m \le 5$

题解

ydc从ZJOI上抄的原题,来源是ZJOI2011年的细胞

首先考虑$f$怎么求,很容易发现$f(n)=\sum\limits_{i=\max(0,n-m)}^{n-1} f(i)$。由于$m$只有$5$,我们可以用一个$m \times m$的矩阵表示转移矩阵,记作$A$。

那么答案就是一堆$A$的若干次方的和(两个$m \times m$的矩阵是可以相加的)。

假设我们把数字串分成$k$个数,分别是$a_1,a_2,a_3,\cdots,a_k$,那么答案是$A^{a_1+a_2+a_3+\cdots+a_k}$,他恰好等于$A^{a_1} \times A^{a_2} \times A^{a_3} \cdots \times A^{a_k}$。

一堆$m \times m$的矩阵,不仅能乘,还能加,还有分配律,我们就能$dp$了

$dp$当然就是$dp_i$表示$1 \sim i$这部分的答案矩阵,转移显然,贴下标程的代码吧

    for(int i=1;i<=n;++i)
    {
        now=pw[0][a[i]-'0'];
        F[i].n=F[i].m=m;
        for(int j=i-1;j>=0;--j)
        {
            F[i]+=now*F[j];
            if(j)
                now=now*pw[i-j][a[j]-'0'];
        }
    }

复杂度是$O(n^2m^3)$

set

题意

一个有$n$个元素的集合,你有一个空集,每次你会选择集合的一个子集,与当前集合进行取并集操作,问期望多少次后第一次变成全集,选中每个子集的概率是输入给你的

$n \le 20$

题解

vfk教ydc做人

先来普及一点科技

定义一种乘法为$c[n]=\sum\limits_x\sum\limits_y a[x]b[y] [x \mid y=n]$

定义一种子集和变换,即$f(n)=\sum\limits_{x \subseteq n}g(x)$

我们用子集和变换来考虑上面的乘法

左边自然是$\sum\limits_{x \subseteq n}c_x$,右边应该是$\sum\limits_{x \subseteq n}\sum\limits_{y \subseteq n} a[x]b[y]=\sum\limits_{x \subseteq n}a[x]\sum\limits_{y \subseteq n}b[y]$

有没有发现什么?进行了子集和变换之后,之前的奇怪乘法,变成了人们熟知的点积

那么我们只要把$a,b$给子集和变换一下,点积得到$c$,再把$c$变回来

说到这里,介绍一点科技:如何巧妙地子集和变换与变回来

    for(int i=0;i<n;++i)
        for(int j=0;j<N;++j)
            if(j>>i&1)
                a[j]+=a[j^(1<<i)];
    for(int i=0;i<n;++i)
        for(int j=0;j<N;++j)
            if(j>>i&1)
                a[j]-=a[j^(1<<i)];

分别是变换与变回

好吧回归正题

读入的数组是$p$,将它看作多项式,先用定义的乘法来考虑,那么$p^k$的第$i$项就代表$k$轮之后得到$i$的概率

答案是$\sum\limits_{k}k \times (p^k-p^{k-1})[2^n-1]$。我们设$f(x)=\sum\limits_{k}k \times (p^k-p^{k-1})[x]$

由于定义的那个乘法太麻烦,就子集和变换一下,就变成了我们所熟知的点积了(不是多项式乘法)

$(p^k)[x]$就是$p[x]^k$

$f$的子集和变换后的结果,是$\sum\limits_{k}k \times (p^k-p^{k-1})=-(1+p+p^2+p^3+\cdots)$

由于$p$所有元素加起来才是$1$,那么子集和变换后的$p$里每个值,肯定也是在$[0,1]$之间的

于是$-(1+p+p^2+p^3+\cdots)$可以$O(1)$算出,得到了$f$的子集和变换结果,变回去即可

时间复杂度:$O(n2^n)$

我的集训队作业

2015-01-24 20:38:20 By ydc

弃疗大法好。

虽然自称自己想要通关,最终还是认输了。

现在想来我的确也没有通关过什么东西。

淡淡地忧伤。真不知道我这多出的52题是用来干嘛的。

完成量152/158。希望可以帮助到大家。有题解甚至是代码。

未完成题目:

Codeforces 335F buy one, get one free

GCJ 2012 Final E Shifting Paths

GCJ 2010 Final E Ninjutsu

GCJ 2011 Final D Ace in the Hole

GCJ 2011 Final E Google Royale

GCJ 2012 Final C Xeno-archaeology

我的集训队作业

对排序算法的深入研究

2014-11-26 19:50:29 By ydc

OI中有很多排序算法,冒泡排序,插入排序,快速排序,基数排序,以及神一般的bogo排序等等等等。

在这门不断追求速度的学科里,最快的排序方法是什么一直是信息学皇冠上的明珠。基数排序是线性的,但是却有非常大的局限性,仅仅基于比较的排序复杂度的下限是多少呢?

有一天,一个人出来妖言惑众:“基于比较的排序复杂度下限是$O(n \log n)$的。”并且提出了伪证。

他用一棵二叉树来建立模型,通过对树的深度进行探究,从而推出排序的复杂度下限。于是人类停滞不前,再也没有人试图创新。

然而事实上,他的行为有着一个巨大的漏洞:那人试图利用大家对树的不甚了解以及其巧妙地误导,愚弄了大家。在此,我们来重新分析树的深度。

我们来真正思考真正的树要具有什么样的性质:根据生物课上所讲的,一棵树不可能无限的生长下去,也就是说一棵树的深度应该是常数;然而他的假树却不同,随着叶子的不断增加,树的深度是会跟着不断增加的——是一个发散的数列!这显然与树的深度不能无限增长这个生物知识相矛盾!虽然由于他巧妙地文字以及我智商的程度至今我还不清楚他是在哪一步偷天换日,将树的深度由有上限变成了没有上限,但既然我们已经知道他认为树的深度是$O(\log n)$这点绝对是错的,我们就有理由继续深入思考。

然而,由于智商所限,我再也没有过一丝成果。我清楚地意识到我尚未领悟人类智慧的力量,于是我开始四处遍寻高人。为了能抹去这个多年笼罩在大家头上的乌云,让人类文明进入新的时代,我曾以囚徒身份进了北京八十监狱寻找至今没人知道身份的黄半仙,曾请教过湖北一位统领全宇宙跳蚤的国王,却一直没能得到满意的结果。终于有一次,我跟随着黄半仙,来到了帝都航天大学吃特色菜(CTSC),在吃特色菜的过程中,我见到了人类智慧之神——Mato_No1

Mato_No1上台讲述了自己的研究成果,他告诉了我一个惊天动地的消息:开了O2的set是$O(1)$的!

顿时,我感到一道曙光冲破了乌云:是不是只要我们将元素插入开了O2的set,再遍历输出,就能得到$O(n)$的排序方法了呢?这样子的话,那棵树的深度也是$O(1)$的啊。

然而事实却再一次给了我打击,我学习了set这个数据结构,然而我很不解的是他明明是一种叫做平衡树的东西进行维护,但是trajan告诉我,平衡树是$O(\log n)$的。trajan大神与Mato_No1大神的思维产生了碰撞,我一遍遍的回忆,终于意识到了真相:开了O2的set!

O2是什么?氧气啊。众所周知,树在有氧气的情况下,会进行呼吸作用!学科的知识再一次产生了交叉,生物学的知识推进了信息学的发展!我们必须明白,平衡树遇上O2进行呼吸作用后,究竟会有怎样惊人的效果!

然而我却再也没有见到Mato_No1,据说他已经进了五道口男子职业技术学校,那里有更多更多的大神,我想,要知道信息学与生物学本质上的联系,也许只有那里的大神才能回答。为此,我于同年七月踏上了南下的火车,得到了进入五道口的机会,从而于明年暑假结束后去寻求真相。然而,没有想到的是,这个真相来的比我预料中的更早。

在昨天,通过一个偶然的机会,我看到了一个叫猪猪侠的大神所写的神奇数据结构Spaly。短短几行代码,却显示了其超高的水平,让我捉摸不透。由于智商差异过大,我只能体会其神奇却不知其原理。可没过多久,noip吧的前吧主却对数据结构Spaly进行了解答

看了这段话,人类多年的疑惑在前吧主轻描淡写的话语中,已得到了解答。真相只有一个!

是的,单旋的Spaly,可以$O(1)$的完成平衡树的操作!这也与树的深度是常数这个科学道理是吻合的!我们可以想象,当set里的那棵平衡树遇到了氧气后,他进行着呼吸作用,每次再也不需要费力的进行双旋,深度也瞬间变成常数!无论树的叶子再怎么多,他的深度永远是常数!

至此,$O(n)$的排序方法诞生了。我们要感谢Mato_No1大神与猪猪侠大神,当然还有对其进行了最终的总结的前吧主Foreseeable!此外还要感谢CCTV,感谢MTV,感谢父母,感谢祖国!

参考文献:

  • Mato_No1在吃特色菜过程中的讲话
  • 猪猪侠公开出来的代码
  • Foreseeable在贴吧里的发言

04已露出庐山真面目

2014-11-18 08:52:40 By ydc

似乎很多小朋友一直在奇怪04是什么题

现在vfk把它放出来了,大家快去切啊!

UOJ的第一道非传统题^_^

撒花

noip 2014 day2 T3 ydc题解

2014-11-09 14:33:07 By ydc

一个$O(nm)$的做法是枚举并在模意义下验根,但是单纯这么做几乎不可能过

容易证明对于原方程的一个根$x$,必有$x|a_0$

$a_0$在$[1,m]$内的约数个数不会特别多,我们如果能做到只对他的约数验根,那么验根的时间是能够承受的,于是瓶颈在于找$[1,m]$内的所有约数

利用筛法的思想,我们找所有形如$p^k$,$p$为质数的不能被$a_0$整除的数,将他们的倍数筛去。

$a_0$的指数和当然不会太大,我们真正的瓶颈在于——对于每个质数,要试验他是否是$a_0$的约数

记$\pi(n)=n/ln(n),L=\lg a_0$,这样的时间复杂度是$O(L\pi(n))$的,显然过不去

压位大法好,第一反应是压9位

int sum=0;
for(int i=1;i<=n;++i)
    sum=((LL)sum*1000000000+a[i])%p;

可以判断$p$是否是$a_0$的约数

但是这样子经实测仍然过不了

如果压18位的话

int sum=0;
for(int i=1;i<=n;++i)
    sum=((LL)sum*1000000000000000000LL+a[i])%p;

乘的是个常数,我们完全可以预处理一个变量表示$10^{18} \mod p$

这样子的复杂度是$O(L\pi(n)/18)$,我考试的时候本机跑$(x-10^{100})^{100}$是0.8s多接近0.9s也许会挂

考完之后zty告诉我说,对于大于$10^5$的质数,筛去他的倍数意义不大,那么我们调一下筛的大小,只筛$10^5$以内的约数,超过$10^5$以内不能被$a_0$整除的质数(以及他们影响到的数)还是用验根的方法,用这个常数优化就能比较快的出解了

UPD:

已挂

不过我们还有70分!

ydc个逗逼,滚粗了

ydc Avatar