silver組：
比賽那天感冒，第一題就弄暈了，現在題解出來了，補上吧~~
暫時只有第一題的：
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
題目看起來挺復雜，其實主要是求出各個turn處的最大速度，分析得到每個turn的最大速度需要滿足三個條件， M_i = min (S_i , t_i – t_{i-1} + M_{i-1} , S_k + t_k – t_i [for all k > i ] )
因此處理每一個turn都要查詢N個turn N*N的復雜度顯然對于大數據要TLE的
逆向思考，如果我們反過來考慮，對于每一個之后的turn來說 如：i 如果他最大速度為 m_i
那么 在turn i-1處，他不能超過的最大速度 m_{i-1} = min(S_i,m_i+t_i – t_{i-1});這樣成功的把后面兩個限制轉換為逆推的結果而不是向后查詢
剩下的問題便是如果知道兩個turn之間距離，以及turn的速度最大值，如何求出之間的最大值，畫圖顯然可以得到一種算式 maxspeed = min(s1,s2) + (dist2-dist1+abs(s1-s2))/2;
或者 maxspeed = max(s1,s2) + (dist2 – dist1 – abs(s1-s2))/2;
注意在開頭和結尾加入虛擬的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個月后的修改線-----------------------------------------------------------------
第一個復習周末 ，先看的這道題，過了這么久果然又杯具的不會了~~之前的解釋寫的有些模糊。
首先，如果要想達到最快速度，那么只需要求得每個turn 能夠達到的最快速度即可~
所以題目編程求每個turn能達到的最快速度了。首先得到簡單的式子，也就是上面的min{1,2,3}，第一個條件決定在這個turn我們可以加速達到的最大速度，后兩個條件為了防止滑的過快，減不下來不能通過自己以及以后的turn。按這種算法，我們必須對每一個turn遍歷之后的turn，很沒有效率。后面兩個條件是為了防止在turn處滑的過快~~那么每一個m_i 只需要滿足 min(S_i,m_{i+1}+t[i+1]-t[i]);只要這樣，就可以保證雪橇可以減速以通過下一個turn。顯然最后一個turn的 m_i 就是他的s_i，這樣遞推回去就能得到一組slowdown值，然后利用前面的式子 up[i]=min{m_i[i],up[i-1]+lenth};正向推回去就可以得到每一個turn的maxspeed。至于最大speed的算法上面已經給出了~
------------------希望下次可以直接做出來，不要再忘了。。。。-------------