Solution20191030

一:腿部挂件

题目描述

给定一个长度为n的数组
进行q次询问:$x_i, \; l_i , \; r_i$,求$\max_{l\le i\le r}x\oplus a_i$(其中$\oplus$是异或运算)

数据范围

$n \le 200000,\; q\le 200000$

思路

求最大异或值,不难想到01Trie树,然而这里求的是区间最大异或,那么就使用可持久化Trie树,具体来说就是像主席树一样,把每次更新的一条链从之前的副本中独立出来作为新的副本。

空间/时间复杂度:$O(n\cdot log(\max{a_i}))$

另一种方法:
将一颗Trie树的每一个结点都变成一个vector记录有哪些$a_i$经过这个点,向下走的时候二分判断当前查询的点的vectir是否有在$[l_i,r_i]$的结点。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fprintf(stderr,__VA_ARGS__)
#define N 200010
using namespace std;
int n,q,a[N];
template<typename T> inline void read(T &x){
    x = 0; char ch = getchar(); T fh = 1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')fh=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    x *= fh;
}
namespace solve1{
    void main(){
        while(q--){
            int x,l,r,mx = 0;
            read(x), read(l), read(r);
            l++, r++;
            REP(i,l,r) mx = max(mx,a[i] ^ x);
            PF("%d\n",mx);
        }
    }
}
namespace solve2{
    int t[N<<5],s[2][N<<5],cnt = 0,root[N];
    #define B 31
    int pre(){
        return 0;
    }
    int insert(int r,int val,int d){
        if(d == B + 2) return 0;
        int now = ++cnt;
        
        bool id = (bool)(val & (1 << (B - d + 0)));
        
        REP(i,0,1) s[i][now] = s[i][r];
        s[id][now] = insert(s[id][r],val,d + 1);
        if(s[id][now]) t[s[id][now]] = t[s[id][r]] + 1;
        return now;
    }
    int solve(int r,int pre,int val,int d){
        if(d == B + 2) return 0;
        bool id = (bool)(((val >> (B - d + 0)) & 1) ^ 1);
        
        if(t[s[id][r]] - t[s[id][pre]])
            return solve(s[id][r],s[id][pre],val,d + 1) + (1 << (B - d));
        return solve(s[id ^ 1][r],s[id ^ 1][pre],val,d + 1);
    }
    void init(){
        memset(s,0,sizeof s);
        memset(t,0,sizeof t);
    }
    void main(){
        init();
        root[0] = pre();
        REP(i,1,n) root[i] = insert(root[i - 1],a[i],1);
        
        while(q--){
            int x,l,r;
            read(x), read(l), read(r);
            l++, r++;
            PF("%d\n",solve(root[r],root[l - 1],x,1));
        }
    }
}
int main()
{
//	freopen("hugclose.in","r",stdin);
//	freopen("hugclose.out","w",stdout);
    cin>>n>>q;
    REP(i,1,n) read(a[i]);
//	if(n <= 5000 && q <= 5000) solve1::main();
    solve2::main();
    return 0;
}

二:走夜路

题目描述

一条直线上有n+1个充电站,两个相邻充电站之间有一距离$D_i$的段路。一开始你在第一个充电站,每个充电站有一个充一单位电量的费用$P_i$,每走一个单位距离就要耗费一单位电,求按顺序走完所有充电站的最小代价,手电筒的容量为$T$。

数据范围

$2\le N\le 500000 \\
1≤T≤10^9\\
1\le D_i,P_i\le1000000$

思路

贪心。

令$nxt_i$为$i$充电站之后第一个比它费用小的充电站。

一个充电站在能够到达$nxt_i$之前,显然尽量充电,否则将会被迫以以更大费用充电。

如果到不了$nxt_i$,就充满。如果存在两站之间的距离大于容量就无解。

Code

#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 501005
#define ll long long
int n,m,i,r,now,d[N],p[N],q[N],nxt[N];
ll dis,ans,sum[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d%d",&d[i],&p[i]),sum[i]=sum[i-1]+1ll*d[i];
	for(i=n;i;i--){
		while(r&&p[q[r]]>p[i])r--;
		nxt[i]=q[r];q[++r]=i;
		if(!nxt[i])nxt[i]=n+1;
	}
	ans=0;now=0;
	for(i=1;i<=n;i++){
		now-=d[i-1];
		if(now<0){puts("-1");return 0;}
		dis=min(sum[nxt[i]-1]-sum[i-1],1ll*m);
		if(dis>now)ans+=1ll*(dis-now)*p[i],now=dis;
	}
	printf("%lld\n",ans);
	return 0;
}

三:宝石专家

题目描述

给定一个长度为n的数组a
进行m次询问,每次询问在l到r的区间内
满足$a_i=a_j$的$|a_i-a_j|$最小值

数据范围

$n \le 200000$

思路

先看某一种特定的$a_i$,它们对答案的贡献一定是它们之间两两相邻所连的线段。

那么所求就是$[l,r]$内这样的小线段的最短长度。

离线。

将询问根据右端点递增排序,从1→n遍历,如果当前i是一条“小线段”的右端点$r_i$,那么在数据结构的$[1,l_i]$位置用$r_i-l_i$更新最小值,表示对于右端点为$i$的询问,如果它的左端点在$[1,l_i]$内,这条小线段的贡献就是$r_i-l_i$。

再看如果当前$i$是一个询问的右端点$R_i$,那么数据结构的$L_i$的位置就是这个询问的答案。

要$a_i$离散化。

这个数据结构(区间修改,单点最值)可以用线段树,也可以用树状数组。注意与计算和的树状数组不同,这里树状数组的更新是-=lowbit,查询是+=lowbit

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fprintf(stderr,__VA_ARGS__)
#define N 200010
#define M 200010
#define INF 0x3f3f3f3f
using namespace std;
template<typename T> inline void read(T &x){
    x = 0; char ch = getchar(); T fh = 1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')fh=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    x *= fh;
}
int n,m,len,a[N],tmp[N],out[M],mp[N];
struct Q{
    int l,r,id;
}q[M];
bool cmp(const Q &x,const Q &y){
    if(x.r != y.r) return x.r < y.r;
    return x.l < y.l;
}
#define ID(x) (lower_bound(tmp + 1,tmp + 1 + len,x) - tmp)
struct BIT{
    int data[N];
    BIT(){memset(data,0x3f,sizeof data);}
    void update(int pos,int val){
        for(;pos;pos -= pos & (-pos))
            data[pos] = min(data[pos],val);
    }
    int query(int pos){
        int res = INF; 
        for(;pos <= n;pos += pos & (-pos))
            res = min(res,data[pos]);
        return res;
    }
}b;
int main()
{
//	freopen("jewel.in","r",stdin);
//	freopen("jewel.out","w",stdout);
    memset(mp,0,sizeof mp);
    cin>>n>>m;
    REP(i,1,n) read(a[i]), tmp[i] = a[i];
    sort(tmp + 1,tmp + 1 + n);
    len = unique(tmp + 1,tmp + 1 + n) - tmp - 1;
    REP(i,1,m) read(q[i].l), read(q[i].r), q[i].id = i;
    sort(q + 1,q + 1 + m,cmp);
    int Qpos = 1;
    REP(i,1,n){
        int id = ID(a[i]);
        if(mp[id]) b.update(mp[id],i - mp[id]);
        mp[id] = i;
        while(q[Qpos].r == i && Qpos <= m){
            out[q[Qpos].id] = b.query(q[Qpos].l);
            Qpos++;			
        }
    }
    REP(i,1,m) PF("%d\n",out[i] == INF ? -1 : out[i]);
    return 0;
}

 

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注