题解 - Vijos

7

此题可以使用链表/平衡树+倍增的方法A掉
先讲讲暴力
暴力（70分）：
暴力预处理每个点可以到达的最短和次短的位置O(n^2)
然后暴力枚举每个点模拟
代码如下：

#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;
}

接下来讲讲正解：
我们要优化这份代码，必须着手于两个O(n^2)

第一个：预处理最短和次短。
我们可以按照权值建一个双向链表，然后快速O(n)维护出每个权值的前驱后继，进而就可以得出最短和次短。
或者也可以使用平衡树等数据结构O(nlogn)维护出前驱后继，虽然可以过，但是常数可想而知。

第二个：模拟
我们一个一个走模拟到最终位置，这样太慢了，怎么办呢？
走的过程已经定下来了，有没有快速的方法求出其终点？
使用倍增，就像爬树快速找到LCA一样，我们预处理后可以快速获得其最终位置。
如何倍增？
将A走一步和B走一步和在一起，变为AB一起分别走一步，那么接下来每一个周期都是定的，就可以倍增走了，边倍增边维护路径上的总和，进而可以处理掉x的限制。

代码如下：

#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;
}

还有注意ans[1]别开太大，否则可能会乘爆，开1e10即可。

2

孤的千年 LV 8 @ 7 年前

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

template<typename T>inline void read(T &_)
{
    _=0;char __=getchar();bool ___=false;
    while(__<'0' || __>'9'){if(__=='-') ___=true;__=getchar();}
    while(__>='0' && __<='9'){_=(_<<3)+(_<<1)+__-'0';__=getchar();}
    if(___) _=-_;
}

const int maxn=1e5+5;
#define ll long long

struct Node
{
    int id,high;
    inline bool operator<(const Node &B)const
    {
        return high<B.high;
    }
}E[maxn];

struct Edge
{
    int id,cut;
    inline bool operator<(const Edge &B)const
    {
        return cut==B.cut?E[id].high<E[B.id].high:cut<B.cut;
    }
}book[5];

set<Node>s;

struct Line
{
    int nexta,nextb;
}line[maxn];

int f[maxn][21];
int dis1[maxn][21];
int dis2[maxn][21];

inline void pack(int now,int &top,set<Node>::iterator pos)
{
    book [++top]=(Edge){pos->id,abs(pos->high-E[now].high)};
}

void del(int now)
{
    set<Node>::iterator pos=s.find(E[now]);
    int top=0;
    if(pos!=s.begin())
    {
        pos--;
        pack(now,top,pos);
        if(pos!=s.begin()) pack(now,top,--pos),pos++;
        pos++;
    }
    if(++pos!=s.end())
    {
        pack(now,top,pos);
        if(++pos!=s.end()) pack(now,top,pos);
    }
    sort(book+1,book+top+1);
    line[now].nextb=book[1].id;
    if(top>=2) line[now].nexta=book[2].id;
}

int n;

inline void query(int begin,int limit,int &disa,int &disb)
{
    for(int i=20;i>=0;i--)
    {
        if(begin+(1<<i)<=n && f[begin][i] && dis1[begin][i]+dis2[begin][i]<=limit)
        {
            disa+=dis1[begin][i];
            disb+=dis2[begin][i];
            limit-=dis1[begin][i]+dis2[begin][i];
            begin=f[begin][i];
        }
    }
    if(!line[begin].nexta) return;
    int ret=abs(E[begin].high-E[line[begin].nexta].high);
    if(ret<=limit) disa+=ret;
}

int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(E[i].high),E[i].id=i;
    for(int i=n;i>=1;i--)
    {
        s.insert(E[i]);
        if(i!=n) del(i);
    }
    
    for(int i=1;i<=n;i++)
    {
        int v1=line[i].nexta,v2=line[v1].nextb;
        dis1[i][0]=v1?abs(E[i].high-E[v1].high):0;
        dis2[i][0]=v2?abs(E[v1].high-E[v2].high):0;
        f[i][0]=v2;
    }
    
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            dis1[i][j]=dis1[i][j-1]+dis1[f[i][j-1]][j-1];
            dis2[i][j]=dis2[i][j-1]+dis2[f[i][j-1]][j-1];
        }       
    
    int x0;read(x0);
    int final=0;
    int ansa=0x3f3f3f3f,ansb=0;
    for(int i=1;i<=n;i++)
    {
        int disa=0,disb=0;
        query(i,x0,disa,disb);
        if(disa)
        {
            if(!final || ((ll)disa*ansb<(ll)disb*ansa))
            {
                final=i;
                ansa=disa;
                ansb=disb;
            }
            else if((ll)disa*ansb==(ll)disb*ansa && E[i].high>E[final].high)
            {
                final=i;
                ansa=disa;
                ansb=disb;
            }
        }
    }
    printf("%d\n",final);
    int m;read(m);
    for(int i=1;i<=m;i++)
    {
        int begin,limit;
        read(begin),read(limit);
        int disa=0,disb=0;
        query(begin,limit,disa,disb);
        printf("%d %d\n",disa,disb);
    }
    return 0;
}

1

938936 LV 8 @ 6 年前

用双向链表+倍增方法AC(具体可以开其他大佬的题解,这里不详细描述)
下面是有良心带注释的代码a.a

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define N 100001
#define next nextt
#define inf 2000000000
using namespace std;
typedef long long ll;
int n,m,h[N];//h保存高度 
int fa[N],fb[N],f[20][N];//fa,fb表示a,b在点i走一步的目标,f表示2^j轮后的目标 
ll ca[N],cb[N];//ca,cb表示a,b在点i走一步的距离 
ll dis[20][N],disa[20][N],disb[20][N];//dis,disa,disb表示2^j轮内总距离、a距离和b距离 
int next[N],last[N];//双向链表 
struct point{//结构体用于排序和构建链表 
    int id;
    ll h;
}val[N];
bool operator<(point a,point b){//用于排序 
    return a.h<b.h;
}
void getaim(int s,int &c1,int &c2){//求后续点,c1表示B目标,c2表示A目标,c1表示第一近,c2表示第二近 
    int cnt=0,id[5],i;
    ll h1,h2;
    ll a1[5];
    c1=c2=0;
    h1=h2=inf;
    if(next[s]) a1[++cnt]=h[next[s]],id[cnt]=next[s];
    if(next[next[s]]) a1[++cnt]=h[next[next[s]]],id[cnt]=next[next[s]];
    if(last[s]) a1[++cnt]=h[last[s]],id[cnt]=last[s];
    if(last[last[s]]) a1[++cnt]=h[last[last[s]]],id[cnt]=last[last[s]];
    for(i=1;i<=cnt;i++){
        int v=abs(a1[i]-h[s]);
        if(v<h1 || v==h1&&a1[i]<h[c1]){
            c2=c1;
            c1=id[i];
            h2=h1;
            h1=v;
        }else if(v<h2 || v==h2&&a1[i]<h[c2]){
            h2=v;
            c2=id[i];
        }
    }
}

void link(){//排序并构造链表 
    sort(val+1,val+n+1);
    int i;
    for(i=1;i<=n;i++){
        if(i!=1){
            last[val[i].id]=val[i-1].id;
        }else last[val[i].id]=0;
        if(i!=n){
            next[val[i].id]=val[i+1].id;
        }else next[val[i].id]=0;
    }
}

void getfa(){//求倍增初始值 
    int i,a,b;
    for(i=1;i<=n;i++){
        getaim(i,b,a);
        if(a==0) fa[i]=i,ca[i]=0; else fa[i]=a,ca[i]=abs(h[a]-h[i]);//记录a目标点和距离 
        if(b==0) fb[i]=i,cb[i]=0; else fb[i]=b,cb[i]=abs(h[b]-h[i]);//记录b目标点和距离 
        if(last[i])//删除链表 
            next[last[i]]=next[i];
        if(next[i]) last[next[i]]=last[i];
    }
    for(i=1;i<=n;i++){//获取倍增初始值 
        if(cb[fa[i]]==0||ca[i]==0){//如果无法走完一轮则记录0 
            f[0][i]=i;
            dis[0][i]=0;
            disa[0][i]=0;
            disb[0][i]=0;
        }else{//可以走完一轮则记录走一轮的值 
            f[0][i]=fb[fa[i]];
            dis[0][i]=cb[fa[i]]+ca[i];
            disa[0][i]=ca[i];
            disb[0][i]=cb[fa[i]];
            
        }
    }
}

void pow(){//倍增 
    int i,j;
    for(j=1;j<20;j++){
        for(i=1;i<=n;i++){
            f[j][i]=f[j-1][f[j-1][i]];
            dis[j][i]=dis[j-1][i]+dis[j-1][f[j-1][i]];
            disa[j][i]=disa[j-1][i]+disa[j-1][f[j-1][i]];
            disb[j][i]=disb[j-1][i]+disb[j-1][f[j-1][i]];
        }
    }
}

void getlen(int s,ll x,ll &sa,ll &sb){//求解a,b路程 
    int i,v=s;
    ll p=x;
    sa=sb=0;
    for(i=19;i>=0;i--){
        if(p>=dis[i][v]){//先求轮次 
            p-=dis[i][v];
            sa+=disa[i][v];
            sb+=disb[i][v];
            v=f[i][v];
        }
    }
    if(p>=ca[v]) sa+=ca[v];//若a可以继续走,则记录 
}
#define eps 1e-6
void work1(ll x){//求第一个问题 
    int i,ans=1,flag=0;//flag表示是否为正无穷 
    double pi=inf;//pi记录比值 
    ll sa=0,sb=0;//表示a,b距离 
    for(i=1;i<=n;i++){
        getlen(i,x,sa,sb);
        if(sb>0){
            double p1=sa,p2=sb;
            p1=p1/p2;
            if(p1<pi-eps||(p1-pi<eps&&pi-p1<eps&&h[i]>h[ans])){//若比值更小,或比值相等且高度更大则更新 
                pi=p1;
                ans=i;
                flag=1;
            }
        }else if(!flag&&h[i]<h[ans]) ans=i; //若比值均为正无穷且高度更大更新 
    }
    cout<<ans<<endl;
}
void work2(int s,ll x){//求解第二个问题 
    ll sa,sb;
    getlen(s,x,sa,sb);
    cout<<sa<<" "<<sb<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    int i,a;
    ll x;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a;
        h[i]=val[i].h=a;
        val[i].id=i;
    }
    link();getfa();pow();
    cin>>x;
    work1(x);
    cin>>m;
    for(i=1;i<=m;i++){
        cin>>a;
        cin>>x;
        work2(a,x);
    }
    return 0;
}

1

Sky1231 (sky1231) LV 10 @ 7 年前

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    //const ll oomin=(numeric_limits<ll>::min)(),oomax=(numeric_limits<ll>::max)();
    const ll oomin=(int)(0xcfcfcfcf),oomax=(int)(0x3f3f3f3f);
    
    ll n,m,*hp,spS,spR,bzS;
    ll h[125000+1+1];
    ll fa[125000+1];
    ll lc[125000+1];
    ll rc[125000+1];
    ll pla[125000+1];
    ll sum[125000+1];
    ll bza[125000+1][20];//bz a to
    ll bzaa[125000+1][20];//bz a sum a
    ll bzab[125000+1][20];//bz a sum b
    ll bzb[125000+1][20];//bz b to
    ll bzba[125000+1][20];//bz b sum a
    ll bzbb[125000+1][20];//bz b sum b
    
    #define llabs(x) (ll(abs(double(x))))
    
    ll cmph(ll x,ll y)
    {
        return (llabs(x-(*hp))<llabs(y-(*hp))||y==oomin||y==oomax);
    }
    
    void rotate(ll now,ll aim)
    {
        if (aim==fa[spR])
            spR=now;
        while (fa[now]!=aim)
        {
            ll nowfa=fa[now],fafa=fa[nowfa],cc;
            if (sum[now]>sum[nowfa])
            {
                cc=lc[now];
                lc[now]=nowfa;
                rc[nowfa]=cc;
            }
            else
            {
                cc=rc[now];
                rc[now]=nowfa;
                lc[nowfa]=cc;
            }
            fa[cc]=nowfa;
            fa[nowfa]=now;
            fa[now]=fafa;
            if (fafa!=-1)
            {
                if (sum[now]<sum[fafa])
                    lc[fafa]=now;
                else
                    rc[fafa]=now;
            }
        }
    }
    
    void insert(ll nowpla,ll nowsum)
    {
        if (spS==0)
        {
            spS++;
            fa[spR]=lc[spR]=rc[spR]=-1;
            pla[spR]=nowpla;
            sum[spR]=nowsum;
        }
        else
        {
            ll now,last;
            for (now=spR,last=-1;now!=-1;)
            {
                last=now;
                if (nowsum==sum[now])
                    break;
                else if (nowsum<sum[now])
                    now=lc[now];
                else if (nowsum>sum[now])
                    now=rc[now];
            }
            if (now==-1)
            {
                if (nowsum<sum[last])
                    lc[last]=++spS;
                else if (nowsum>sum[last])
                    rc[last]=++spS;
                fa[spS]=last;
                lc[spS]=rc[spS]=-1;
                pla[spS]=nowpla;
                sum[spS]=nowsum;
            }
        }
        rotate(spS,-1);
    }
    
    ll find(ll nowsum)
    {
        for (ll now=spR;now!=-1;)
            if (nowsum==sum[now])
                return now;
            else if (nowsum<sum[now])
                now=lc[now];
            else if (nowsum>sum[now])
                now=rc[now];
        return -1;
    }
    
    ll findlow(ll nowsum)
    {
        if (spS==0)
            return oomax;
        else
        {
            ll lmax=oomax;
            for (ll now=spR;now!=-1;)
                if (nowsum<sum[now])
                    now=lc[now];
                else if (nowsum>sum[now])
                    lmax=sum[now],now=rc[now];
                else
                    return nowsum;
            return lmax;
        }
    }
    
    ll findlar(ll nowsum)
    {
        if (spS==0)
            return oomin;
        else
        {
            ll rmin=oomin;
            for (ll now=spR;now!=-1;)
                if (nowsum<sum[now])
                    rmin=sum[now],now=lc[now];
                else if (nowsum>sum[now])
                    now=rc[now];
                else
                    return nowsum;
            return rmin;
        }
    }
    
    void work(ll now,ll maxdis,ll &suma,ll &sumb)
    {
        suma=sumb=0;
        for (ll i=bzS;i>=0;i--)
        {
            for (;i>0&&(bza[now][i]==0||bzaa[now][i]+bzab[now][i]+suma+sumb>maxdis);i--)
                ;
            if (i==0&&(bza[now][i]==0||bzaa[now][i]+bzab[now][i]+suma+sumb>maxdis))
                break;
            suma+=bzaa[now][i];
            sumb+=bzab[now][i];
            now=bza[now][i];
        }
    }
    
    void main()
    {
        while (~scanf("%lld",&n))
        {
            for (ll i=1;i<=n;i++)
                scanf("%lld",&h[i]);
            spS=0,spR=1;
            memset(fa,0,sizeof(fa));
            memset(lc,0,sizeof(lc));
            memset(rc,0,sizeof(rc));
            memset(pla,0,sizeof(pla));
            memset(sum,0,sizeof(sum));
            memset(bza,0,sizeof(bza));
            memset(bzaa,0,sizeof(bzaa));
            memset(bzab,0,sizeof(bzab));
            memset(bzb,0,sizeof(bzb));
            memset(bzba,0,sizeof(bzba));
            memset(bzbb,0,sizeof(bzbb));
            for (ll i=n;i>=1;i--)
            {
                ll temp[4];
                temp[0]=findlow(h[i]);
                if (temp[0]!=oomax)
                    temp[1]=findlow(temp[0]-1);
                else
                    temp[1]=oomax;
                temp[2]=findlar(h[i]);
                if (temp[2]!=oomin)
                    temp[3]=findlar(temp[2]+1);
                else
                    temp[3]=oomin;
                hp=&h[i];
                sort(&temp[0],&temp[4],cmph);
                if (temp[0]!=oomin&&temp[0]!=oomax)
                {
                    ll now=find(temp[0]);
                    bzb[i][0]=pla[now];
                    bzba[i][0]=0;
                    bzbb[i][0]=llabs(h[i]-temp[0]);
                }
                if (temp[1]!=oomin&&temp[1]!=oomax)
                {
                    ll now=find(temp[1]);
                    bza[i][0]=pla[now];
                    bzaa[i][0]=llabs(h[i]-temp[1]);
                    bzab[i][0]=0;
                }
                insert(i,h[i]);
            }
            ll flag=0;
            for (ll i=1;i<=n;i++)
                if (bza[i][0]!=0&&bzb[bza[i][0]][0]!=0)
                {
                    bza[i][1]=bzb[bza[i][0]][0];
                    bzaa[i][1]=bzaa[i][0]+bzba[bza[i][0]][0];
                    bzab[i][1]=bzab[i][0]+bzbb[bza[i][0]][0];
                    flag=1;
                }
            for (ll i=2;flag;i++)
            {
                flag=0;
                for (ll j=1;j<=n;j++)
                    if (bza[j][i-1]!=0&&bza[bza[j][i-1]][i-1]!=0)
                    {
                        bza[j][i]=bza[bza[j][i-1]][i-1];
                        bzaa[j][i]=bzaa[j][i-1]+bzaa[bza[j][i-1]][i-1];
                        bzab[j][i]=bzab[j][i-1]+bzab[bza[j][i-1]][i-1];
                        flag=1;
                    }
                bzS=i-1;
            }
            ll now,x0,ansa=oomax,ansb=0;
            scanf("%lld",&x0);
            h[now=n+1]=oomin;
            for (ll i=1;i<=n;i++)
            {
                ll tempa,tempb;
                work(i,x0,tempa,tempb);
                if (tempa==0)
                    continue;
                else if ((ansb==0&&(tempb!=0||(tempb==0&&h[now]<h[i])))||(ansb!=0&&tempb!=0&&(tempa*ansb<tempb*ansa||(tempa*ansb==tempb*ansa&&h[now]<h[i]))))
                {
                    ansa=tempa;
                    ansb=tempb;
                    now=i;
                }
            }
            printf("%lld\n",now);
            scanf("%lld",&m);
            for (ll i=1;i<=m;i++)
            {
                ll si,xi,ansa,ansb;
                scanf("%lld%lld",&si,&xi);
                work(si,xi,ansa,ansb);
                printf("%lld %lld\n",ansa,ansb);
            }
        }
    }
};

int main()
{
    dts::main();
}

sky1231 @ 7 年前

很H2O的題

1

Kvar_ispw17 LV 8 @ 7 年前

贡献一个用 set 实现的预处理，清晰易懂。

#include <bits/stdc++.h>
#define N 100000 + 5
using namespace std;
#define EPS 1e-6
typedef long long ll;
#define inf 0x7f7f7f7f
class city {
  public:
    ll idx, h, abs;
    city() {};
    city(ll x) { h = x; }
    city(ll a, ll b, ll c) { idx = a, h = b, abs = c; }
    bool operator < (const city& rhs) const {
        if (h > rhs.h) return false;
        else if (h < rhs.h) return true;
        else return abs < rhs.abs;
    }
} c[N];

int n, x1, m;
ll blue[N], red[N];
ll f[N][25], dA[N][25], dB[N][25];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &c[i].h);
        c[i].idx = i;
    }
    c[0] = inf;
    set<city> s;
    memset(blue, 0, sizeof blue);
    memset(red, 0, sizeof red);
    blue[n - 1] = n;
    s.insert(c[n]);
    s.insert(c[n - 1]);
    for (int i = n - 2; i >= 1; i--) {
        set<city>::const_iterator i1, i2, i3, i4;
        city c1, c2, c3, c4;
        c1 = c2 = c3 = c4 = city(0, inf, 0);
        i3 = s.lower_bound(c[i]);
        if (i3 == s.end()) {
            i2 = i3, i2--;
            i1 = i2, i1--;
            c1 = city((*i1).idx, abs((*i1).h - c[i].h), 0);
            c2 = city((*i2).idx, abs((*i2).h - c[i].h), 0);
        } else if (i3 == s.begin()) {
            i4 = i3, i4++;
            c3 = city((*i3).idx, abs((*i3).h - c[i].h), 1);
            c4 = city((*i4).idx, abs((*i4).h - c[i].h), 1);
        } else {
            i2 = i3, i2--;
            i1 = i2, i1--;
            i4 = i3, i4++;
            c2 = city((*i2).idx, abs((*i2).h - c[i].h), 0);
            c3 = city((*i3).idx, abs((*i3).h - c[i].h), 1);
            if (i2 != s.begin()) c1 = city((*i1).idx, abs((*i1).h - c[i].h), 0);
            if (i4 != s.end())   c4 = city((*i4).idx, abs((*i4).h - c[i].h), 1);
        }
        city t[15];
        t[0] = c1, t[1] = c2, t[2] = c3, t[3] = c4;
        sort(t, t + 4);
        blue[i] = t[0].idx;
        red[i] = t[1].idx;
        s.insert(c[i]);
    }

    for (int i = 1; i <= n; i++) {
        f[i][0] = red[i];
        if (f[i][0] == 0) dA[i][0] = dB[i][0] = inf;
        else dA[i][0] = abs(c[red[i]].h - c[i].h);
    }
    for (int i = 1; i <= n; i++) {
        f[i][1] = blue[f[i][0]];
        if (f[i][1] == 0) {
            dA[i][1] = dB[i][1] = inf;
        } else {
            dA[i][1] = dA[i][0];
            dB[i][1] = abs(c[f[i][1]].h - c[f[i][0]].h);
        }
    }
    for (int j = 2; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            if (f[i][j] == 0) {
                dA[i][j] = dB[i][j] = inf;
            } else {
                dA[i][j] = dA[i][j - 1] + dA[f[i][j - 1]][j - 1];
                dB[i][j] = dB[i][j - 1] + dB[f[i][j - 1]][j - 1];
            }
        }
    }

    scanf("%d", &x1);
    int minid = (*(--s.end())).idx;
    double minslp = inf;
    for (int i = 1; i <= n; i++) {
        ll disA, disB;
        disA = disB = 0;
        int cur = i;
        int x0 = x1;
        double slp = inf;
        for (int j = 20; j >= 0; j--) {
            if (dA[cur][j] + dB[cur][j] <= x0) {
                while (x0 >= dA[cur][j] + dB[cur][j]) {
                    x0 -= dA[cur][j] + dB[cur][j];
                    disA += dA[cur][j];
                    disB += dB[cur][j];
                    cur = f[cur][j];
                }
            }
        }
        if (disB == 0) slp = inf;
        else slp = double(disA) / double(disB);
        if (slp < minslp) {
            minslp = slp;
            minid = i;
        } else if (fabs(slp - minslp) <= 1e-9) {
            if (c[i].h > c[minid].h) {
                minslp = slp;
                minid = i;
            }
        }
    }
    printf("%d\n", minid);
    scanf("%d", &m);
    while (m--) {
        int si, xi;
        scanf("%d%d", &si, &xi);
        ll disA, disB;
        disA = disB = 0;
        int cur = si;
        for (int j = 20; j >= 0; j--) {
            if (dA[cur][j] + dB[cur][j] <= xi) {
                while (xi >= dA[cur][j] + dB[cur][j]) {
                    xi -= dA[cur][j] + dB[cur][j];
                    disA += dA[cur][j];
                    disB += dB[cur][j];
                    cur = f[cur][j];
                }
            }
        }
        printf("%lld %lld\n", disA, disB);
    }
    return 0;
}

0

linhui LV 9 @ 8 年前

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int M = 100005;
const double INF = 0x7fffffff;
typedef long long LL;

struct City{
int h, id;
City *r, *l;
City(int a=0, int b=0):h(a), id(b){}
bool operator < (const City& x) const{
return h < x.h;
}
}c[M], bri[6];

bool cmp(City a, City b){
if(abs(a.h) == abs(b.h))
return a.h < b.h;
return abs(a.h) < abs(b.h);
}

int n;
int f[M][20], pos[M], to[M], to2[M], f_b[M], h[M];
LL fa[M][20], fb[M][20];

void add(City& a, City& b){
b.r = a.r;
a.r = &b;
b.l = &a;
}

void delet(City& x){
if(x.r != NULL) x.r->l = x.l;
if(x.l != NULL) x.l->r = x.r;
}

void init(){
sort(c+1, c+1+n);
c[1].l = c[1].r = NULL;
for(int i = 1; i < n; i++)
add(c[i], c[i+1]); //构建双向链表
for(int i = 1; i <= n; i++)
pos[c[i].id] = i; //pos[i]: i 在双向链表中的位置
for(int po = 1; po <= n; po++){ //从1到n找下一个位置,找完删除
int cnt = 0, i = pos[po];
//找海拔较低的
for(City* q = c[i].l; q != NULL && cnt < 2; q = q->l)
if(q->id > c[i].id)
bri[++cnt] = City(q->h - c[i].h, q->id);
//找海拔较高的
int lim = cnt + 1;
for(City* q = c[i].r; q != NULL && cnt <= lim; q = q->r)
if(q->id > c[i].id)
bri[++cnt] = City(q->h - c[i].h, q->id);
if(cnt >= 2) sort(bri+1, bri+1+cnt, cmp);//排序
if(cnt >= 2) fa[po][0] = abs(bri[2].h), to2[po] = bri[2].id;//倍增
if(cnt >= 1) fb[po][0] = abs(bri[1].h), to[po] = bri[1].id;
delet(c[i]);//delet po
}
for(int i = 1; i <= n; i++) f_b[i] = fb[i][0];
for(int i = 1; i <= n; i++){
f[i][0] = to[to2[i]];
fb[i][0] = f_b[to2[i]];
}
for(int j = 1; j <= 19; j++)//倍增
for(int i = 1; i <= n; i++){
f[i][j] = f[f[i][j-1]][j-1];//f记录a走的下一个地点，因为a先走，可能多走一步
fa[i][j] = fa[i][j-1] + fa[f[i][j-1]][j-1];
fb[i][j] = fb[i][j-1] + fb[f[i][j-1]][j-1];
}
}

void solve(){
int x0, ans = 1;
scanf("%d", &x0);
long double mins = INF;
for(int i = 1; i <= n; i++){
int x = i;
LL t1 = 0, t2 = 0;
double res = 0;
for(int j = 19; j >= 0; j--)
if(f[x][j] && t1 + t2 + fa[x][j] + fb[x][j] <= x0){
t1 += fa[x][j];
t2 += fb[x][j];
x = f[x][j];
}
if(t1 + t2 + fa[x][0] <= x0) t1 += fa[x][0];
if(t2 == 0) res = INF;
else res = (double)t1 / (double)t2;
if(res < mins || (res == mins && h[ans] < h[i])){
mins = res;
ans = i;
}
}
printf("%d\n", ans);
}

void clac(int s, int x){
LL t1 = 0, t2 = 0;
for(int j = 19; j >= 0; j--)
if(f[s][j] && t1 + t2 + fa[s][j] + fb[s][j] <= x){
t1 += fa[s][j];
t2 += fb[s][j];
s = f[s][j];
}
if(t1 + t2 + fa[s][0] <= x) t1 += fa[s][0];
printf("%lld %lld\n", t1, t2);
}

void solve2(){
int m;
scanf("%d", &m);
for(int i = 1; i <= m; i++){
int s, x;
scanf("%d%d", &s, &x);
clac(s, x);
}
}

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &c[i].h);
h[i] = c[i].h, c[i].id = i;
}
init();
solve();
solve2();
return 0;
}
链表 + 倍增

0

noip111 LV 7 @ 8 年前

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
const int maxn = 200000+10;
typedef long long LL;
//next1,next2表示i位置的第一近的位置号和第二位置号
int g[maxn][20+2],next1[maxn],next2[maxn];
LL len1[maxn],len2[maxn]; //表示位置i第一近和第二近的路程
LL lenA,lenB; //lenA表示A走的总路程 lenB表示B走的总路程
int n,m,i,j;
struct road
{
LL A,B;
//重载运算符+
road operator +(const road &a)
{

road c;
c.A = A + a.A;
c.B = B + a.B;
return c;
}
}f[maxn][20+2];
struct Point
{
int id, h; //位置号和高度值
//重载比较运算符
bool operator<(const Point &a) const
{
return h < a.h;
}
}p[maxn];
//定义多关键字集合
multiset<Point> S;
//定义多关键字集合的一个变量
multiset<Point>::iterator it;
//更新数组i的 next1 和 next2 与j的位置
void updata(int i ,int h,int j,int h2)
{
if (!next1[i])
{
next1[i] = j;
len1[i]= abs(h-h2);
return ;
}
if ((abs(h-h2) == len1[i] && p[next1[i]].h > h2)
|| (abs(h-h2) < len1[i]))
{
next2[i] = next1[i];
len2[i] = len1[i];

next1[i] = j;
len1[i] = abs(h-h2);

return ;

}
if (!next2[i])
{
next2[i] = j;
len2[i]= abs(h-h2);
return ;
}
if ((abs(h-h2)== len2[i] && p[next1[i]].h > h2)
|| (abs(h-h2) < len2[i]))
{
next2[i]= j;
len2[i] = abs(h-h2);
}
}
//询问从st位置出发a和b走的总路程不超过len 存储的路程为lenA和lenB
void ask(int st,LL len)
{
for (int j = 20; j >=0; j--)
{
if (g[st][j]!=0 && f[st][j].A+f[st][j].B<=len)
{
len -= (f[st][j].A+f[st][j].B);
lenA+=f[st][j].A;
lenB+=f[st][j].B;
st = g[st][j];

}
}
if (next2[st] && len>=len2[st])
lenA +=len2[st];
}

int main()
{
cin>>n;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &p[i].h);
p[i].id = i;
}
for (int i = n; i>=1; --i)
{
//查找节点p[i]在升序中的位置
it = S.lower_bound(p[i]);
if (it != S.end()) //不是末尾
updata(i , p[i].h, it->id, it->h);

if (it != S.end()) //不是末尾
{
it++; //访问后一个

if (it != S.end())
updata(i , p[i].h, it->id, it->h);
it--;
}

if (it != S.begin())
{
it--;
updata(i , p[i].h, it->id, it->h);
}
if (it != S.begin())
{
it--;
updata(i , p[i].h, it->id, it->h);
}
S.insert(p[i]);
}

for (int i = 1; i <= n;++i)
{
//倍增关系是A走2个位置B走一个位置
g[i][0] = next1[next2[i]];
f[i][0].A =len2[i];
f[i][0].B =len1[next2[i]];
}
for (int i = 1; i <= 20; ++i)
for (int j = 1; j <= n;++j)
{
//倍增
g[j][i] = g[g[j][i-1]][i-1];

f[j][i]= f[j][i-1]+ f[g[j][i-1]][i-1];
}
LL x;
cin>>x;
LL ansA = (LL)round(10e9);
LL ansB = 0;
int Pos = 0;
//从i号出发走的路程为x
for (int i = 1; i <= n;++i)
{

lenA = lenB = 0;
ask(i,x);

if (lenB != 0)
{
//存储lenA/lenB的比值最小
if (Pos ==0 || ansA*lenB > lenA * ansB)

{
Pos = i;
ansA = lenA;
ansB = lenB;
}
}
}
cout << Pos << endl;
cin>>m;
for (int i = 1; i <= m; ++i)
{
int st;
scanf("%d %d",&st,&x);
lenA = lenB = 0;
ask(st,x);
cout<<lenA<<" "<<lenB <<endl;
}
return 0;
}

0

caesar_199 LV 9 @ 8 年前

调了半个小时发现错因是我把城市从零开始编号但是输入输出的时候忘了转换。。。真的是哭都哭不出来了

0

abclzr LV 8 @ 8 年前

http://www.cnblogs.com/abclzr/p/5859446.html

0

三次元❤堕天逗比 LV 10 @ 9 年前

测试数据 #0: WrongAnswer, time = 0 ms, mem = 28692 KiB, score = 0

测试数据 #1: WrongAnswer, time = 15 ms, mem = 28688 KiB, score = 0

测试数据 #2: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #3: WrongAnswer, time = 0 ms, mem = 28692 KiB, score = 0

测试数据 #4: WrongAnswer, time = 0 ms, mem = 28692 KiB, score = 0

测试数据 #5: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #6: WrongAnswer, time = 15 ms, mem = 28688 KiB, score = 0

测试数据 #7: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #8: WrongAnswer, time = 15 ms, mem = 28692 KiB, score = 0

测试数据 #9: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #10: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #11: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #12: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #13: WrongAnswer, time = 0 ms, mem = 28692 KiB, score = 0

测试数据 #14: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #15: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #16: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #17: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #18: WrongAnswer, time = 0 ms, mem = 28688 KiB, score = 0

测试数据 #19: WrongAnswer, time = 0 ms, mem = 28692 KiB, score = 0

WrongAnswer, time = 45 ms, mem = 28692 KiB, score = 0

这时间，这结果

0

function2 LV 10 @ 9 年前

预处理可以不用平衡树，排个序+双向链表就能搞定~

0

renxuandi LV 10 @ 10 年前

由于VJ的数据加强过，set会TLE。。。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int Maxn=1e5+19;
typedef long long LL;
typedef int node[Maxn];
typedef pair<LL,int> PII;
typedef int Array[Maxn][21];
int n,m,x0,X,s,Ans;
int A[Maxn],Bnxt[Maxn];
double Dis=1e70,Hi;
Array Da,Db,to;

int f,c;
inline void Read(int &x)
{
while (!isdigit(c=getchar())&&c!='-');
if (c=='-') f=1,x=0;else f=0,x=c-'0';
while (isdigit(c=getchar())) x=x*10+c-'0';
if (f) x=-x;
}

int rt;
struct SBT
{
int cnt;
node Lsn,Rsn,s;
PII key[Maxn];

inline void Update(int x) {s[x]=s[Lsn[x]]+s[Rsn[x]]+1;}
inline void R_Rot(int &x)
{
int k=Lsn[x];Lsn[x]=Rsn[k];Rsn[k]=x;
s[k]=s[x];Update(x);x=k;
}
inline void L_Rot(int &x)
{
int k=Rsn[x];Rsn[x]=Lsn[k];Lsn[k]=x;
s[k]=s[x];Update(x);x=k;
}
inline void Maintain(int &x,int Flag)
{
if (!Flag)
if (s[Lsn[Lsn[x]]]>s[Rsn[x]]) R_Rot(x);
else if (s[Rsn[Lsn[x]]]>s[Rsn[x]]) L_Rot(Lsn[x]),R_Rot(x);else return;
else if (s[Rsn[Rsn[x]]]>s[Lsn[x]]) L_Rot(x);
else if (s[Lsn[Rsn[x]]]>s[Lsn[x]]) R_Rot(Rsn[x]),L_Rot(x);else return;
Maintain(Lsn[x],0);Maintain(Rsn[x],1);
Maintain(x,1);Maintain(x,0);
}
inline void insert(int &x,PII v)
{
if (!x) {x=++cnt,key[x]=v,s[x]=1;return;}
s[x]++;
insert(v<key[x]?Lsn[x]:Rsn[x],v);
Maintain(x,v>=key[x]);
}
inline int find(PII v)
{
int x=rt;
while (1)
{
if (key[x]==v) return x;
x=(v<key[x]?Lsn[x]:Rsn[x]);
}
}
inline PII pre(int x,PII v)
{
if (!x) return v;
if (v<=key[x]) return pre(Lsn[x],v);
else {PII tmp=pre(Rsn[x],v);return tmp==v?key[x]:tmp;}
}
inline PII nxt(int x,PII v)
{
if (!x) return v;
if (v>=key[x]) return nxt(Rsn[x],v);
else {PII tmp=nxt(Lsn[x],v);return tmp==v?key[x]:tmp;}
}
} S;

int main()
{
freopen("drive.in","r",stdin);
freopen("drive.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) Read(A[i]);
S.insert(rt,make_pair(1LL<<60,0));
S.insert(rt,make_pair(-(1LL<<60),0));
for (int i=n;i>=1;i--)
{
PII x=make_pair(1LL*A[i],i);int k;
S.insert(rt,x);
PII L=S.pre(rt,x),R=S.nxt(rt,x),T;
if (i==n) continue;
if (i==n-1) {Bnxt[i]=n;continue;}
if (abs(L.first-A[i])<=abs(R.first-A[i]))
{
Bnxt[i]=L.second;T=S.pre(rt,L);
k=(abs(T.first-A[i])<=abs(R.first-A[i])?T.second:R.second);
} else
{
Bnxt[i]=R.second;T=S.nxt(rt,R);
k=(abs(L.first-A[i])<=abs(T.first-A[i])?L.second:T.second);
}
to[i][1]=Bnxt[k];
Da[i][1]=abs(A[k]-A[i]);
Db[i][1]=(k?abs(A[k]-A[Bnxt[k]]):0);
}
for (int x=2;x<=20;x++)
for (int i=1;i<=n;i++)
{
int p=to[i][x-1];
to[i][x]=to[p][x-1];
Da[i][x]=Da[i][x-1]+Da[p][x-1];
Db[i][x]=Db[i][x-1]+Db[p][x-1];
}
scanf("%d",&x0);
for (int y=1;y<=n;y++)
{
int s=y,X=x0,Aa=0,Ab=0;
for (int i=20;i>=1;i--)
if (to[s][i]&&Da[s][i]+Db[s][i]<=X)
{
Aa+=Da[s][i],Ab+=Db[s][i];
X-=Da[s][i]+Db[s][i];
s=to[s][i];
}
if (Da[s][1]<=X) Aa+=Da[s][1];
double x=(!Ab?1e60:(1.0*Aa)/(1.0*Ab));
if (x<Dis-1e-9||fabs(x-Dis)<1e-9&&A[y]>Hi) Dis=x,Hi=A[y],Ans=y;
}
printf("%d\n",Ans);
scanf("%d",&m);
while (m--)
{
Read(s),Read(X);
int Aa=0,Ab=0;
for (int i=20;i>=1;i--)
if (to[s][i]&&Da[s][i]+Db[s][i]<=X)
{
Aa+=Da[s][i],Ab+=Db[s][i];
X-=Da[s][i]+Db[s][i];
s=to[s][i];
}
if (Da[s][1]<=X) Aa+=Da[s][1];
printf("%d %d\n",Aa,Ab);
}
}

0

fan_hd LV 8 @ 10 年前

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=~0U>>2;
int n;
struct High
{
int ord,Val;
}R[100005];
int H[100005];
struct List
{
int Val,next,last;
}L[100005];
inline bool Cmp(const High& A,const High& B)
{
return A.Val<B.Val;
}
struct Tree
{
int S_A,S_B;
int C_A,C_B;
int S[18],CA[18],CB[18];
}T[100005];
inline void Build(int Pc,int Pr)
{
T[Pc].C_A=T[Pc].C_B=INF;
if (L[Pr].last)
if (H[Pc]-H[L[L[Pr].last].Val]<T[Pc].C_B)
T[Pc].S_B=L[L[Pr].last].Val,T[Pc].C_B=H[Pc]-H[L[L[Pr].last].Val];
if (L[Pr].next)
if (H[L[L[Pr].next].Val]-H[Pc]<T[Pc].C_B)
T[Pc].S_B=L[L[Pr].next].Val,T[Pc].C_B=H[L[L[Pr].next].Val]-H[Pc];
if (T[Pc].S_B)
{
if (L[Pr].last)
{
if (L[L[Pr].last].Val!=T[Pc].S_B)
T[Pc].S_A=L[L[Pr].last].Val,T[Pc].C_A=H[Pc]-H[L[L[Pr].last].Val];
if (L[L[Pr].last].last && L[L[Pr].last].Val==T[Pc].S_B)
T[Pc].S_A=L[L[L[Pr].last].last].Val,T[Pc].C_A=H[Pc]-H[T[Pc].S_A];
}
if (L[Pr].next)
{
if (L[L[Pr].next].Val!=T[Pc].S_B)
if (H[L[L[Pr].next].Val]-H[Pc]<T[Pc].C_A)
T[Pc].S_A=L[L[Pr].next].Val,T[Pc].C_A=H[L[L[Pr].next].Val]-H[Pc];
if (L[L[Pr].next].next && L[L[Pr].next].Val==T[Pc].S_B)
if (H[L[L[L[Pr].next].next].Val]-H[Pc]<T[Pc].C_A)
T[Pc].S_A=L[L[L[Pr].next].next].Val,T[Pc].C_A=H[L[L[L[Pr].next].next].Val]-H[Pc];
}
}
if (L[Pr].last) L[L[Pr].last].next=L[Pr].next;
if (L[Pr].next) L[L[Pr].next].last=L[Pr].last;
}
int Find(int x)
{
int l=1,r=n,mid;
while (l<r-1)
{
mid=(l+r)>>1;
if (R[mid].Val<x) l=mid;
else r=mid;
}
for (int i=l;i<=r;i++)
if (R[i].Val==x) return i;
}
void Double_Inc(int Ps)
{
T[Ps].S[0]=T[T[Ps].S_A].S_B;
T[Ps].CA[0]=T[Ps].C_A;
T[Ps].CB[0]=T[T[Ps].S_A].C_B;
for (int i=1;i<18;i++)
{
T[Ps].S[i]=T[T[Ps].S[i-1]].S[i-1];
T[Ps].CA[i]=T[Ps].CA[i-1]+T[T[Ps].S[i-1]].CA[i-1];
T[Ps].CB[i]=T[Ps].CB[i-1]+T[T[Ps].S[i-1]].CB[i-1];
}
}
pair<int,int> Get_Ans(int P,int x)
{
int D_A=0,D_B=0;
int V=17;
while (true)
{
while ((T[P].S[V]==0 || T[P].CA[V]+T[P].CB[V]>x) && V>=0) V--;
if (V>=0) D_A+=T[P].CA[V],D_B+=T[P].CB[V],x-=T[P].CA[V]+T[P].CB[V],P=T[P].S[V];
else break;
}
if (T[P].S_A && T[P].C_A<=x) D_A+=T[P].C_A;
return pair<int,int>(D_A,D_B);
}
inline double Calc(int A,int B)
{
if (B==0) return 1000000000.0;
return (double)A/B;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",H+i),R[i].Val=H[i],R[i].ord=i;
sort(R+1,R+n+1,Cmp);
for (int i=1;i<=n;i++) L[i].Val=R[i].ord;
for (int i=1;i<n;i++) L[i].next=i+1;
for (int i=2;i<=n;i++) L[i].last=i-1;
for (int i=1;i<=n;i++) Build(i,Find(H[i]));
for (int i=n;i;i--) Double_Inc(i);
int X0;
scanf("%d",&X0);
int ans;
double Cur=10000000000.0;
for (int i=n;i;i--)
{
pair<int,int> T=Get_Ans(R[i].ord,X0);
if (Calc(T.first,T.second)<Cur-1e-8) ans=R[i].ord,Cur=Calc(T.first,T.second);
}
printf("%d\n",ans);
int m;
scanf("%d",&m);
for (int i=1,p,x;i<=m;i++)
{
scanf("%d%d",&p,&x);
pair<int,int> T=Get_Ans(p,x);
printf("%d %d\n",T.first,T.second);
}
return 0;
}

0

绿色的云 LV 10 @ 11 年前

终于过了~~
编译成功

foo.cpp: In function 'int WORK1()':
foo.cpp:269:1: warning: no return statement in function returning non-void [-Wreturn-type]
测试数据 #0: Accepted, time = 31 ms, mem = 49852 KiB, score = 5
测试数据 #1: Accepted, time = 31 ms, mem = 49856 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 49856 KiB, score = 5
测试数据 #3: Accepted, time = 31 ms, mem = 49860 KiB, score = 5
测试数据 #4: Accepted, time = 31 ms, mem = 49856 KiB, score = 5
测试数据 #5: Accepted, time = 31 ms, mem = 49856 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 49864 KiB, score = 5
测试数据 #7: Accepted, time = 31 ms, mem = 49864 KiB, score = 5
测试数据 #8: Accepted, time = 31 ms, mem = 49864 KiB, score = 5
测试数据 #9: Accepted, time = 31 ms, mem = 49864 KiB, score = 5
测试数据 #10: Accepted, time = 31 ms, mem = 49900 KiB, score = 5
测试数据 #11: Accepted, time = 46 ms, mem = 49900 KiB, score = 5
测试数据 #12: Accepted, time = 31 ms, mem = 49900 KiB, score = 5
测试数据 #13: Accepted, time = 46 ms, mem = 49892 KiB, score = 5
测试数据 #14: Accepted, time = 250 ms, mem = 52204 KiB, score = 5
测试数据 #15: Accepted, time = 312 ms, mem = 52204 KiB, score = 5
测试数据 #16: Accepted, time = 625 ms, mem = 53624 KiB, score = 5
测试数据 #17: Accepted, time = 609 ms, mem = 54088 KiB, score = 5
测试数据 #18: Accepted, time = 718 ms, mem = 54556 KiB, score = 5
测试数据 #19: Accepted, time = 687 ms, mem = 54552 KiB, score = 5
Accepted, time = 3665 ms, mem = 54556 KiB, score = 100
发一下题解：
http://hi.baidu.com/vporvgjwxchmpwe/item/651f91edf52a642d6cabb818

-1

noip111 LV 7 @ 8 年前

其实很简单，不是很难的。
用一点数据结构，就解决了。

-1

noip111 LV 7 @ 8 年前

#1
AC
1ms/9398kB

#2
AC
1ms/9398kB

#3
AC
2ms/9398kB

#4
AC
1ms/106449kB

#5
AC
2ms/9398kB

#6
AC
1ms/9398kB

#7
AC
1ms/9410kB
#8
AC
2ms/9406kB

#9
AC
4ms/106449kB

#10
AC
3ms/106449kB

#11
AC
16ms/106449kB

#12
AC
19ms/9480kB

#13
AC
16ms/9492kB

#14
AC
20ms/106449kB
#15
AC
163ms/108640kB

#16
AC
171ms/35515kB

#17
AC
435ms/110058kB

#18
AC
442ms/110445kB

#19
AC
517ms/110960kB

#20
AC
546ms/110960kB

-1

huangxin LV 8 @ 11 年前

郁闷的wa了20分

测试数据 #0: Accepted, time = 0 ms, mem = 36836 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 36836 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 36836 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 36832 KiB, score = 5
测试数据 #4: WrongAnswer, time = 0 ms, mem = 36836 KiB, score = 0
测试数据 #5: Accepted, time = 0 ms, mem = 36832 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 36836 KiB, score = 5
测试数据 #7: Accepted, time = 15 ms, mem = 36832 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 36832 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 36832 KiB, score = 5
测试数据 #10: Accepted, time = 31 ms, mem = 36836 KiB, score = 5
测试数据 #11: Accepted, time = 31 ms, mem = 36832 KiB, score = 5
测试数据 #12: Accepted, time = 15 ms, mem = 36832 KiB, score = 5
测试数据 #13: Accepted, time = 31 ms, mem = 36836 KiB, score = 5
测试数据 #14: WrongAnswer, time = 187 ms, mem = 36832 KiB, score = 0
测试数据 #15: WrongAnswer, time = 234 ms, mem = 36832 KiB, score = 0
测试数据 #16: Accepted, time = 515 ms, mem = 36832 KiB, score = 5
测试数据 #17: WrongAnswer, time = 625 ms, mem = 36832 KiB, score = 0
测试数据 #18: Accepted, time = 625 ms, mem = 36832 KiB, score = 5
测试数据 #19: Accepted, time = 484 ms, mem = 36832 KiB, score = 5
WrongAnswer, time = 2823 ms, mem = 36836 KiB, score = 80

-1

绿色的云 LV 10 @ 11 年前

由于这道题只过了NOIP的数据，VJ还是过不来，就只说说思路：
由于Hi各不相同，所以可以使用平衡树来预处理每个城市最近和第二近的城市，从东往西向平衡树中加入城市，在假如前顺便查询每个城市各自在两人开车的情况下到达的下一个城市。
第二步预处理:倍增算法
f[0][i][j]表示在A先开车的情况下从i出发，经过2^j步到达的城市
f[1][i][j]表示在A先开车的情况下从i出发，经过2^j步到达的城市
可得状态转移方程：
j=1
f[0][i][j]=f[1][f[0][i][j-1]][j-1];
f[1][i][j]=f[0][f[0][i][j-1]][j-1];
j>1
f[0][i][j]=f[0][f[0][i][j-1]][j-1];
f[1][i][j]=f[1][f[1][i][j-1]][j-1];
然后要查询时递归查询即可
预处理复杂度O(n log n)
查询复杂度O(m log n)

-2

td650739 LV 8 @ 11 年前

Q_Q 木有题解

Silence•轩辕•寂 @ 11 年前

oooO ↘┏━┓ ↙ Oooo
( 踩)→┃你┃ ←(死 )
\ ( →┃√┃ ← ) /
　 _)↗┗━┛ ↖(_/

-2

czmp LV 8 @ 12 年前

SOFA

absi2011 @ 11 年前

差评
lrj124 @ 8 年前

差评

题解

20 条题解

开车旅行

信息

状态

开发

支持

题解

20 条题解

开车旅行

信息

状态

开发

支持

还没有账户？

登录