隐藏
Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

简化思考

本题如果去掉食人鱼的限制,就变成了一个裸的邻接矩阵k次幂,用矩阵快速幂乱搞一通即可。


初步思想

如果没有限制,能不能将这个如果变成现实呢?
我们可以考虑去掉每个食人鱼的影响,即食人鱼到那里就把对应的边去掉,然后再做快速幂。
但是这个做法是与时间有关的,对于每一个时间我们都要重新构造邻接矩阵,这样做错的离谱,构造完了根本就不关快速幂的事了。

阅读全文 »

判断条件

对于三元组$\begin{pmatrix} y && z && x \end{pmatrix} ,z\in(y,x)$,满足y>=x&&x>=z,且$[y,x]$所有元素已知,则输出true,若有未知输出maybe,若不满足输出false

阅读全文 »

初步想法

由题,我们可以想出一种显然的宽搜算法。
我们可以使用四元组$(ex,ey,x,y)$唯一表示题目的状态。
$(ex,ey)$表示空格所在坐标
$(x,y)$表示点所在坐标
那么我们就可以得到$O(q(n\times m)^2)$的搜索算法。

阅读全文 »

题目大意

给一段区间,求出区间内的前k大连续和之和(每一段连续和长度满足>=l、<=r)


初步思想

对于k大k小总结本$P2^5+1$有一系列处理方法,其中我们考虑可行的有:

阅读全文 »

题目大意

给一个有$n$个结点的图,每个点与其前$k$个点有边相连,统计该图的生成树个数。


数据分析

若直接使用提示的做法,时间复杂度$O(n!\times n)$,这样可以得到40分。
若使用高斯消元/LU分解的方法,时间复杂度$O(n^3)$,这样可以得到60分。
观察题目,我们发现$k$很小,那么矩阵中有很多元素为0,因此我们可以在高斯消元的时候对0值不作处理,这样时间复杂度是$O(n^2k)$,可以通过70分的数据。
本题能拿到70分已经很不错了。

阅读全文 »

题目大意

有一棵由圆台组成的树,平行光线以∠$\alpha$射向这棵树,求地上影子的面积。

题目大意2

求本人心理阴影面积。
记得这道题是从初一开始就膜的神题,今天总算正式A了。

阅读全文 »