题目分类
|
| Y2K Accounting Bug |
最优局面（math） |
| Airline Hub |
球面距离（geometry） |
| Snakes |
图论，联通性 |
| Snap |
模拟
|
| Steps |
分析 (math)
|
Y2K Accounting Bug ：
一年12个月中任意连续的5个月都是赤字，每月要么盈利 s ，要么亏蚀 d， 求这一年可能的最大盈利
对于一个给定的 s 和 d，我们只要让亏损的月份尽量少，而实际上存在固定的最优局面
分类讨论每种情况的最优局面， 一共有五种（O表示亏 。表示盈）
。。。。O亏，则 。。。。O。。O。。。。为最优局面
。。。OO亏，则 。。。OO。。OO。。。为最优局面
。。OOO亏，则 。。OOO。。OOO。。为最优局面
。OOOO亏，则 。OOOOO。OOOO。为最优局面
OOOOO亏， 必亏
Airline Hub ：
0ms的不知道怎么做的，我是暴力做法500ms
这里只提一下球面距的求解方法， 先将经纬度化成角度，再把角度化成直角坐标，用余弦公式计算两半径夹角q， 再求出弧长 l = r*q；
在计算角度时， 中间过程既乘了 r^2 又 除了 r^2所以约去了
附上代码
1 double dis(double la1, double lo1, double la2, double lo2， double r)
2 //la1 lo1为第一个点的纬度，经度
3 {
4 point p[2];
5 double ang[2][2];
6 double la[2]={la1, la2}, lo[2]={lo1, lo2};
7 int i;
8 for(i = 0; i < 2; i++)
9 {
10 ang[i][0]=la[i]/180*pi;
11 ang[i][1]=lo[i]/180*pi;
12 p[i].z=sin(ang[i][0]); //本应该乘于r
13 p[i].x=cos(ang[i][0])*cos(ang[i][1]);
14 p[i].y=cos(ang[i][0])*sin(ang[i][1]);
15 }
16 return r * acos(p[0].x*p[1].x+p[0].y*p[1].y+p[0].z*p[1].z); //本应该除于r*r
17 }
18
Snakes：
题目意思就不说了，这里主要说一下做法！
我们把蛇连同它的攻击范围看做一个圆，再把圆抽象成一个点！点与点之间有边连接仅当两个点代表的圆有公共面积！然后我们在把上边界和下边界各抽象成一个点(S和T)，同样上边界与点之间有边连接仅当点代表的圆与上边界相交，同理，可得下边界与点之间的边关系！
这样处理以后如果有从左到右的路径，当且仅当不存在S到T通路！只要深搜或者广搜即可！但是题目还要我们求出左右的坐标，只需确定纵坐标即可，而且纵坐标要最大！所以我们考虑与S连通的每一个点，如果该点代表的圆与左边界有交点，那么如果从这个交点上面走一定走不过去，所以我们更新左边的纵坐标到这个交点处，对所有的圆都这样处理，即可确定左边纵坐标，右边的同理可求！而且这一步可以在求连通的时候随便求出，我们只需从S出发，一直搜即可！
Snap：
按照题意模拟（随机数取
rand()/99%2）。注意赢来的牌是加在上面，不是加在下面的。
Steps ：
这里首先能发现 加速的次数 == 减速的次数，也就是说如果不考虑匀速部分，并且最大速度为n，可以算出这种情况下能走的距离 s = n^2;
再考虑匀速部分, 设dis为要求两点距离
显然我需要找到一个n满足 n*n<= dis < (n+1)*(n+1)，最大速度一定为 n ，多余的部分即 leave = dis - n*n;
leave /n 部分用最大速度匀速跑，leave % n 部分之需要中途匀速一秒就好