noip模拟测试84

考试过程:先读题,觉得开题顺序1,2,3,4,首先是T1,我刚开始觉得是二分+主席树,刚开始觉得这没什么问题,就开打。
打完后一测大样例发现有两个地方不对,经过调试后发现我这种思路并不能满足单调性,最后改成了暴力,但是因为数组开小了,导致\(70pts ->40pts\),跟10分钟打的暴力一个分。
然后是T2,我觉得是最短路,但是我遇到了两个问题:
1.如何解决当前是二进制下第几位。
2.如何存储这么大的数,并且能够比较大小。
在考场上我想了半天没有什么好的办法,就用了一个数组存起来,每次按位比较。但是小样例过了,大样例就有些数不对了,我没调出来。
T3,一道期望题,没什么思路,就打了个暴力走了。
T4 ,没有多少时间了,而且题目看着比较毒瘤,我就没做。

考试总结:1.想到可能是正解的思路后要先思考,验证正确性,不要等打完了后才发现是假的。
2.对于已有的想法可以适当发散思路,思考如何更好地利用这个想法去解题。

T1 宝藏

思路:主席树+双指针。
显然,对于一个中位数是否合法的判定,我们可以利用主席树\(o(logn)\)进行判定。
接下来我们考虑如何求出所有的情况。
我们可以将\(w\)从小到大排序,然后从最大值开始枚举中位数\(i\),从\(1\)开始枚举长度\(j\),显然,如果小的长度无法满足,那么大的一定也无法满足,这样我们就可以利用这个指针进行计算了。
时间复杂度\(o(n\times log(n))\)
代码如下:

T2 寻找道路

首先解决一个问题:如何知道当前是二进制下的第几位。
考虑问题的本质,我们想知道这是二进制下第几位的目的就是为了计算答案,那么我们可以反过来计算,每次将\(ans\times 2\),再考虑是否需要加一即可。
思路:因为前导零不会产生贡献,所以我们可以将\(1\)号店只走\(0\)边能到达的点都缩成一个点。
接下来我们要让走过的路径尽可能少,并最小化字典序。
那么我们可以利用一个类似于拓扑排序的思想,每次从队列里拿出所有距离相同并且答案相同的点,先遍历\(0\)边,后遍历\(1\)边更新答案。、
时间复杂度\(o(n+m)\)
代码如下:

T3 猪国杀

咕了

T4 数树

咕了

上一篇:计算机网络通信协议和七层模型


下一篇:AI绘制一个英语图书插画教程