silver組：
比賽那天感冒，第一題就弄暈了，現(xiàn)在題解出來(lái)了，補(bǔ)上吧~~
暫時(shí)只有第一題的：
Problem 6: Bobsledding [Brian Jacokes, 2009]
Bessie has entered a bobsled competition because she hopes her hefty
weight will give her an advantage over the L meter course (2 <= L
<= 1,000,000,000).
Bessie will push off the starting line at 1 meter per second, but
her speed can change while she rides along the course. Near the
middle of every meter Bessie travels, she can change her speed
either by using gravity to accelerate by one meter per second or
by braking to stay at the same speed or decrease her speed by one
meter per second.
Naturally, Bessie must negotiate N (1 <= N <= 100,000) turns on the
way down the hill. Turn i is located T_i meters from the course
start (1 <= T_i <= L-1), and she must be enter the corner meter at
a speed of at most S_i meters per second (1 <= S_i <= 1,000,000,000).
Bessie can cross the finish line at any speed she likes.
Help Bessie learn the fastest speed she can attain without exceeding
the speed limits on the turns.
Consider this course with the meter markers as integers and the
turn speed limits in brackets (e.g., '[3]'):
| 1 2 3 4 5 6 7[3]
|---+---+---+---+---+---+---+
| \
Start + 8
\
+ 9
\
+ 10 +++ 14 (finish)
\ /
11[1] +---+---+
12 13[8]
Below is a chart of Bessie's speeds at the beginning of each meter length
of the course:
Max: 3 1 8
Mtrs: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Spd: 1 2 3 4 5 5 4 3 4 3 2 1 2 3 4
Her maximum speed was 5 near the beginning of meter 4.
PROBLEM NAME: bobsled
INPUT FORMAT:
* Line 1: Two space-separated integers: L and N
* Lines 2..N+1: Line i+1 describes turn i with two space-separated
integers: T_i and S_i
SAMPLE INPUT (file bobsled.in):
14 3
7 3
11 1
13 8
OUTPUT FORMAT:
* Line 1: A single integer, representing the maximum speed which
Bessie can attain between the start and the finish line,
inclusive.
SAMPLE OUTPUT (file bobsled.out):
5
題目看起來(lái)挺復(fù)雜，其實(shí)主要是求出各個(gè)turn處的最大速度，分析得到每個(gè)turn的最大速度需要滿足三個(gè)條件， M_i = min (S_i , t_i – t_{i-1} + M_{i-1} , S_k + t_k – t_i [for all k > i ] )
因此處理每一個(gè)turn都要查詢N個(gè)turn N*N的復(fù)雜度顯然對(duì)于大數(shù)據(jù)要TLE的
逆向思考，如果我們反過(guò)來(lái)考慮，對(duì)于每一個(gè)之后的turn來(lái)說(shuō) 如：i 如果他最大速度為 m_i
那么 在turn i-1處，他不能超過(guò)的最大速度 m_{i-1} = min(S_i,m_i+t_i – t_{i-1});這樣成功的把后面兩個(gè)限制轉(zhuǎn)換為逆推的結(jié)果而不是向后查詢
剩下的問(wèn)題便是如果知道兩個(gè)turn之間距離，以及turn的速度最大值，如何求出之間的最大值，畫(huà)圖顯然可以得到一種算式 maxspeed = min(s1,s2) + (dist2-dist1+abs(s1-s2))/2;
或者 maxspeed = max(s1,s2) + (dist2 – dist1 – abs(s1-s2))/2;
注意在開(kāi)頭和結(jié)尾加入虛擬的turn就可以了
Code Snippet
#define REP(i,n) for( int (i) = 0 ; i < (n) ; ++i)
using namespace std;
int L,N;
struct node{
int dist;
int speed;
};
vector<node> vec;
bool comp(const node& n1,const node& n2){
return n1.dist<n2.dist;
}
vector<int> up,down;
#define inf 98765433
void solve()
{
//freopen("e:\\usaco\\bobsled.11.in","r",stdin);
freopen("bobsled.in","r",stdin);
freopen("bobsled.out","w",stdout);
cin>>L>>N;
vec.resize(N+2); up.resize(N+2,0); down.resize(N+2,0);
vec[0].dist =0;vec[0].speed =1;
vec[N+1].dist =L;vec[N+1].speed=inf;
REP(i,N) scanf("%d %d",&vec[i+1].dist,&vec[i+1].speed);
sort(vec.begin(),vec.end(),comp);
down[N+1] = inf;
for(int i=N;i>0;i--)
down[i] = min(vec[i].speed,vec[i+1].dist-vec[i].dist+down[i+1]);
int maxspeed = 1;up[0]=1;
for(int i=1;i<N+2;i++){
up[i] = min(down[i],up[i-1]+vec[i].dist - vec[i-1].dist);
maxspeed = max(maxspeed,min(up[i],up[i-1])+(vec[i].dist-vec[i-1].dist+abs(up[i]-up[i-1]))/2);
}
cout<<maxspeed<<endl;
}
int main()
{
solve();
return 0;
}
----------------------------------------------3個(gè)月后的修改線-----------------------------------------------------------------
第一個(gè)復(fù)習(xí)周末 ，先看的這道題，過(guò)了這么久果然又杯具的不會(huì)了~~之前的解釋寫(xiě)的有些模糊。
首先，如果要想達(dá)到最快速度，那么只需要求得每個(gè)turn 能夠達(dá)到的最快速度即可~
所以題目編程求每個(gè)turn能達(dá)到的最快速度了。首先得到簡(jiǎn)單的式子，也就是上面的min{1,2,3}，第一個(gè)條件決定在這個(gè)turn我們可以加速達(dá)到的最大速度，后兩個(gè)條件為了防止滑的過(guò)快，減不下來(lái)不能通過(guò)自己以及以后的turn。按這種算法，我們必須對(duì)每一個(gè)turn遍歷之后的turn，很沒(méi)有效率。后面兩個(gè)條件是為了防止在turn處滑的過(guò)快~~那么每一個(gè)m_i 只需要滿足 min(S_i,m_{i+1}+t[i+1]-t[i]);只要這樣，就可以保證雪橇可以減速以通過(guò)下一個(gè)turn。顯然最后一個(gè)turn的 m_i 就是他的s_i，這樣遞推回去就能得到一組slowdown值，然后利用前面的式子 up[i]=min{m_i[i],up[i-1]+lenth};正向推回去就可以得到每一個(gè)turn的maxspeed。至于最大speed的算法上面已經(jīng)給出了~
------------------希望下次可以直接做出來(lái)，不要再忘了。。。。-------------