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个逗逼,滚粗了

NOIp2014 Day1 民间题解

2014-11-08 13:57:22 By ydc

萌萌哒ydc来放题解了

先放day1,day2明天才考

T1

考你会不会编程

T2

$n$个点$n-1$条边的无向连通图就是个树

考虑距离为2的点对,可以理解为枚举$i$,$i$能走到的点集两两之间距离为$2$

我们要做的是对于一个数组$a_1,a_2,a_3,\ldots,a_m$,要求$a_ia_j,i \neq j$的Σ与max

max是个很简单的事情,你只要求$a$数组的最大值与次大值即可

至于Σ,我们知道$\sum\limits_{i=1}^n \sum\limits_{j=1}^n a_ia_j=(\sum\limits_{i=1}^na_i)^2$,于是容易推出我们要求的就是$(\sum\limits_{i=1}^na_i)^2-\sum\limits_{i=1}^n a_i^2$

当然你也可以令$s=\sum\limits_{i=1}^n a_i$,求$\sum\limits_{i=1}^n a_i(s-a_i)$

复杂度应该是$O(n)$的

T3

我们很容易看出一个很经典的完全背包的框架:我们可以在某个时刻上升$1,2,3,\ldots \infty$次,有$n$个时刻

当然根据题意,这题和完全背包有很多的不同,比如能下降,不能选择上升$0$次,下界不可到上界不可越,有些位置不允许,等等等等

即使如此,我们仍然能以完全背包的思想为核心,解决这个题

由于是完全背包,显然可以用滚动数组优化将空间降为$O(m)$。为了便于理解,我们用二维状态来描述:$dp_{i,j}$表示横坐标为$i$,纵坐标为$j$的最小步数

由于不能上升$0$次,我们这样转移:$dp_{i,j}=\min(dp_{i-1,j-x_i}+1,dp_{i,j-x_i}+1)$

由于有障碍,我们求出$dp_{i,j}$后再将障碍位置的值赋值为$\infty$

由于上界可以越过,所以要特殊转移一下,$dp_{i,m}=\min(dp_{i-1,k}+s_k)$,$s_k$为$k$达到$m$处的花费,他是个式子,在此不将其展开

最后由于能下降,所以$dp_{i,j}$还可以由上一步在$j+y_i$的状态转移

如此问题就解决了,时间复杂度$O(nm)$

关于UOJ Test Round#1 T3的标程

2014-11-06 18:47:19 By ydc

今天下午wangck1998提出这题标程有误,经研究确实如此

错误原因在于求出中心之后,我以最大值和次大值的判断来更新答案,从而导致对于次大值为0的情况需要特判。由于没有考虑到……于是挂了

在此向大家提出歉意,并对wangck1998提出感谢,以及大家若还发现什么BUG,欢迎来找我

以后我们也会吸取教训,尽量避免出错

不得不说的是UOJ的hack功能的优越性就这么体现出来了呢……

UOJ Test Round #1 题解

2014-10-26 22:28:28 By ydc

vfk的数据

算法一

这题是一个对于字符串进行排序的题目

我们第一个想法是按照字典序相同

但这样有个问题,就是100.in的字典序比2.in要小。于是我们改为双关键字排序,即用(长度,字符串)作为一个二元组,以长度为第一关键字,字符串为第二关键字,进行排序

如果使用冒泡排序,复杂度是$O(n^2L)$,$L$为串长,能够得到$50\%$的分数

算法二

对于参加noip的选手,一般来说至少要掌握一种$O(n \log n)$的排序方式

比如使用快速排序,能够把时间复杂度优化为$O(n \log nL)$,可以得到满分

一种会错误的写法

有的人可能会想算出编号

但我们题目中从来没有提到过数字的大小范围,事实上即使你用$long\,long$进行存储,也是无法通过所有数据的

对于用$int$和用$long\,long$的,都是70分

算法三

如果数据范围加强,也是可以做的

问题主要在于字典序的比较,快速比较两个字符串大小,能用二分+hash的方法在$\log L$里算出,这样子做复杂度是$O(n \log n \log L)$

另外我们可以建立一棵trie,在tire上进行DFS一遍,可以$O(nL)$的预处理出所有字符串的字典序的排名

然后再进行排序,复杂度就是$O(nL+n \log n)$

trie树会有庞大的额外空间……

事实上我们可以改写成100关键字的基数排序来做的话,就能够避免字符集的影响,做到时空都不超过$O(nL)$了

pyx的难题

算法一

我们先来枚举那个题目的优先级

注意到排序后相邻两个优先级之间的所有数字是等价的,换句话我们可以枚举优先级的排名

枚举了排名之后,我们进行判定,如果使用最暴力的方法判定,就是进行模拟

我们用一个队列来存储所有题目,并让队列是有序的。如果新加一个题目,就$O(n)$的进行调整,使他重新有序。

这样的复杂度是:枚举$O(n)$,判定$O(n^2)$,总复杂度$O(n^3)$

如此可以得到$60\%$的分数

算法二

随着优先级的增高,完成他的时间只可能会变小

对于这种单调性,我们可以使用二分查找的方法优化

用二分查找进行优化,每次暴力判定,时间复杂度是$O(n^2 \log n)$

算法三

如果没有想到二分查找,有没有办法优化判定的过程呢?

注意到我们的模拟过程是这样的:添加一个题目,删除一个题目,并且还要随时随地的知道还没做完的题目里优先级最高的题目

那么我们并不需要$O(n^2)$的来做,事实上用堆(或者别的数据结构),是可以$O(n \log n)$的模拟全程的

时间复杂度仍然是$O(n^2 \log n)$

算法四

我们可以将算法二和算法三结合起来

二分答案,并用优先队列判定,可以在$O(n \log^2 n)$的时间里出解

可以得到90分

算法五

对于最后的点,数据范围是$3 \times 10^5$,即使手写堆,$O(n \log^2 n)$的时间复杂度也无法在时限内出解

我们需要想办法优化掉一个$\log$。然后第二问基本上毫无特殊性,要优化他几乎是不可能的(除非使用VEB树之类的东西,神犇请受我一拜);与之对应的是,第一问的二分是建立在单调性上的,而有单调性的题,往往可以试着利用扫描的方法去优化。

我们先假设特殊题目的优先级是-1(本质上是$-\infty$),进行一遍模拟

经过这一步模拟,我们可以得到$[t_x,T]$这个时间段里的信息:每个题目在$[t_x,T]$内所使用的时间

我们把在这个时间段里做过的题按优先级排序

那么找到前$i$小的,使得他们的存在时间和等于$s_x$,就相当于平移回去了!

如果题目允许实数,只要把他的优先级定为第i小的$+0.5$就好了;当然,由于要求互不相同,所以我们要找到一个最小的没有出现过的优先级。由于题目保证有解,所以找到的最小的一定是个合法解

由于不需要二分答案,所以时间复杂度$O(n \log n)$

ydc的大树

算法一

我们可以的进行一堆预处理,比如说任意两点的距离,他们路径上的所有点等等$\ldots$

接下来枚举摧毁的点,枚举所有黑点,利用预处理的信息进行判定。

朴素实现的话,时间复杂度是$O(nm^2)$,可以通过$30\%$的数据,即$1,2,7$号点

算法二

算法一预处理和距离是只需要$O(n^2)$的,但是预处理路径上所有点则是$O(n^3)$

注意到预处理路径上的所有点,是可以用压位技巧或者bitset来进行优化,这样时间复杂度就是$O(n^3/30)$,可以通过。

这个算法能得到60分

算法三

对于六号点,由于是链,所以每个黑点的距离要么是最左边的黑点,要么是最右边的黑点

预处理离最左边的点最远的点有哪些;预处理离最右边的点最远的点有哪些

枚举炸掉的点后,我们要求的就是最远点是最左边点的在他右边的点的个数以及最远点是最右边点的在他左边的点的个数

能得到链的10分

算法四

结合算法三与算法二,可以得到70分

算法五

为了方便描述,我们暂且认为每个点走到的就是单纯意义上的最远点

由于涉及到最远点的问题,我们引入一些中心的概念。(参考自noip原题树网的核)

树中最长的路径称为树的直径。对于给定的树$T$,直径不一定唯一。但可以证明各直径的中点唯一(不一定恰好是某个结点,可能在某条边的内部),我们称之为中心

我们还能证明,任何点走到离他的最远点一定经过了中心。如果中心不是某个节点而在边的内部,可以想象既然经过了这个点,必然经过边上的两个点。

我在此定义概念类中心。大概就是说,如果中心恰好是节点,那么他也就是类中心,否则就是它所在的边的任意一个端点。

可以证明,任何点走到离他的最远点一定经过了类中心。

既然类中心有这样优美的性质,那么它是否对我们解题有帮助呢?

我们将无根树变有根树,找到一个类中心,将它提根。

类中心的找法很容易,只需任意求出一条直径,根据定义来找即可。直径可以用做两次最远点或者树形动态规划的方法在$O(n)$时间内求出来,具体算法是noip级别知识,不再赘述。

我们枚举每个点,我们要做的就是看有哪些黑点走到最远点必须经过他。

利用类中心的性质,我们知道任意$a$走到$a$的最远点时必须经过根。判定$a$走到$a$的最远点是否必须经过$b$分两种情况:

  • $a$不在$b$子树内。我们只需记录每个子树内最深点的深度,拿$b$所在子树是不是覆盖了所有最深点之类的情况出来讨论即可。
  • $a$在$b$子树内。$a$走到$a$的最远点,必须经过根,于是必须经过$b$了。

当然我们还要注意到题目要求的不是单纯意义上的最远点,而是黑点之间的。(也可以理解为在黑点构成的虚树做这道题目)

我们只需稍微改变一下定义即可。我们把直径理解为黑点之间的最长路,中心、类中心的定义跟着变化;要维护的东西(如每个子数内最深点的深度)也跟着把“点”变成“黑点”即可。

问题完美解决,是$O(n)$的算法,他与读入复杂度同阶,非常优秀。

这个算法能够得到100分

其他算法

这题还有很多其他的算法

vfk的树形dp的办法,还看到有人用点分治能$O(n \log n)$做等等……

这是一道一题多解的题目

UOJ Test Round #1 公告

2014-10-23 19:30:32 By ydc

10月26号,星期日晚上7:00~10:00开始公测!

UOJ就要迈出第一步了!欢迎大家来捧场!

由于是公测,目的主要在于测BUG,所以是人民群众喜闻乐见的原题大战

气泡熊在笑

不过不用担心!我觉得我选的题还是蛮好玩的!

为了应景,题目难度、部分分设置都和联赛差不多,对于想要为NOIP准备的同学而言是个不可错过的机会!

赛后我们会有详细的题解。

出题人有 ydc, vfleaking


题目三小时三道题的OI赛制,

难度高仿noip,

大家也不用担心掉rating,

因为这一场是unrated哟,还怕什么!

这是神犇强者展现实力,虐爆全场的时候!

这是大众选手增强信心,迈向未来的时候!

还等什么?来战吧!

有什么问题请在下面留言。


rank前5分别是

  1. matthew99
  2. bright_sun
  3. qq836793
  4. jcvb
  5. Claris

恭喜他们!

此外 latrommIClaris 同分,只是罚时相对较高。

接下来是喜闻乐见的题解时间

共 9 篇博客