1
17
2016
0

Diary of OI

Jan.17th

注:黑粗体为超链接
一道纯物理题……算得蛋疼
 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
double a,v,l,d,w;
int main(){
    a=1.0*IN(),v=1.0*IN(),l=1.0*IN(),d=1.0*IN(),w=1.0*IN();
    if (w>=v||2*a*d<=w*w){
        if (v*v>=2*a*l) return printf("%.15lf\n",sqrt(2*a*l)/a),0;
        else return printf("%.15lf\n",(l-v*v/(2*a))/v+v/a),0;
    }
    else{
        double t=0,pred=v*v/(2*a)+(v*v-w*w)/(2*a);
        if (pred<=d) t+=v/a+(v-w)/a+(d-pred)/v;
        else{
            double v0=sqrt(a*d+w*w/2);
            t+=v0/a+(v0-w)/a;
        }
        double sufd=(v*v-w*w)/(2*a);
        if (sufd<=l-d){
            t+=(l-d-sufd)/v+(v-w)/a;
        }
        else{
            double v0=sqrt(2*a*(l-d)+w*w);
            t+=(v0-w)/a;
        }
        printf("%.15lf\n",t);
    }
}
这题都不会来……人生了无希望
先把这个环从最高的那个山丘上断开变成一条链 这是等价的
然后l数组记录每个点在它左边离它最近的比它高的山丘的编号
r数组记录每个点在它右边离它最近的比他高的山丘的编号
ci记录i到ri之间高度和它一样的山的数量
然后对于每座山丘ci先加到Ans中去
然后左边右边判一下加一加
具体见代码
 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=1e6+5;
int n,Max,pos;
int a[maxn],b[maxn],l[maxn],r[maxn],c[maxn];
int main(){
    n=IN();Max=0;pos=0;
    Rep(i,1,n){
        a[i]=IN();
        if (a[i]>=Max){Max=a[i];pos=i;}
    }
    Rep(i,pos,n) b[i-pos+1]=a[i];
    Rep(i,1,pos-1) b[i+1+n-pos]=a[i];
    b[n+1]=a[pos];
    l[1]=0;
    Rep(i,2,n){
        l[i]=i-1;
        while (l[i]>1&&b[l[i]]<b[i]) l[i]=l[l[i]];
        if (b[i]==b[l[i]]) l[i]=l[l[i]];
    }
    c[n+1]=0;
    Per(i,n,1){
        r[i]=i+1;
        while (r[i]<n+1&&b[r[i]]<b[i]) r[i]=r[r[i]];
        if (b[r[i]]==b[i]){c[i]=c[r[i]]+1;r[i]=r[r[i]];}
    }
    ll Ans=0;
    Rep(i,2,n){
        Ans+=c[i];
        if (b[i]!=Max){
            if (l[i]==1&&r[i]==n+1) Ans++;
            else Ans+=2;
        }
    }
    printf("%I64d\n",Ans);
}

 

Category: Diary | Tags: codeforces | Read Count: 206

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com