1. 首页
  2. 文章中心
  3. NOIP

NOIP2012 开车旅行：SET+倍增

109 阅读 0 评论
我是靠谱客的博主 鲜艳裙子，这篇文章主要介绍NOIP2012 开车旅行：SET+倍增，现在分享给大家，希望可以做个参考。

啊，看到题：字好多。
然后就直接开始码暴力模拟了，觉得可以预处理一下每个点可以到达的最近点和次近点，这样大概就有50分了（然而实际有70分。。我忽略了只能往后走这一点带来的便利，于是每一次都要找一次最近点&次近点= =果然弱啊(。・・)ノ）
暴力的过程写的蛮。。。第一次只骗到15分= =，后来发现了BUG调到35.。就开始在精度这里卡。。。换了几种最后终于有50了。。。【我还存了一次余数除数hh.。。。】
去看了大牛的暴力，突然发现自己忽略了预处理。。。
暴力【50】如下：

复制代码
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ll long long
#define maxn 100010
using namespace std;
const ll inf=1e18;
int n,m;
ll x0;
ll h[maxn];
int vis[maxn];
ll sum[2];
int find(int x,int typ){
    ll minn=inf;int y=0;
    for(int j=1;j<=n;j++){
        if(j<=x || vis[j])continue;
        ll tp=abs(h[j]-h[x]);
        if(minn>tp){
            y=j;minn=tp;
        }
        else if(tp==minn){
            if(h[j]<h[y])y=j;
        }
    }
    if(typ==1)return y;
    int z=0;minn=inf;
    for(int j=1;j<=n;j++){
        if(j<=x || vis[j] || y==j)continue;
        ll tp=abs(h[j]-h[x]);
        if(minn>tp){
            z=j;minn=tp;
        }
        else if(tp==minn){
            if(h[j]<h[z])z=j;
        }
    }
    if(typ==0)return z;
}
void solve(int st,ll limit){
    vis[st]=1;
    int now=0;
    ll tot=0;
    int j=st;vis[st]=1;
    while(1){
        if(now==0){//a
            int k=find(j,0);
            if(k && !vis[k]){
                ll tp=abs(h[k]-h[j]);
                if((tot+tp)>limit)return ;
                j=k;
                sum[0]+=tp;
                tot+=tp;
                vis[j]=1;
                now^=1;//printf("%lld %lld a.[%d]n",tp,tot,j);
            }
            else return ;
        }
        else if(now==1){
            int k=find(j,1);
            if(k && !vis[k]){
                ll tp=abs(h[k]-h[j]);
                if((tot+tp)>limit)return ;
                j=k;
                sum[1]+=tp;
                tot+=tp;
                vis[j]=1;
                now^=1;//printf("%lld %lld b.[%d]n",tp,tot,j);
            }
            else return ;
        }
    }
}
void solve1(ll x0,int ty,int hh){
    if(ty==1){
        ll res=inf;
        int ans;
        ll ans0=1,ans1=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof vis);
            sum[0]=sum[1]=0;
            solve(i,x0);
            ll tp;
            if(sum[1]==0)continue;
            if(ans1==0 && h[ans]<h[i]){
                ans0=sum[0];ans1=sum[1];
                ans=i;
            }
            else if(sum[1] && ((double)ans0/ans1>(double)sum[0]/sum[1] || ((double)sum[1]*ans0==(double)ans1*sum[0] && h[ans]<h[i]))){
                        ans0=sum[0];ans1=sum[1];ans=i;
                    }
        }
        printf("%dn",ans);
    }
    else if(ty==2){
        memset(vis,0,sizeof vis);
        sum[0]=sum[1]=0;
        solve(hh,x0);
        printf("%lld %lldn",sum[0],sum[1]);
    }
}
void file(){
    freopen("drive.in","r",stdin);
    freopen("drive.out","w",stdout);
}
int main(){
//  file();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&h[i]);
    }
    scanf("%lld",&x0);
    solve1(x0,1,0);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int s;
        ll x;
        scanf("%d%lld",&s,&x);
        solve1(x,2,s);
    }
    return 0;
}

70分就不管了，此时已经。。。
然后开始写正解。
顺道学了一下set
怎样的呢？
我们可以把A,B分别走的两步看成一步，就可以用ST了。tt[i][j]表示i节点向后走2^j步到达的点，va[i][j],vb[i][j]分别表示此时a,b走的距离。
用set存每个点，注意是倒着存。把每个点最近点和次近点的标号和距离存下来
之后两个询问直接模拟就好。然后就A了

复制代码
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define maxn 100010
using namespace std;
const ll inf=1e18;
int n,m;
ll x0;
ll h[maxn];
int vis[maxn];
struct node{
    ll key,h;
}t[5];
int tt[maxn][21];
ll va[maxn][21],vb[maxn][21];
set<ll>q;
map<ll,int>mp;
ll a[maxn],b[maxn];
int fa[maxn],fb[maxn];
bool cmp(node u,node v){
    return (u.key<v.key ||(u.key==v.key && u.h<v.h));
}
void pre(){
    for(int i=n;i>=1;i--){
        q.insert(h[i]);
        t[1].h=*--q.lower_bound(h[i]);
        t[2].h=*q.upper_bound(h[i]);
        if(t[1].h!=-inf)t[3].h=*--q.lower_bound(t[1].h);
        else t[3].h=-inf;
        if(t[2].h!=inf)t[4].h=*q.upper_bound(t[2].h);
        else t[4].h=inf;
        for(int k=1;k<=4;k++){
            t[k].key=abs(t[k].h-h[i]);
        }
        sort(t+1,t+5,cmp);
        a[i]=t[2].key;b[i]=t[1].key;
        fa[i]=mp[t[2].h];fb[i]=mp[t[1].h];//system("pause");
    //  for(int j=1;j<=n;j++){
    //      printf("(%d %d %d %lld %lld)n",i,fa[i],fb[i],a[i],b[i]);
    //  }
        for(int j=0;j<=20;j++){
            if(!j){
                if(fa[i]){
                    tt[i][0]=fa[i];va[i][0]=a[i];
                }
            }
            else if(j==1){
                if(fb[fa[i]]){
                    tt[i][1]=fb[fa[i]];
                    vb[i][1]=b[fa[i]];va[i][1]=a[i];
                }
            }
            else if(tt[tt[i][j-1]][j-1]){
                va[i][j]=va[i][j-1]+va[tt[i][j-1]][j-1];
                vb[i][j]=vb[i][j-1]+vb[tt[i][j-1]][j-1];
                tt[i][j]=tt[tt[i][j-1]][j-1];
            }
            else break;
        }
    }
}
double calc1(int s,ll limit,int typ){
    ll suma=0;ll sumb=0;
    if(typ==1){
        for(int i=20;i>=0;i--){
            if(tt[s][i] && (suma+sumb+va[s][i]+vb[s][i])<=limit){
                suma+=va[s][i];sumb+=vb[s][i];
                s=tt[s][i];
            //  printf("[%d %lld %lld]n",s,suma,sumb);
            }
        }//system("pause");
        if(sumb==0)return inf;
        return (double)suma/(double)sumb;
    }
    else if(typ==2){
        for(int i=20;i>=0;i--){
            if(tt[s][i] && (suma+sumb+va[s][i]+vb[s][i])<=limit){
                suma+=va[s][i];sumb+=vb[s][i];
                s=tt[s][i];
            //  printf("[%d %lld %lld]n",s,suma,sumb);
            }
        }//system("pause");     
        printf("%lld %lldn",suma,sumb);
        return 0;
    }
}
void solve1(ll x0){
    double minn=1e18;int ans;//printf("&n");
    for(int i=1;i<=n;i++){
        double tp=calc1(i,x0,1);
        if(minn>tp ||(minn==tp && h[ans]<h[i])){
            minn=tp;ans=i;
        }
        //printf("*n");
    //  system("pause");
    }
    printf("%dn",ans);
}
void solve2(int s,ll x0){
    calc1(s,x0,2);
}
void file(){
    freopen("drive.in","r",stdin);
    freopen("drive.out","w",stdout);
}
int main(){
    //file();
    scanf("%d",&n);
    q.insert(-inf);q.insert(inf);
    for(int i=1;i<=n;i++){
        scanf("%lld",&h[i]);
        mp[h[i]]=i;
    }
    pre();//system("pause");
    scanf("%lld",&x0);
    solve1(x0);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int s;ll x;
        scanf("%d%lld",&s,&x);
        solve2(s,x);
    }
    return 0;
}

最后

以上就是鲜艳裙子最近收集整理的关于NOIP2012 开车旅行：SET+倍增的全部内容，更多相关NOIP2012内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(72)

相关文章

旅行(NOIP模拟测试22)
旅行(NOIP模拟测试22)
NOIp2012开车旅行
NOIp2012开车旅行
NOIP 2012 Senior 3 - 开车旅行
NOIP 2012 Senior 3 - 开车旅行
【NOIP2012】旅行计划
【NOIP2012】旅行计划
NOIP2012 开车旅行：SET+倍增
NOIP2012 开车旅行：SET+倍增
【暑期每日一题】洛谷 P7398 [COCI2020-2021#5] Šifra~
【暑期每日一题】洛谷 P7398 [COCI2020-2021#5] Šifra~
洛谷 P1137 旅行计划
洛谷 P1137 旅行计划
【暑期每日一题】洛谷 P7550 [COCI2020-2021#6] Bold
【暑期每日一题】洛谷 P7550 [COCI2020-2021#6] Bold

评论列表共有 0 条评论

立即
投稿
返回
顶部