2016.3.8测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------------
题面大概可以在superoj上找到
----------------------------------------------------
T1:
先说一下我写的65分乱搞吧：
每次找到一个最长的单调不下降或者单调不上升后缀
如果他是单调不上升的，那就next_permutation一下
如果他是单调不下降的，那就算一下后面部分的全排列有多少种
如果小于m，那就令m减去他，然后翻转一下
否则，删去前面部分
这样直到m=0或者序列中只剩一个元素为止
复杂度O(n+m/O(玄学))
哈哈哈哈
----------------------------------------------------
T2:
每一个环相当于是一个限制:
kx+b>=0(k是环上绿色边-红色边个数，b是环上的初始费用之和）
相当于求满足所有限制的x个数
首先考虑下bellman-ford是怎么判负环的:
d[i][j]表示点i，做了最多j次松弛操作的最短路径长度
1~i的路径上有负环当且仅当有d[n][j]<d[n-1][j](这是因为，松弛一次相当于更新了一遍）
首先设f[i][j][k]表示从1到i，最多做了j次松弛操作,绿色边-红色边个数
那么根据上面那个，就有不等式:
min{f[u][n][k] + k*x | k <= m} >= min{f[u][n-1][j] + j*x | j <= m}
这样就得到了x的一个范围
然后用u的范围去更新一下所有u能走到的点的范围
然后就没有了..
----------------------------------------------------
T3:
我发现我不会玩东方了..
没有标准算法，每个点都是有一定规律的
第一个点只要去擦一下所有子弹就行了
第二个点，中间有一个一直不动的很大的点，而这个点主要靠不中弹得分，所以自机只能在四个角落移动，每个时刻四个角落中最多有三个角落有子弹，所以DP一下，f[i][j][k]表示前i秒，现在在角落j，上一次中弹在时刻k的最优答案，暴力转移一下就好
第三个点，所有的子弹排成一个16行的三角形，从上往下子弹的分数递增，DP一下即可，但是最后还要去最后一行擦一个弹才能拿到满分
第四个点，所有子弹排成一个60行的三角形，从上往下子弹的分数递增，DP一下就好
第五个点，所有子弹组成了一棵树，而叶子节点的擦弹得分很高，所以按时间顺序去走这些叶子节点
第六个点，也是一棵树，但是只有1个擦弹得分很高的点，只需要DP一下哪些子树在拿到擦弹得分很高的点之前遍历，哪些在之后遍历，最后还原出来路径就行了
第七个点，子弹都是从一个点发出来的，而且很快很密集，去这个点擦所有子弹就可以了
第八个点，自己一开始在一个矩形的最下面，有一大堆子弹高速飞来，每一个子弹都有一个时刻会到达离直线y=x+1800相当近的地方（鬼才能发现这个啊），只要沿着这条直线走，然后就是一个类似于接馅饼的DP
第九个点，每180秒是一个阶段，每个阶段躲过全部的子弹可以获得200000分。如果把每个阶段里每个子弹的轨迹画出来，那么可以发现中间有位置一定不会被子弹打到。如果画子弹轨迹时按照分数的高低使用不同的颜色，那么可以发现有一个位置周围所有的子弹分数都相当高。然后只要走到那个位置即可（9600个子弹，画个毛啊，还要用不同颜色）
第十个点，在某两个点之间来回走，有若干个圆形的子弹作为障碍物挡在路上。如果将这些障碍物的图画出来，可以发现中间只有一条通路能过去，“然后就是考验你计算几何的时间了”（我想阿出题人了）
----------------------------------------------------
评论 (0)
