題目分類
|
| Y2K Accounting Bug |
最優(yōu)局面（math） |
| Airline Hub |
球面距離（geometry） |
| Snakes |
圖論，聯(lián)通性 |
| Snap |
模擬
|
| Steps |
分析 (math)
|
Y2K Accounting Bug ：
一年12個(gè)月中任意連續(xù)的5個(gè)月都是赤字，每月要么盈利 s ，要么虧蝕 d， 求這一年可能的最大盈利
對(duì)于一個(gè)給定的 s 和 d，我們只要讓虧損的月份盡量少，而實(shí)際上存在固定的最優(yōu)局面
分類討論每種情況的最優(yōu)局面， 一共有五種（O表示虧 。表示盈）
。。。。O虧，則 。。。。O。。O。。。。為最優(yōu)局面
。。。OO虧，則 。。。OO。。OO。。。為最優(yōu)局面
。。OOO虧，則 。。OOO。。OOO。。為最優(yōu)局面
。OOOO虧，則 。OOOOO。OOOO。為最優(yōu)局面
OOOOO虧， 必虧
Airline Hub ：
0ms的不知道怎么做的，我是暴力做法500ms
這里只提一下球面距的求解方法， 先將經(jīng)緯度化成角度，再把角度化成直角坐標(biāo)，用余弦公式計(jì)算兩半徑夾角q， 再求出弧長 l = r*q；
在計(jì)算角度時(shí)， 中間過程既乘了 r^2 又 除了 r^2所以約去了
附上代碼
1 double dis(double la1, double lo1, double la2, double lo2， double r)
2 //la1 lo1為第一個(gè)點(diǎn)的緯度，經(jīng)度
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]); //本應(yīng)該乘于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); //本應(yīng)該除于r*r
17 }
18
Snakes：
題目意思就不說了，這里主要說一下做法！
我們把蛇連同它的攻擊范圍看做一個(gè)圓，再把圓抽象成一個(gè)點(diǎn)！點(diǎn)與點(diǎn)之間有邊連接僅當(dāng)兩個(gè)點(diǎn)代表的圓有公共面積！然后我們?cè)诎焉线吔绾拖逻吔绺鞒橄蟪梢粋€(gè)點(diǎn)(S和T)，同樣上邊界與點(diǎn)之間有邊連接僅當(dāng)點(diǎn)代表的圓與上邊界相交，同理，可得下邊界與點(diǎn)之間的邊關(guān)系！
這樣處理以后如果有從左到右的路徑，當(dāng)且僅當(dāng)不存在S到T通路！只要深搜或者廣搜即可！但是題目還要我們求出左右的坐標(biāo)，只需確定縱坐標(biāo)即可，而且縱坐標(biāo)要最大！所以我們考慮與S連通的每一個(gè)點(diǎn)，如果該點(diǎn)代表的圓與左邊界有交點(diǎn)，那么如果從這個(gè)交點(diǎn)上面走一定走不過去，所以我們更新左邊的縱坐標(biāo)到這個(gè)交點(diǎn)處，對(duì)所有的圓都這樣處理，即可確定左邊縱坐標(biāo)，右邊的同理可求！而且這一步可以在求連通的時(shí)候隨便求出，我們只需從S出發(fā)，一直搜即可！
Snap：
按照題意模擬（隨機(jī)數(shù)取
rand()/99%2）。注意贏來的牌是加在上面，不是加在下面的。
Steps ：
這里首先能發(fā)現(xiàn) 加速的次數(shù) == 減速的次數(shù)，也就是說如果不考慮勻速部分，并且最大速度為n，可以算出這種情況下能走的距離 s = n^2;
再考慮勻速部分, 設(shè)dis為要求兩點(diǎn)距離
顯然我需要找到一個(gè)n滿足 n*n<= dis < (n+1)*(n+1)，最大速度一定為 n ，多余的部分即 leave = dis - n*n;
leave /n 部分用最大速度勻速跑，leave % n 部分之需要中途勻速一秒就好