JSOI2015 一轮省选 个人题解与小结

时间:2021-05-11 20:59:26

T1:

题目大意:现有一个以1为根节点的树,要求从1开始出发,经过下面的点然后最终要回到根节点。同时除了根节点之外各点均有一个权值(即受益,每个点上的收益只能拿一次,且经过的话必须拿),同时除了根节点外各点均有一个经过次数的限制,要求求出来从根节点出发回到根节点的最终受益总和的最大值,以及这个最大值是否存在多种方式可以做到(单纯的访问顺序不同算一种)

题解:很明显的树状DP,关于每一个节点均转移一下,取最前面的一些(注意出现负数的话不管怎么样直接无视,但是0不要直接扔),然后再取最大的求和即可(建议用一个堆什么的维护,直接蛮干怕TLE,反正我一般直接上左偏树)。接下来就是关于多解的转移了——这里面个人认为有三种情况会出现多解:1.被取到的子节点有多解(这是显然的) 2.在当前点取完后,在被取的点里面存在值为0的点(显然可取可不取对不?) 3.取完点后,发现被取的点的最小值和没被取的点的最大值一样(也就意味着既然可以选这个,也可以选那个) 别的没了,树状DP乱搞搞即可AC

注:此题由于要考虑到一些细节,所以估计大部分人跪在细节上了——所以——对于自己会的题目,好好珍惜吧——毕竟我等蒟蒻能会的省选题不会太多的

个人程序100分(Pascal)

T2:

题目大意:给一个01正方形矩阵,求出最大的正方形子矩阵满足8元对称(4条对称轴)、90度对称(转90度,转180度,转270度均能重合)、4元对称(2条垂直对称轴)、180对称轴(转180度能重合)、简单对称(1条对称轴)的子矩阵变长

题解:额。。这个。。。貌似全场没人成功AC,于是我也花了5分钟写了个O(n^5)的暴力(虽然显然远远达不到,实际数值大概O(n^4)的样子),结果奇迹发生了——70分!!!!(听star神犇说用二分,详细不知道orz OTL)

注:看来伸展树老师(嘿嘿嘿:伸展树 è splay è SPL 有木有!!!)说的很对——大力出奇迹!!!对于这种能写暴力的题目不写白不写(但是显然不可能写了也白写)orz orz orz

个人程序70分(Pascal)

T3:

题目大意:对于一个无向树,先去掉无用点(无用点是指度为2的点,去掉无用点就是指把无用点左右侧的点直接连接到一起,从而无视此无用点),然后判断剩下来的树是不是形态一样(一样这个东西有点类似于判断有机物的同分异构,只是连手型原子都用不着考虑)。

题解:这个嘛,我虽然某种意义上算是AC了,不过其实我的乱搞的——方法如下,首先去干净无用点,然后接下来对于两棵树,首先对比点是不是一样多(显然的),其次是各点的度数得有可能一一对应,然后满足如下条件的话,我用了一个很逗比的方式——对于两棵树,分别剥掉最外层的一层叶子节点(度数为1的点),然后看是不是去掉的一样多,如果不一样直接可以断定为不同;然后接着继续各剥一层,然后看一不一样多,然后同上一层一层来剥,直到剥到裸奔为止,如果每一波剥下来的都一样,那么这两个图就一样(其实我是受化学上异构体判断法的启发——判断一个烷烃是否同构,我们一般实际上都会忽视掉H原子对不?然后实际上这次可能出现更复杂的图,所以为何不可以考虑将剥了一次的碳链再当作完整有机物再剥呢?对不?)虽然正确性我不会证,但是还是混过了JSOI的10组数据(JYY说正解是哈希,貌似有点道理,详细也大概明白点了)

注:这题。。。唉。。。想到了就想哭——难得搞出来一道难题,结果居然逗比——输出格式弄错了,唉。。。否则我270就全省第一了,而且相比210的最高分简直就是狂虐。。。唉。。。逗比毁一生啊。。还是那句话——好好珍惜有想法的题目吧,毕竟不多

个人程序100分(Pascal)(实际上此题爆零,由于输出格式逗比了)

总结:第一轮已经结束,由于本人上一轮NOIP严重逗比的缘故,所以省内排名才30的样子,不过也基本上和上一轮500上下的小伙伴们扳平了,加油——继续努力。同时值得注意的是,我之所以能有好的进步抑或是发挥,和我之前一直觉得自己太弱,一直保持着忧患意识相当有关,希望这次小小的胜利不要打乱我进步的节奏——能阻止我自己的人,只有我自己;能保佑我自己的人,更是只有我自己。最重要的一点是——少逗比,题目千千万万要看清楚,这次写了12kb的正确程序结果最后狗血地死在输出格式上也是醉了,我等蒟蒻会的省选题毕竟有限,还是珍惜吧——其实这次貌似T1能AC(个人觉得较水),T2认真写O(n^5)的暴力(事实证明只要别逗比至少60能拿到),T3这种题这次纯属命大(lqybzx:呵呵逗比了还叫命大? HansBug:TT,不过话说最高分才210我170,rank5,心里也算基本平衡啦么么哒),在接下来两轮中估计也只能水个10-30的暴力。。。就是这样,继续努力,不以物喜不以己悲便是了