原文放在我的uoj博客上,既然新开了blog,那就移过来了

这是这篇文章的第三次转移,那肯定是我觉得这篇文章非常有纪念意义

玩具谜题(toy)

送分题。没有什么好说的。

直接按照题目的要求模拟即可。

标准的noip式day1T1。

 

反思

这道题目没有什么失误,时间上也只花费了5min-。由于这类题目没法对拍,肉眼检查了一遍,还算正常。

天天爱跑步(running)

首先考虑暴力80分的做法(代码只提供60分的,原因下文会说),下面仔细的分解每一部分的点:

  1. (10):每个人的终点就是起点,那么直接对\(W_j=0\)的点,计算出现了几次即可。
  2. (10):所有的\(W_j=0\),计算所有人的起点出现了几次即可。
  3. (25):直接对于每一个人的路线,暴力\(LCA\),累加得到答案。
  4. (15):树退化成链,变成了区间操作。我们把跑的路径分成两类,即从小到大一类,从大到小一类。然后,我们扫一遍n,对当前位置i,正好经过的区间左边界为i的格式加入d[i],然后把右边界为i的对应的左边界x的\(d[x]-1\),那么显然对于的当前处理到的位置i,答案就是\(d[i-W_i]\)和\(d[i+W_i]\),那么,前扫一遍后扫一遍即可。
  5. (20):以1结点为根建树,假设1结点的深度为0,结点i的深度为\(d[i]\),那么只有当\(d[i]=W_j\)的时候,这个结点的答案才不为0,而这种时候,他的答案就是所有能够通过这个结点的路径数量,那么,我们每次把路径的右端点的标记+1,这个结点的答案就是他所有孩子的权值和。
  6. (20):终点为1的。那么只存在从下到上上升的一部分,是下文正解的一部分,这里不赘述,代码也不提供。

那么下面来分析一下正解吧。

首先,对于一个人跑步的路径\((x,y)\),我们把它分成两部分:\((x,lca(x,y))\)和\((lca(x,y),y)\)。

如果一个点i在从x到\(lca(x,y)\)的路径可以检测到的话,那么就有\(d[i]+w[i]=d[x]\)。

如果一个点i在从\(lca(x,y)\)到y的路径上可以检测到的话,那么就有\(d[i]-w[i]=d[y]-len(x,y)\)。

我们可以直接使用树剖来解决这类树上链的问题,但也可以考虑直接在树上标记,然后dfs解决:从x到y的一个路径,在x中\(a[d[x]]\)加一个,当dfs把\(lca(x,y)\)退栈的时候,x的影响就没有了,那么把\(a[d[x]]\)减掉。 在\(lca(x,y)\)那里需要把一个\(b[d[y]]\)加进来,在y出栈后,就把\(b[d[y]]\)减掉。

每次\(ans[x]\)的答案就是子树\(a[d[x]+w[x]]+b[d[x]-w[x]]\)的数量。

但我们发现,这样做在树退化成链的时候会重复,我们需要特判一下,起点和终点相同的时候也会重复,也需要特判。

60分代码

满分代码

反思

这道题目主要的失误在于考场上时间安排的失误。

刚开始觉得,这题是D1T2,于是1h+都在思考正解,然后,弃疗去看T3,发现T3可做,然后T3煞笔一样的数据范围看错,边的输入了m,然后一直过不了大样例,调了整整1h+,这直接导致了T2来不及。

因为考场上,我想不出T2的正解,而从上面的分析就可以看出,T2的暴力是需要花很多时间的,时间花的越多,分数就越高。但我把时间浪费在了T3的调试上,T2的硬刚上。这都是考场上策略的失误。

说到底还是平时缺少训练,代码能力差,应考能力差的表现。

换教室(classroom)

首先是最短路,floyd即可。

暴力出奇迹,直接爆搜,80+。

那么对于正解,就是数学、dp相关的内容。

我们用\(f[i][j][k]\)表示前i节课,换掉j节课,其中第i节课(即最后一节)换或者不换(k=0
表示换,k=1表示不换)的期望。

然后考虑转移,由于期望可加,那么,我们只要一次用概率乘上当前情况的最短路即可。

但还要注意一些细节,题面中也说明了:1、有重边(56分);2、有自环(25分)。

注意,uoj的hack数据中,有\(m>n\)的情况,题目中也确实没有保证\(m<\le n\),所以也是一个细节。

反思

可能是期望dp的题目第一次进入联赛吧,出题人给了很多的暴力分,暴力可以到80+。

这道题目的失分主要在于三个点:

1、数据范围看错,比赛的时候浪费了一个小时(边的读入少了);也是因为这个,导致最短路选了SPFA,于是TLE(30分)。

2、最后选取答案的时候,没有去掉一类情况(f[n][n][0])(5分)。

3、没有考虑自环的情况(20分)。

说了这么多,总之就是这道题目上的失误很多。平时训练很多题目注重于思考而疏于代码的练习,这是以后需要重点关注的。平时训练的时候很多题目来源于acm,Wa了以后会多次提交,而导致在比赛的时候,看错了数据范围,是个人平时做题习惯不好造成的。

组合数问题(problem)

基础的数学知识是\(C_n^m\)对应杨辉三角中的第\(n\)行\(m\)列的数。

那么,直接递推就可以得出整个杨辉三角。而对于能否被k整除的问题,直接\(%k\)即可。

反思

失误最严重的一道题目。

这道题目对于我而言,或者说对于所有的选手而言都理应是一道送分题。

从上面的题解也可以看出。

但是我在考场上的做法是判断\(C_n^m\)这个组合数的因子中有多少个k,然后的是递推,但是这样做的话,是有巨大的bug的:例如,当$k=6$的时候,因子中没有出现6,但出现了2和3,是能被6整除的。

所以导致了我在k为合数的时候,全部Wa,因此失掉了60分!

这是严重的失误,但失误绝对是因为平时训练时的习惯造成的。

当时在考场上,这道题目我还和暴力拍上了,很放心,当然,那么暴力的因子也是这么处理的,所以也错了。

本是想着万一这道题目出了什么岔子,暴力是要交上去的,所以也加了些许优化。

所以以后用来对拍的暴力,还是要用最保险的打法,不然,非常容易狗带(记得去年是因为对拍以后交错程序,也是Day2的T1)。

一次又一次的教训!一定要警示!

蚯蚓(earthworm)

直接调用STL中的\(priority\_queue\),然后对于q,我们只需要在每次处理以后,当前处理的-q放入即可。期望得分65。

考虑q=0的做法。

我们只需要三个队列来处理。

一个队列存放没有切过的蚯蚓(已经进行过排序);

一个队列存放切过的前半段蚯蚓,另一个队列存放切过的后半段蚯蚓,这样的话,我们一定可以保证三个队列都是有序的,那么,我们每次要切的蚯蚓,只需要比较三个队列的头即可。这样的时间复杂度是\(O(nlogn+m)\)。

在这个基础上继续思考。

我们发现,由于每次+q,队列中所有元素的相对位置是不会发生变化的。

也就是说,我们可以用另外的一个变量在处理q(这个和用STL处理的时候类似),那么对于当前处理的,我们只要放进队里的时候-Q(表示当前总的q)即可,因为当前的放进的那个队列中一定是最小的,又由于当前次没有+q,只会更小,所以不会影响总体的顺序。

那么,复杂度类似的,仍然是\(O(nlogn+m)\)。

最后还有一个细节问题,是官网数据中没有涉及的,但UOJ的hack中有:

当u、v接近1000000000的时候,单纯的double处理会出现精度问题,为了避免这个问题,我们用\(*u/v\)代替\(*p\)来避免,但要注意开\(long long\)

90分程序

满分代码

 

反思

总的来说,这道题目的算法并不是很难想到。

先前的Noip题中也有一道合并果子,因为可以直接用优先队列解,便没有深究。而其实,合并果子是有线性的做法的,也就是和上面所述的三个队列类似。

那么,这道题目就只能归结于平时做题的时候缺少思考,依赖于blog中的题解,没有独立思考的过程,没有去想更有的解法和策略。

这道题目,实际在考场的中的得分仅有65分,应该说,不考虑上述的情况,在考场上,应该是可以写出90分的算法的。而当时是觉得打个优先队列也有这么多分,就草草了事,去做T3了,而后来的话,似乎忘了这么一回事,一直在拍,在检查,没有想着去多拿一点分(结果连T1都跪了)。

愤怒的小鸟(angrybirds)

应该算是一道比较基础的状态压缩dp。

首先\(O(n^2)\)预处理。

表示确定两个点以后,我们可以求出抛物线的解析式,然后根据这个解析式求得有多少个点符合要求。

然后就是dp,f[i]表示状态为i(i转换为2进制以后,0表示不可行,1表示可行)最少需要多少次。

暴力背包转移即可。

这样的复杂度是\(O(n^2*2^n)\),提出一种优化:

每次,对于一个状态,我们一定会将最前面的一个不可行的位置变为可行(因为最后一定要变为全部可行),那么,我们不需要每次都寻找\(n^2\)次,只需要对于当前的最前面一个不可行的位置找即可,这样,总的复杂度就变成了\(O(n*2^n)\),但实际上,官方数据不需要优化。

 

反思

这道题目上的失误主要在于精度处理上的问题。

在联赛以前一直有这么一个心态:联赛肯定不会很难,所以在平时的训练中也会刻意的去回避这一类要处理精度的问题。

所以说,心态和策略的错误是这道题目的最大失误。

对于精度问题,犯了一下两个错误:

1、精度的问题,考虑的太少,我的eps只写了1e-4。看到成绩以后,发现这道题目拿了90分,一直以为是TLE。而在拿到官方数据以后,在发现是Wa,然后我把eps改成了1e-10,就过了。
2、在判断a<0的时候,忽略了精度问题(虽然不考虑也能A掉官方数据),应该改为a<-eps。

此类精度问题,在后面的训练中已经是不可回避的问题了,一定多做此类题目,增加处理精度的经验(记得在ZJOI2016上有过这样一份讲稿,要再去学习一下)。

总结

先说说今年的题目。

对这场Noip题目总的感觉是题目的顺序编排存在一定不合理性。

对于题目本身,Noip2016引入了从未有过的期望dp,对数据结构的考察在淡化。相对前几年,今年的题目更侧重与思考,减少了代码量。这应该也是以后算法竞赛的趋势吧。

但让我个人比较不爽的是,Noip对暴力选手过于照顾。尤其体现在D1T3上,暴力可以拿80分,这会让联赛没有区分度,让打残期望dp的选手(比如我)成为了名副其实的暴力选手,甚至分数还不如暴力选手。当然,对于D1T2这样,暴力可以有80分的题目,我个人还是比较提倡的。因为80分来自不同的部分,这样会体现出选手的不同能力水平。

扯了那么多,有什么用。

还是说说自己吧。

这场Noip考得非常差。

先前公开了一篇Noip酱油记(空间日志),迟迟没有公开的原因就是在测了余姚中学的数据以后,已经意识到了问题的严重性。

考完两场考试,回来的车上,估了一下自己的分数(即那篇酱油记中所述),怎么算都不会低于450,觉得不管怎样,卡个一等应该没什么大问题。也不会对后面的OI路造成非常大的影响。

但余姚中学的数据,我的测试结果是339,最终ccf的测试结果是396。

这是一个极差的分数,和我去年滚粗的成绩差不多。

简单地来说,和估分的主要差距在于D1T3最短路弄错,丢24分;D2T1出现制杖性错误,丢60分,这样加上去,和估分差不多。

成绩出来后,一度想过放弃,想过退役。但说实话,OI这七年一路走过来实则不易。

小学五年级下半年,宁波市比赛初赛狗带,六年级上半年慈溪市初赛狗带。当时还以初赛不好、复赛好为理由搪塞自己和父母,现在想来真是可笑至极(想想自己,也是从小学五年级开始学的,到了现在还不如那些初中开始的)。

初中的OI表面上看起来很顺利,初一二等,初二全省20,初三全省第一,一路上升。但其实背后,有非常惨烈的现实:难度相对比较高的宁波市比赛,除了初三获得二等第一以外,其余两年全部狗带。

现在看来,是Noip普及组的成绩使自己自负了,使自己觉得已经有了相当的OI水平。

那时候,除了偶尔做几道USACO,其余基本全是水水题。那时候根本不是道什么Codeforces,就连知道的poj也觉得是英文题而望而却步。初中的三年,浪费了。到了高中,本身课业繁忙,留给OI的时间没有初中那么充裕了,也是到了这时候,我才意识到初中都干什么去了。

但现在,到了这个时候,说这些过去的都是徒劳。

现在是12月中旬,Noip后的一个月。前一个月又是浑浑噩噩的过去了。

现在最主要的是要调整好自己的心态,找到自己的问题所在。为什么联赛后连续两点狗带,这不是运气的问题。这一定是自己实力的问题,平时的代码量不够,平时的训练不够,应考能力不强,临场发挥不好等等都是问题所在。

既然觉得自己到了这时候不应该放弃,上天也眷顾我送了一个一等。

我会以这次Noip为契机,更加努力的奋斗。

义无反顾的继续走下去。不管还要经历多少困苦,不管最后的结局如何。

自己选择的路,怎能轻言放弃,就算跪着也要走下去。

猛然忆起上林OJ曾经滚动的一句话:静心思考,反思过去


发表评论

电子邮件地址不会被公开。 必填项已用*标注