UOJ Logo ydc的博客

博客

标签

#4 NOI2014 消除游戏题解

2019-05-11 17:32:02 By ydc

求问uoj有哪些表情能用啊?有没有一个表情包的list呢?

虽然知道版刷uoj是不现实的(何况对于一个只能业余时间来陶冶情操的人),但还是看到#4空着有点不爽,毕竟这里是个打游戏总想着集全成就的强迫症患者。

这是我当年进队的那场NOI,考完后很快就把几道传统题做了,但这题一直没做。其实搞OI时,我从来就没管过提答题,觉得费时费力(事实上做这道应该不算太难的提答题就花了我好多时间orz)。

也是退役了之后心态变得不那么功利了,单纯为觉得好玩而刷。(划掉)

网上翻了一圈也没翻到较详细的题解(更别说代码),就来写个题解造福一波。(还会放代码)

解锁成就:AC提答题!

测试点一

观察发现,正好有一个超长回文数和一个超大质数构成,手玩!

测试点十

找规律了好久,感觉并不擅长提答。从输入可以猜出想让你回文串干掉所有数。发现第一行是回文,但二三行并不是。发现每9列会进行一次循环。

所以其实做法就是,如果我能把每个$3 \times 9$给干掉,由于循环节的特性,所以就能一次性干完了。

然后试图干掉前9列的27个数。分成9个$3 \times 3$的块,块与块构成回文。

最关键的是,从左上角(1,1)出发,按照RDLDRRUUR这个策略,会让每个块构成一个回文。

所以事实上……你不断重复这个策略。。。就做完了!

测试点二

随机,每次随机一个质数或回文串,多次得分取最高。

一个优化是串的开头,本来是随的,效果不好,改成了第一个非-1元。可能是这样更容易消完吧。

测试点三,测试点四

这两个点就是要你搜质数。

我们发现事实上测试点二还能更进一步,质数的密度是很高的$1/\ln n$。我们即使强行要求每个数必须是长为18,从一个点出发,上下左右4个方向走,将会有几乎$4^18$个数字串可以选,而这当中几乎肯定有质数。

所以你写个DFS,很快能搜完一个“由500个18位质数”组成的解。

测试点五

数据范围不大,暴力搜!

搜的结果发现并没有找到既是质数又回文的8位串。

由于数据范围实在不大,所以我每次搜数字串的流程如下:每次枚举串长(从8到2),找到长度等于该串长的分值最高串(程序同时考虑了质数与回文的情况,尽管好像回文没有用)。这个枚举是真纯暴力,就是起点是枚举的,然后枚举$4^8$种情况。最后在所有情况中取max。

交了一发这个点9分,但是我已经纯暴力了。想了想发现,我现在是“若目前最优值小于当前答案,更新解,否则不更新”。我改为“否则,若相等则以0.5的概率更新解”,然后外面套了10次迭代,于是10分了。

测试点六

接下来就是搜回文串了。

这个点很水,直接搜。

测试点七

我用6的程序怎么搜都搜不出来,绝望了一阵。

睡了一觉之后做了点小改动。

随机起点变为将起点设为中心,700+变900+。

然后让两端分别按逆序枚举(比如一个往左另一个就先试着往右)

结果秒出。。。卧槽

测试点八

关键在于方向的搜索顺序!

奇技淫巧:奇数轮顺着搜,偶数轮逆着搜。

然后我本来是,随机一个中心点,以他为中心搜若干条回文串。这个“若干”本来定的较大。

经实践发现,定很大和定个10000,结果差不多。而将这个“若干”改为10000后,枚举一个中心点的时间就很低了——低到可以爆枚所有中心点。

实践又发现,枚举前10行作为中心点后,程序已经能跑出很优的解了。

测试点九

虽然$K=5$,但只要和之前一样,找一个超长回文串就很优了。

观察发现,他“几乎”是对称的。打印一下发现100000个数里仅仅36个不对称的数。

我们将不对称的数置为0,将问题转化为,从左侧某个点出发,找一条全不为0的以第64列为终点的尽可能长的路径,然后翻倍——如果能经过所有点那就太好了。

于是试图去弄一个加了剪枝的求哈密顿路径的算法,没啥进展。

最后我启发式的想出这么一个策略:

从(1,1)出发,右,下,左,下,右,下,左,下……直到最后一行,右,右,现在到了(n,3)。然后右,上,左,上,右,上,左,上……直到第一行,然后右,右,如此循环。“尽可能”地按这个策略。

什么叫“尽可能”的呢?就是DFS时,搜索的最优先顺序是这样的即可。接下来“不能这么做的”,就会自动被回溯过程中弄掉。

于是我将DFS的规则定义如下:假设列%2=0,除了在顶端底端外不能往右;假设列%2=1,他就不允许往左。

        int tmp[6],cand=0;
        if(y%2==0)
        {
            if(x==n&&y%4==2)
                tmp[++cand]=DIR_R;
            if(x==1&&y%4==0)
                tmp[++cand]=DIR_R;
            tmp[++cand]=DIR_L;
            tmp[++cand]=DIR_D;
            tmp[++cand]=DIR_U;
        }
        else
        {
            tmp[++cand]=DIR_R;
            tmp[++cand]=DIR_D;
            tmp[++cand]=DIR_U;
        }
      for(int i=1;i<=cand;++i)
        {
            int px=x+movex[tmp[i]],py=y+movey[tmp[i]];
            if(check(px,py))
                DFS(px,py,lcor,rcor);
        }

大家可以根据上述代码理解一下~然后发现很快就出了个非常优的解(不确定有没有经过所有非对称数,反正能拿10分就对了!)

代码可以参见这里

想回来了

2019-05-02 21:25:16 By ydc

大家好,这里是想必已经没有人记得的ydc。

OI时光真的是我高中生涯里一段难忘的时光。即使当年的记忆早已尘封在记忆深处,可当我又一次打开uoj时,当我偶尔与当年的朋友一起吃个饭时,当偶尔有人来问我oi题时,这些记忆都会涌上心头。

如今我已经大四了,大学期间没有任何ACM的经验,科研压力愈发变大,这个时候回来刷题已经成为完完全全没有任何利益的行为。

但是A题还是那么好玩啊!

不需要考虑考试成绩,不需要考虑保送降分,只是单纯地点开一个题来思考有空时来写写代码(准确的说是发现不会做被虐然后看题解)

偶尔上博客写写吐槽,回忆一下往昔,想想当初uoj还只有1,2道题的情形以及那段日子里我的生活

感觉在接下来五年的博士生涯或者更久远的人生里偶尔过点这样的生活似乎很不错

今晚刷了一波UER1,虽然这场比赛当初是我办的,但我只出了#12(最水的那道送分题233)。点开DZY Loves Graph,发现被狠狠地虐了(捂脸)

以后将不定期写点题解和近况吐槽~

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)$做等等……

这是一道一题多解的题目

共 11 篇博客