苏州市吴江区中学生信息编程竞赛域
Powered by Vijos
/ 苏州市吴江区中学生信息编程竞赛域 / 题库 / 开车旅行 /

题解

4 条题解

  • 1
    @ 2025-03-29 17:02:57

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    typedef long long LL;
    inline const LL Get_Int() {
    LL num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
    if(x=='-')bj=-1;
    x=getchar();
    }
    while(x>='0'&&x<='9') {
    num=num*10+x-'0';
    x=getchar();
    }
    return num*bj;
    }
    int n,m,Go[2005][2],ansl;
    LL a[2005],x0,Dist[2005][2005],Min[2005],Second[2005],ans[2]= {1,10000000000};
    int main() {
    n=Get_Int();
    for(int i=1; i<=n; i++)a[i]=Get_Int();
    memset(Min,0x7f,sizeof(Min));
    memset(Second,0x7f,sizeof(Second));
    for(int i=1; i<=n; i++) {
    int Minl=0,Secondl=0;
    for(int j=i+1; j<=n; j++) {
    Dist[i][j]=abs(a[i]-a[j]);
    if(Dist[i][j]<Min[i]||(Dist[i][j]==Min[i]&&a[j]<a[Minl])) {
    Second[i]=Min[i];
    Secondl=Minl;
    Min[i]=Dist[i][j];
    Minl=j;
    } else if(Dist[i][j]<Second[i]||(Dist[i][j]==Second[i]&&a[j]<a[Secondl])) {
    Second[i]=Dist[i][j];
    Secondl=j;
    }
    }
    Go[i][0]=Minl;
    Go[i][1]=Secondl;
    }
    x0=Get_Int();
    for(int i=1; i<=n; i++) { //从i开始
    LL Now=i,dist=0,chose=1,sum[2]= {0};
    while(Go[Now][chose]&&dist+Dist[Now][Go[Now][chose]]<=x0) {
    dist+=Dist[Now][Go[Now][chose]];
    sum[chose]+=Dist[Now][Go[Now][chose]];
    Now=Go[Now][chose];
    chose^=1;
    }
    if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
    ans[1]=sum[1];
    ans[0]=sum[0];
    ansl=i;
    }
    }
    printf("%d\n",ansl);
    m=Get_Int();
    while(m--) {
    LL Now=Get_Int(),x=Get_Int(),dist=0,chose=1,sum[2]= {0};
    while(Go[Now][chose]&&dist+Dist[Now][Go[Now][chose]]<=x) {
    dist+=Dist[Now][Go[Now][chose]];
    sum[chose]+=Dist[Now][Go[Now][chose]];
    Now=Go[Now][chose];
    chose^=1;
    }
    printf("%lld %lld\n",sum[1],sum[0]);
    }
    return 0;
    }

  • 0
    @ 2025-03-29 17:28:27

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    typedef long long LL;
    inline const LL Get_Int() {
    LL num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
    if(x=='-')bj=-1;
    x=getchar();
    }
    while(x>='0'&&x<='9') {
    num=num*10+x-'0';
    x=getchar();
    }
    return num*bj;
    }
    const int maxn=100005;
    int n,m,Go[maxn][2],ansl,Left[maxn],Right[maxn],p[maxn][25];
    LL x0,a[maxn],ans[2]= {1,10000000000},Dist[maxn][2],DistA[maxn][25],DistB[maxn][25];
    struct City {
    int height,pos;
    bool operator < (const City& b) const {
    return height<b.height;
    }
    } b[maxn];
    LL dist(int x,int y) {
    return abs(a[x]-a[y]);
    }
    void Sparse_Table() {
    for(int i=1; i<n; i++) {
    p[i][0]=Go[Go[i][1]][0];
    DistA[i][0]=Dist[i][1];
    DistB[i][0]=Dist[Go[i][1]][0];
    }
    for(int j=1; j<=log2(n); j++)
    for(int i=1; i<=n; i++) {
    p[i][j]=p[p[i][j-1]][j-1];
    if(!p[i][j])continue;
    DistA[i][j]=DistA[i][j-1]+DistA[p[i][j-1]][j-1];
    DistB[i][j]=DistB[i][j-1]+DistB[p[i][j-1]][j-1];
    }
    }
    void Jump(int Now,LL x,LL* sum) {
    int k=log2(n);
    LL tot=0;
    for(int i=k; i>=0; i--)
    if(p[Now][i]&&tot+DistA[Now][i]+DistB[Now][i]<=x) {
    tot+=DistA[Now][i]+DistB[Now][i];
    sum[1]+=DistA[Now][i];
    sum[0]+=DistB[Now][i];
    Now=p[Now][i];
    }
    if(tot+DistA[Now][0]<=x) {
    tot+=DistA[Now][0];
    sum[1]+=DistA[Now][0];
    Now=Go[Now][1];
    }
    }
    int main() {
    n=Get_Int();
    for(int i=1; i<=n; i++) {
    a[i]=Get_Int();
    b[i].height=a[i];
    b[i].pos=i;
    }
    sort(b+1,b+n+1);
    for(int i=1; i<=n; i++) {
    Left[b[i].pos]=b[i-1].pos;
    Right[b[i].pos]=b[i+1].pos;
    }
    for(int i=1; i<=n; i++) { //双向链表处理最近次近
    LL Min=1e15,Second=1e15;
    int Minl=0,Secondl=0;
    if(Left[i])Min=min(Min,dist(i,Left[i])),Minl=Left[i];
    if(Left[Left[i]]&&dist(i,Left[Left[i]])<Second)Second=dist(i,Left[Left[i]]),Secondl=Left[Left[i]];
    if(Right[i]&&dist(i,Right[i])<Min) {
    Second=Min;
    Secondl=Minl;
    Min=dist(i,Right[i]);
    Minl=Right[i];
    } else if(Right[i]&&dist(i,Right[i])<Second)Second=dist(i,Right[i]),Secondl=Right[i];
    if(Right[Right[i]]&&dist(i,Right[Right[i]])<Second)Second=dist(i,Right[Right[i]]),Secondl=Right[Right[i]];
    Go[i][0]=Minl;
    Go[i][1]=Secondl;
    Dist[i][0]=Min;
    Dist[i][1]=Second;
    if(Right[i])Left[Right[i]]=Left[i];
    if(Left[i])Right[Left[i]]=Right[i];
    }
    Sparse_Table();
    x0=Get_Int();
    for(int i=1; i<=n; i++) { //从i开始
    LL sum[2]= {0,0};
    Jump(i,x0,sum);
    if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
    ans[1]=sum[1];
    ans[0]=sum[0];
    ansl=i;
    }
    }
    printf("%d\n",ansl);
    m=Get_Int();
    while(m--) {
    LL sum[2]= {0,0},Now=Get_Int(),x=Get_Int();
    Jump(Now,x,sum);
    printf("%lld %lld\n",sum[1],sum[0]);
    }
    return 0;
    }

  • 0
    @ 2025-03-29 17:04:36

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    typedef long long LL;
    inline const LL Get_Int() {
    LL num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
    if(x=='-')bj=-1;
    x=getchar();
    }
    while(x>='0'&&x<='9') {
    num=num*10+x-'0';
    x=getchar();
    }
    return num*bj;
    }
    const int maxn=100005;
    int n,m,Go[maxn][2],ansl,Left[maxn],Right[maxn],p[maxn][25];
    LL x0,a[maxn],ans[2]= {1,10000000000},Dist[maxn][2],DistA[maxn][25],DistB[maxn][25];
    struct City {
    int height,pos;
    bool operator < (const City& b) const {
    return height<b.height;
    }
    } b[maxn];
    LL dist(int x,int y) {
    return abs(a[x]-a[y]);
    }
    void Sparse_Table() {
    for(int i=1; i<n; i++) {
    p[i][0]=Go[Go[i][1]][0];
    DistA[i][0]=Dist[i][1];
    DistB[i][0]=Dist[Go[i][1]][0];
    }
    for(int j=1; j<=log2(n); j++)
    for(int i=1; i<=n; i++) {
    p[i][j]=p[p[i][j-1]][j-1];
    if(!p[i][j])continue;
    DistA[i][j]=DistA[i][j-1]+DistA[p[i][j-1]][j-1];
    DistB[i][j]=DistB[i][j-1]+DistB[p[i][j-1]][j-1];
    }
    }
    void Jump(int Now,LL x,LL* sum) {
    int k=log2(n);
    LL tot=0;
    for(int i=k; i>=0; i--)
    if(p[Now][i]&&tot+DistA[Now][i]+DistB[Now][i]<=x) {
    tot+=DistA[Now][i]+DistB[Now][i];
    sum[1]+=DistA[Now][i];
    sum[0]+=DistB[Now][i];
    Now=p[Now][i];
    }
    if(tot+DistA[Now][0]<=x) {
    tot+=DistA[Now][0];
    sum[1]+=DistA[Now][0];
    Now=Go[Now][1];
    }
    }
    int main() {
    n=Get_Int();
    for(int i=1; i<=n; i++) {
    a[i]=Get_Int();
    b[i].height=a[i];
    b[i].pos=i;
    }
    sort(b+1,b+n+1);
    for(int i=1; i<=n; i++) {
    Left[b[i].pos]=b[i-1].pos;
    Right[b[i].pos]=b[i+1].pos;
    }
    for(int i=1; i<=n; i++) { //双向链表处理最近次近
    LL Min=1e15,Second=1e15;
    int Minl=0,Secondl=0;
    if(Left[i])Min=min(Min,dist(i,Left[i])),Minl=Left[i];
    if(Left[Left[i]]&&dist(i,Left[Left[i]])<Second)Second=dist(i,Left[Left[i]]),Secondl=Left[Left[i]];
    if(Right[i]&&dist(i,Right[i])<Min) {
    Second=Min;
    Secondl=Minl;
    Min=dist(i,Right[i]);
    Minl=Right[i];
    } else if(Right[i]&&dist(i,Right[i])<Second)Second=dist(i,Right[i]),Secondl=Right[i];
    if(Right[Right[i]]&&dist(i,Right[Right[i]])<Second)Second=dist(i,Right[Right[i]]),Secondl=Right[Right[i]];
    Go[i][0]=Minl;
    Go[i][1]=Secondl;
    Dist[i][0]=Min;
    Dist[i][1]=Second;
    if(Right[i])Left[Right[i]]=Left[i];
    if(Left[i])Right[Left[i]]=Right[i];
    }
    Sparse_Table();
    x0=Get_Int();
    for(int i=1; i<=n; i++) { //从i开始
    LL sum[2]= {0,0};
    Jump(i,x0,sum);
    if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
    ans[1]=sum[1];
    ans[0]=sum[0];
    ansl=i;
    }
    }
    printf("%d\n",ansl);
    m=Get_Int();
    while(m--) {
    LL sum[2]= {0,0},Now=Get_Int(),x=Get_Int();
    Jump(Now,x,sum);
    printf("%lld %lld\n",sum[1],sum[0]);
    }
    return 0;
    }

  • 0
    @ 2025-03-29 17:03:44

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    typedef long long LL;
    inline const LL Get_Int() {
    LL num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
    if(x=='-')bj=-1;
    x=getchar();
    }
    while(x>='0'&&x<='9') {
    num=num*10+x-'0';
    x=getchar();
    }
    return num*bj;
    }
    const int maxn=100005;
    int n,m,Go[maxn][2],ansl,Left[maxn],Right[maxn],p[maxn][25];
    LL x0,a[maxn],ans[2]= {1,10000000000},Dist[maxn][2],DistA[maxn][25],DistB[maxn][25];
    struct City {
    int height,pos;
    bool operator < (const City& b) const {
    return height<b.height;
    }
    } b[maxn];
    LL dist(int x,int y) {
    return abs(a[x]-a[y]);
    }
    void Sparse_Table() {
    for(int i=1; i<n; i++) {
    p[i][0]=Go[Go[i][1]][0];
    DistA[i][0]=Dist[i][1];
    DistB[i][0]=Dist[Go[i][1]][0];
    }
    for(int j=1; j<=log2(n); j++)
    for(int i=1; i<=n; i++) {
    p[i][j]=p[p[i][j-1]][j-1];
    if(!p[i][j])continue;
    DistA[i][j]=DistA[i][j-1]+DistA[p[i][j-1]][j-1];
    DistB[i][j]=DistB[i][j-1]+DistB[p[i][j-1]][j-1];
    }
    }
    void Jump(int Now,LL x,LL* sum) {
    int k=log2(n);
    LL tot=0;
    for(int i=k; i>=0; i--)
    if(p[Now][i]&&tot+DistA[Now][i]+DistB[Now][i]<=x) {
    tot+=DistA[Now][i]+DistB[Now][i];
    sum[1]+=DistA[Now][i];
    sum[0]+=DistB[Now][i];
    Now=p[Now][i];
    }
    if(tot+DistA[Now][0]<=x) {
    tot+=DistA[Now][0];
    sum[1]+=DistA[Now][0];
    Now=Go[Now][1];
    }
    }
    int main() {
    n=Get_Int();
    for(int i=1; i<=n; i++) {
    a[i]=Get_Int();
    b[i].height=a[i];
    b[i].pos=i;
    }
    sort(b+1,b+n+1);
    for(int i=1; i<=n; i++) {
    Left[b[i].pos]=b[i-1].pos;
    Right[b[i].pos]=b[i+1].pos;
    }
    for(int i=1; i<=n; i++) { //双向链表处理最近次近
    LL Min=1e15,Second=1e15;
    int Minl=0,Secondl=0;
    if(Left[i])Min=min(Min,dist(i,Left[i])),Minl=Left[i];
    if(Left[Left[i]]&&dist(i,Left[Left[i]])<Second)Second=dist(i,Left[Left[i]]),Secondl=Left[Left[i]];
    if(Right[i]&&dist(i,Right[i])<Min) {
    Second=Min;
    Secondl=Minl;
    Min=dist(i,Right[i]);
    Minl=Right[i];
    } else if(Right[i]&&dist(i,Right[i])<Second)Second=dist(i,Right[i]),Secondl=Right[i];
    if(Right[Right[i]]&&dist(i,Right[Right[i]])<Second)Second=dist(i,Right[Right[i]]),Secondl=Right[Right[i]];
    Go[i][0]=Minl;
    Go[i][1]=Secondl;
    Dist[i][0]=Min;
    Dist[i][1]=Second;
    if(Right[i])Left[Right[i]]=Left[i];
    if(Left[i])Right[Left[i]]=Right[i];
    }
    Sparse_Table();
    x0=Get_Int();
    for(int i=1; i<=n; i++) { //从i开始
    LL sum[2]= {0,0};
    Jump(i,x0,sum);
    if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
    ans[1]=sum[1];
    ans[0]=sum[0];
    ansl=i;
    }
    }
    printf("%d\n",ansl);
    m=Get_Int();
    while(m--) {
    LL sum[2]= {0,0},Now=Get_Int(),x=Get_Int();
    Jump(Now,x,sum);
    printf("%lld %lld\n",sum[1],sum[0]);
    }
    return 0;
    }

  • 1

开车旅行

信息

ID
1354
难度
8
分类
数据结构 | 动态规划 点击显示
标签
递交数
13
已通过
7
通过率
54%
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1