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的算法上面已经给出了~
------------------希望下次可以直接做出来，不要再忘了。。。。-------------