慕容琳的后花园
慕容琳的后花园
hgoi#20191030

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("%d\n",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("%lld\n",ans);
    return 0;
}

T3-宝石专家

给定一个长度为n的数组a
进行m次询问,每次询问在l到r的区间内
满足a_i = a_jij – 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],f[200010][132];
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;
        f[i][j]=min(f[i+1][j],gl[i]<=r?gl[i]-i:inf);
    }
    for(int i=1;i<=m;++i)
    {
        gi(x),gi(y),ky=(y-1)/p,ans=f[x][ky];
        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;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20191030
T1-腿部挂件 给定一个长度为n的数组 进行m次询问,每次询问l到r的区间里$a[i]\oplus x$的最大值 解法 如果没有l,r的限制,很容易想到trie树 那有l,r的限制怎么办呢 我们在trie树里套一…
扫描二维码继续阅读
2019-10-30
功能