HGOI 20191030am 题解

Problem A 腿部挂件

　　给出$n$个数的序列$a_i$,支持$T$次操作。

　　每次操作形如$x , l , r$，计算$\max_{i = l}^{r} (a_i \oplus x)$的值。

　　对于$100\%$的数据满足$1 \leq n \leq 2 \times 10^5 , 0 \leq a_i \leq 10^9$

Solution ：

　　通常可以使用可持久化字典树求解，但是这里可以用字典树套vector来做。

　　这样当当前节点vector有一个在$l,r$的数中就往下走，还是按照以前的贪心策略，从高位到低位贪心。

　　这样做的时间复杂度是$O(n {log_2} ^2 n)$

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

struct node

{

    vector<int>p;

    int ls,rs;

    node(){ls=rs=-;}

}tr[];

int n,m,a,x,y,cnt,o[];

void push(int k,int p)

{

    for(int i=-,nw=;i>=;i--)

    {

        if(k&o[i])

        {

            if(tr[nw].ls==-)tr[nw].ls=++cnt;

            nw=tr[nw].ls;

        }

        else

        {

            if(tr[nw].rs==-)tr[nw].rs=++cnt;

            nw=tr[nw].rs;

        }

        tr[nw].p.pb(p);

    }

}

int query(int k,int l,int r)

{

    int ans=;

    for(int i=-,nw=;i>=;i--)

    {

        if(k&o[i])

        {

            if(tr[nw].rs==-||*(tr[tr[nw].rs].p.end()-)<l||*lower_bound(tr[tr[nw].rs].p.begin(),tr[tr[nw].rs].p.end(),l)>r)

                nw=tr[nw].ls,ans+=o[i];

            else nw=tr[nw].rs;

        }

        else

        {

            if(tr[nw].ls==-||*(tr[tr[nw].ls].p.end()-)<l||*lower_bound(tr[tr[nw].ls].p.begin(),tr[tr[nw].ls].p.end(),l)>r)

                nw=tr[nw].rs;

            else nw=tr[nw].ls,ans+=o[i];

        }

    }

    return ans^k;

}

int main()

{

    freopen("hugclose.in","r",stdin);

    freopen("hugclose.out","w",stdout);

    scanf("%d%d",&n,&m),o[]=cnt=;

    for(int i=;i<;i++)o[i]=o[i-]*;

    for(int i=;i<=n;i++)scanf("%d",&a),push(a,i);

    for(int i=;i<=m;i++)scanf("%d%d%d",&a,&x,&y),printf("%d\n",query(a,x+,y+));

    return ;

}

hugclose.cpp

Problem B 走夜路

　　一条直线上有n+1个充电站，一开始你在第一个充电站，每个充电站都能以某个代价充电

　　每走一个单位距离就要耗费一单位电，求按顺序走完所有充电站的最小代价

　　对于$100\%$的数据满足$1 \leq n \leq 5\times 10^5$

Solution :

　　考虑一种贪心，依次考虑每一个充电站。

　　下一个充电站优先级从高到低依次是：

当前充电站以后第一个费用小于当前充电站(此时，直接在当前充电站充满恰好能到下个充电站的电，然后直接走到那个充电站即可)
终点(如果当前充电站冲一定的点之后能到终点，那么就直接到达终点)
在充满电后能走到的所有充电站中，费用最小的充电站(此时需要先在当前充电站充满电后再移动)

　　可以考虑使用单调栈来求对于每个位置右侧第一个小于它的数，(从前往后加入数，满足栈单调增，弹栈的时候记录即可)

　　然后再使用小常数的$st$表来求出静态区间最小值并且维护标号。

　　所以，本题就是$O(n log_2 n)$的复杂度了。

#pragma GCC optimize(3)

# include <bits/stdc++.h>

using namespace std;

const int N=+;

int st[<<][],id[<<][];

# define int long long

int n,T,d[N],a[N],r[N];

stack<int>s;

int dist(int x,int y) { if (x>y) swap(x,y); return d[y-]-d[x-];}

namespace fast_IO{

    const int IN_LEN = , OUT_LEN = ;

    char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf + IN_LEN, *oh = obuf, *lastin = ibuf + IN_LEN, *lastout = obuf + OUT_LEN - ;

    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, , IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}

    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, , oh - obuf, stdout), oh = obuf; *oh ++= x;}

    inline void flush(){fwrite(obuf, , oh - obuf, stdout);}

    int read(){

        int x = ; int zf = ; char ch = ' ';

        while (ch != '-' && (ch < '' || ch > '')) ch = getchar_();

        if (ch == '-') zf = -, ch = getchar_();

        while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar_(); return x * zf;

    }

    void write(int x){

        if (x < ) putchar_('-'), x = -x;

        if (x > ) write(x / );

        putchar_(x %  + '');

    }

}

using namespace fast_IO;

void build() {

    memset(st,0x3f,sizeof(st));

    for (int i=;i<=n;i++) st[i][]=a[i],id[i][]=i;

    for (int i=;i<=;i++)

        for (int j=;j<=n;j++)

            if (st[j][i-]<st[j+(<<(i-))][i-]) {

                st[j][i] = st[j][i-];

                id[j][i] = id[j][i-];

            } else {

                st[j][i] = st[j+(<<(i-))][i-];

                id[j][i] = id[j+(<<(i-))][i-];

            }

}

int LOG[N];

int query(int l,int r) {

    int k=LOG[r-l+];

    if (st[l][k] < st[r-(<<k)+][k]) return id[l][k];

    else return id[r-(<<k)+][k];

}

signed main()

{

    n=read();T=read();

    for (int i=;i<=n;i++) LOG[i] = log2(i);

    for (int i=;i<=n;i++) d[i]=read(),a[i]=read();

    build();

    while (!s.empty()) s.pop();

    for (int i=n;i>=;i--) {

        while (!s.empty()&&a[s.top()]>=a[i]) s.pop();

        if (s.empty()) r[i]=n; else r[i]=s.top()-;

        s.push(i);

    }

    for (int i=;i<=n;i++)

        r[i] = (r[i]==n)?(-):(r[i]+),

        d[i] += d[i-];

    int now = , res = ;

    int cost = ;

    while (true) {

        if (r[now]!=- && dist(r[now] , now) <= T) {

            if (res >= dist(r[now], now)) res-=dist(r[now],now);

            else  cost +=  1ll * a[now]*(dist(r[now], now)-res),res = ;

            now = r[now];

        } else if (dist(n+,now) <= T) {

            if (res >= dist(n+, now)) res-=dist(n+,now);

            else cost += 1ll * a[now]*(dist(n+,now)-res),res = ;

            break;

        } else {

            cost += 1ll * (T-res)*a[now];

            int l = now+, r = n , ans = -;

            while (l<=r) {

                int mid = (l+r) >> ;

                if (dist(mid,now)<=T) ans=mid,l=mid+;

                else r = mid-;

            }

            if (ans == -) {

                write(-); flush(); return ;

            }

            int to = query(now+,ans);

            res = T - dist(to , now);

            now = to;

        }

    }

    write(cost);  flush();

    return ;

}

wayhome.cpp

Problem C 宝石专家

　给出$n$个数的序列$a_i$,处理$T$个询问,

　每个询问形如$l,r$，请输出在$a_l ... a_r$中两个相同的数的最近距离。

　若$a_x = a_y$，那么距离定义为$|x- y|$

　对于$100\%$的数据，满足$1 \leq n,T\leq 2 \times 10^5$

Solution :

　　首先，我们发现对于相同的数，在一些位置，只有相邻的两个数所构成的线段有意义。

　　所以需要处理的小线段长度在$n$这个级别。

　　我们考虑将操作离线，放在一个$[1,n]$的数轴上，并考虑从$n$到$1$依次扫。

　　如果当前遇到了一个小线段的左端点$l$，那么在线段树中$[r,n]$用这条线段的权值$r-l$来更新答案。

　　所以，线段树的意义是扫到当前位置，询问线段的右端点的答案。

　　所以，如果遇到一个询问线段，那么直接求出$[l,r]$的最小值即可，但是由于值的单调性，直接单点求出$r$的值即可。

　　时间复杂度就是$O(n log_2 n)$。

#pragma GCC optimize(3)

# include <bits/stdc++.h>

# define inf (0x3f3f3f3f)

using namespace std;

const int N = 2e5 + ;

vector<int>tmp;

vector<int>v[N];

vector< pair<int,int> >r[N],qes[N];

int n,m,a[N],ans[N];

namespace fast_IO{

    const int IN_LEN = , OUT_LEN = ;

    char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf + IN_LEN, *oh = obuf, *lastin = ibuf + IN_LEN, *lastout = obuf + OUT_LEN - ;

    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, , IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}

    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, , oh - obuf, stdout), oh = obuf; *oh ++= x;}

    inline void flush(){fwrite(obuf, , oh - obuf, stdout);}

    int read(){

        int x = ; int zf = ; char ch = ' ';

        while (ch != '-' && (ch < '' || ch > '')) ch = getchar_();

        if (ch == '-') zf = -, ch = getchar_();

        while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar_(); return x * zf;

    }

    void write(int x){

        if (x < ) putchar_('-'), x = -x;

        if (x > ) write(x / );

        putchar_(x %  + '');

    }

}

using namespace fast_IO;

struct Seg {

    int val,tag;

    Seg() { val = tag = inf;}

}tr[N<<];

# define lson ls,l,mid

# define rson rs,mid+,r

# define mid (l+r>>)

# define ls (x<<)

# define rs (x<<|)

void down(int x) {

    tr[ls].val=min(tr[ls].val,tr[x].tag);

    tr[rs].val=min(tr[rs].val,tr[x].tag);

    tr[ls].tag=min(tr[ls].tag,tr[x].tag);

    tr[rs].tag=min(tr[rs].tag,tr[x].tag);

    tr[x].tag = inf;

}

void update(int x,int l,int r,int opl,int opr,int val) {

    if (opl <= l && r <= opr) {

        tr[x].tag = min(tr[x].tag , val);

        tr[x].val = min(tr[x].val , val);

        return;

    }

    down(x);

    if (opl<=mid) update(lson,opl,opr,val);

    if (opr> mid) update(rson,opl,opr,val);

    tr[x].val = min(tr[ls].val , tr[rs].val);

}

int query(int x,int l,int r,int pos) {

    if (l == r) return tr[x].val;

    down(x);

    if (pos<=mid) return query(lson,pos);

    else return query(rson,pos);

}

int main()

{

    n=read();m=read();

    for (int i=;i<=n;i++) {

        tmp.push_back(a[i]=read());

    }

    sort(tmp.begin(),tmp.end());

    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());

    for (int i=;i<=n;i++) {

        a[i] = lower_bound(tmp.begin(),tmp.end(),a[i]) - tmp.begin()+;

        v[a[i]].push_back(i);

    }

    for (int i=;i<=n;i++) {

        if (v[i].size() < ) continue;

        for (int j=;j<v[i].size()-;j++)

            r[v[i][j]].push_back(make_pair(v[i][j+],v[i][j+]-v[i][j]));

    }

    for (int i=;i<=m;i++) {

        int l=read(),r=read();

        qes[l].push_back(make_pair(r,i));

    }

    for (int i=n;i>=;i--) {

        int sz = r[i].size();

        if (sz) {

            for (int j=;j<sz;j++)

                update(,,n,r[i][j].first,n,r[i][j].second);

        }

        sz = qes[i].size();

        if (sz) {

            for (int j=;j<sz;j++)

             ans[qes[i][j].second] = query(,,n,qes[i][j].first);

        }

    }

    for (int i=;i<=m;i++) {

        write((ans[i]>=inf)?-:ans[i]); putchar_('\n');

    }

    flush();

    return ;

}

jewel.cpp

巴特西

HGOI 20191030am 题解

最新文章

热门文章