hgoi#20191030

muronglin
muronglin 2019年10月30日
  • 在其它设备中阅读本文章

T1- 腿部挂件

给定一个长度为 n 的数组 进行 m 次询问,每次询问 l 到 r 的区间里 $a[i]\oplus x$ 的最大值

解法

如果没有 l,r 的限制,很容易想到 trie 树 那有 l,r 的限制怎么办呢 我们在 trie 树里套一个 vector,里面存这个子节点拥有的数的编号 在查找时,只有当这个子节点有在 l 到 r 内的点时才能往下走

ac 代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
struct node
{
    vector<int>p;
    int ls,rs;
    node(){ls=rs=-1;}
}tr[6100000];
int n,m,a,x,y,cnt,o[50];
void push(int k,int p)
{
    for(int i=30-1,nw=1;i>=0;i--)
    {
        if(k&o[i])
        {
            if(tr[nw].ls==-1)tr[nw].ls=++cnt;
            nw=tr[nw].ls;
        }
        else
        {
            if(tr[nw].rs==-1)tr[nw].rs=++cnt;
            nw=tr[nw].rs;
        }
        tr[nw].p.pb(p);
    }
}
int query(int k,int l,int r)
{
    int ans=0;
    for(int i=30-1,nw=1;i>=0;i--)
    {
        if(k&o[i])
        {
            if(tr[nw].rs==-1||(tr[tr[nw].rs].p.end()-1)<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==-1||(tr[tr[nw].ls].p.end()-1)<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[0]=cnt=1;
    for(int i=1;i<30;i++)o[i]=o[i-1]*2;
    for(int i=1;i<=n;i++)scanf("%d",&a),push(a,i);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&a,&x,&y),printf("%dn",query(a,x+1,y+1));
    return 0;
}

T2- 走夜路

一条直线上有 n + 1 个充电站,一开始你在第一个充电站,每个充电站都能以某个代价充电 每走一个单位距离就要耗费一单位电,求按顺序走完所有充电站的最小代价

解法

显然的一个贪心,对于一个点: 要么直接充满电,要么充电直到能走到下一个比它优的点 那怎么求下一个比它优的点呢,用二分,具体见代码

ac 代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define ls (nw*2)
#define rs (nw*2+1)
#define int long long
using namespace std;
int n,m,ans,d[500010],p[500010],s[500010],tr[2000010];
void build(int nw,int l,int r)
{
    if(l==r)tr[nw]=p[l];
    else
    {
        build(ls,l,mid);
        build(rs,mid+1,r);
        tr[nw]=min(tr[ls],tr[rs]);
    }
}
int query(int nw,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)return tr[nw];
    if(qr<=mid)return query(ls,l,mid,ql,qr);
    if(ql>mid)return query(rs,mid+1,r,ql,qr);
    return min(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
void check()
{
    for(int i=0;i<n;i++)
        if(d[i]>m)puts("-1"),exit(0);
}
signed main()
{
//  freopen("wayhome.in","r",stdin);
//  freopen("wayhome.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%lld%lld",&d[i],&p[i]),s[i+1]=s[i]+d[i];
    check(),build(1,1,n);
    for(int i=0,nw=0;i<n;i++)
    {
        int l=i+1,r=n,g;
        while(l<=r)
        {
            if(query(1,1,n,i+1,mid)<=p[i])
                g=mid,r=mid-1;
            else l=mid+1;
        }
        //查询第一个比它优的点是哪个
        //用线段树维护区间最小值(用ST表更优)
        //如果i+1到mid的区间内有比它优的点,mid就可以作为答案
        //二分求出最小的mid
        if(s[g]-s[i]>nw)
        {
            if(s[g]-s[i]>=m)ans+=(m-nw)*p[i],nw=m;
            else{ans+=(s[g]-s[i]-nw)*p[i],nw=0,i=g-1;continue;}
        }
        else{nw-=s[g]-s[i],i=g-1;continue;}
        nw-=d[i];
    }
    printf("%lldn",ans);
    return 0;
}

T3- 宝石专家

给定一个长度为 n 的数组 a 进行 m 次询问,每次询问在 l 到 r 的区间内 满足 $ a\_i = a\_j $ 且 $ i < j $ 的 $ j - i $ 的最小值

解法

先将问题转化,将相同的数全部提出来,答案一定是在相邻的两个相同的数处产生 如果一组相同的数有 x 个,可以转化成 x - 1 个区间 问题就变成了求在一个大区间内的最小区间 我们可以发现这些区间有一定的性质 以一个点为左端点或右端点时,最多只存在一个区间 然后可以分块做,f[i][j]表示 i 为左端点,j×K(每块长度)为右端点时的最小区间 f[i][j]可以由 f[i+1][j]和以 i 为左端点的区间转移过来 查询时将右端点分成两部分,一部分用 f 数组直接得到,剩下 <K 的一部分,以这些点为右端点暴力求得 但是这道题卡内存,所以...... 我们需要减少块数 我们发现查询时整块整块的算,复杂度是 1 的 所以时间主要花在多余的数上,而这东西是跑不满的

ac 代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
namespace io {
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], iS, iT, obuf[SIZE], oS = obuf, oT = oS + SIZE - 1, c, qu[55]; int f, qr;
    // getchar
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : iS ++)) : iS ++)
    // print the remaining part
    inline void flush () {
        fwrite (obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }
    // putchar
    inline void putc (char x) {
        *oS ++ = x;
        if (oS == oT) flush ();
    }
    // input a signed integer
    template <class I>
    inline void gi (I &x) {
        for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x  10 + (c & 15); x = f;
    }
    // print a signed integer
    template <class I>
    inline void print (I &x) {
        if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
        while (qr) putc (qu[qr --]);
    }
    //no need to call flush at the end manually!
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::gi;
using io::putc;
using io::print;
map<int,int>mp;
const int k=131;
int n,m,p,x,y,ky,ans,r,gl[200010],gr[200010],l[200010],f200010;
int main()
{
    freopen("jewel.in","r",stdin);
    freopen("jewel.out","w",stdout);
    memset(gl,0x3f,sizeof(gl));
    memset(f,0x3f,sizeof(f));
    gi(n),gi(m),p=max(n/k,100);
    for(int i=1;i<=n;++i)
        gi(x),r=mp[x],r&&(gl[r]=i,gr[i]=r),mp[x]=i,l[i]=i-gr[i];
    for(int i=n-1;i>=1;--i)for(int j=k;j>=1;--j)
    {
        r=j*p;if(r<=i)break;
        fi=min(fi+1,gl[i]<=r?gl[i]-i:inf);
    }
    for(int i=1;i<=m;++i)
    {
        gi(x),gi(y),ky=(y-1)/p,ans=fx;
        for(int j=ky*p+1;j<=y;++j)
            (gr[j]>=x)&&(ans>l[j])&&(ans=l[j]);
        (ans==inf)&&(ans=-1),print(ans),putc('n');
    }
    return 0;
}