3.5测试总结
3.10测试总结

2016.3.8测试总结

YYY posted @ 2016年3月08日 22:49 in OI相关 with tags DP 图论 弹幕游戏 , 552 阅读
_THIS_IS_START_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个子弹,画个毛啊,还要用不同颜色)
第十个点,在某两个点之间来回走,有若干个圆形的子弹作为障碍物挡在路上。如果将这些障碍物的图画出来,可以发现中间只有一条通路能过去,“然后就是考验你计算几何的时间了”(我想阿出题人了)
----------------------------------------------------
_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter