absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] AGC010C
[破碎的状态] 主代码手的练习(北京赛区D)(hihoCoder 1630)

[破碎的状态] RQNOJ 707 [NOIP2012] 开车旅行

absi2011 posted @ Nov 09, 2017 05:51:15 PM in 刷题记录 with tags RQNOJ LCA NOIP 瞎搞 小高考 , 536 阅读

http://www.rqnoj.cn/problem/707

做法如下:

1,求每个点,A和B出发,会到哪里

这里可以用set做一下,也可以向我一样写个链表[Line 23-36/110-208]

类似线段树的东西,按高度排序,然后搞个链表,每次删掉一个点,然后找它左右的最小/最大

set和上面的差不多....不过复杂度会高一点,我这个是O(n)的,我怕set T掉了...

RQNOJ还是挺慢的

2,组建树

把每个点拆分成两个形态,一个是A开始走,一个是B开始走

建个图,发现是三个树(最后一个点/倒数第二个点A出发)

3,dfs,计算树上各点的权值(A走了多少/B走了多少),并倍增

4,每次询问一个距离和一个起点,这时候只要用倍增来判定一下是不是超过了(和二分差不多的样子)规定的距离就行了

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int next1[100005],next2[100005];
int h[100005];
struct place
{
    int height;
    int id;
    place * last;
    place * next;
    friend bool operator < (const place &a,const place &b)
    {
        return a.height<b.height;
    }
};
place t[100005];
place * null;
place * p[100005];
struct edge
{
    int y;
    edge * next;
};
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
edge * li[200005];
void insert_edge(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
long long sum[200005][2];
int up[200005][25];
void dfs(int x,int c)
{
    int i;
    for (i=1;i<19;i++)
    {
        if (up[x][i-1]==-1)
        {
            up[x][i]=-1;
        }
        else
        {
            up[x][i]=up[up[x][i-1]][i-1];
        }
    }
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        sum[t->y][!c]=sum[x][!c]+abs(h[t->y/2]-h[x/2]);
        sum[t->y][c]=sum[x][c];
        up[t->y][0]=x;
        dfs(t->y,!c);
    }
}
int q_ans1,q_ans2;
void query(int x,int s)
{
    if (sum[s][0]+sum[s][1]<=x)
    {
        q_ans1=sum[s][0];
        q_ans2=sum[s][1];
    }
    int now=s;
    int i;
    for (i=18;i>=0;i--)
    {
        if (up[now][i]==-1) continue;
        int t=up[now][i];
        if (sum[s][0]+sum[s][1]-sum[t][0]-sum[t][1]<=x)
        {
            now=t;
        }
    }
    q_ans1=sum[s][0]-sum[now][0];
    q_ans2=sum[s][1]-sum[now][1];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&h[i]);
        t[i].id=i;
        t[i].height=h[i];
    }
    sort(t,t+n);
    null=&t[n];
    for (i=0;i<n;i++)
    {
        if (i!=0)
        {
            t[i].last=&t[i-1];
        }
        else
        {
            t[i].last=null;
        }
        if (i!=n-1)
        {
            t[i].next=&t[i+1];
        }
        else
        {
            t[i].next=null;
        }
        p[t[i].id]=&t[i];
    }
    for (i=0;i<n;i++)
    {
        p[i]->last->next=p[i]->next;
        p[i]->next->last=p[i]->last;
        if (p[i]->next==null)
        {
            if (p[i]->last==null)
            {
                next1[i]=-1;
                next2[i]=-1;
                continue;
            }
            else
            {
                next1[i]=p[i]->last->id;
                p[i]->last=p[i]->last->last;
            }
        }
        else
        {
            if (p[i]->last==null)
            {
                next1[i]=p[i]->next->id;
                p[i]->next=p[i]->next->next;
            }
            else
            {
                if (p[i]->next->height-p[i]->height<p[i]->height-p[i]->last->height)
                {
                    next1[i]=p[i]->next->id;
                    p[i]->next=p[i]->next->next;
                }
                else
                {
                    next1[i]=p[i]->last->id;
                    p[i]->last=p[i]->last->last;
                }
            }
        }
        if (p[i]->next==null)
        {
            if (p[i]->last==null)
            {
                next2[i]=-1;
            }
            else
            {
                next2[i]=p[i]->last->id;
            }
        }
        else
        {
            if (p[i]->last==null)
            {
                next2[i]=p[i]->next->id;
            }
            else
            {
                if (p[i]->next->height-p[i]->height<p[i]->height-p[i]->last->height)
                {
                    next2[i]=p[i]->next->id;
                }
                else
                {
                    next2[i]=p[i]->last->id;
                }
            }
        }
    }
    for (i=0;i<n;i++)
    {
        if (next1[i]!=-1) insert_edge(next1[i]*2+1,i*2+0);
        if (next2[i]!=-1) insert_edge(next2[i]*2+0,i*2+1);
    }
    memset(up,-1,sizeof(up));
    dfs(n*2-1,1);
    dfs(n*2-2,0);
    if (n!=1) dfs(n*2-3,1);
    int x0;
    scanf("%d",&x0);
    int b_ans1=0,b_ans2=1,b_ans_id=0;
    for (i=0;i<n;i++)
    {
        query(x0,i*2+1);
        if ((q_ans1==0)&&(q_ans2==0)) continue;
        if ((long long)b_ans1*q_ans2<(long long)b_ans2*q_ans1)
        {
            b_ans_id=i;
            b_ans1=q_ans1;
            b_ans2=q_ans2;
        }
        else if ((long long)b_ans1*q_ans2==(long long)b_ans2*q_ans1)
        {
            if (h[i]>h[b_ans_id])
            {
                b_ans_id=i;
                b_ans1=q_ans1;
                b_ans2=q_ans2;
            } 
        }
    }
    printf("%d\n",b_ans_id+1);
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        int s,x;
        scanf("%d%d",&s,&x);
        s--;
        query(x,s*2+1);
        printf("%d %d\n",q_ans2,q_ans1);
    }
    return 0;
}
boardmodelpaper.com 说:
Jan 08, 2024 06:42:12 PM

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


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