时间戳

首页 > 技术文章 > 牛客练习赛81B-小Q与彼岸花/51Nod-1295 XOR key (Tire树及其可持久化)

牛客练习赛81B-小Q与彼岸花/51Nod-1295 XOR key (Tire树及其可持久化)

UpMing 2021-04-24 21:58 原文

牛客练习赛81B-小Q与彼岸花：

 

题目大意：

给你n（n<=5000）个数和m（m<=5000）个询问，每次询问区间[L,R]中两个数的异或最大值是多少

题目思路：

因为这里的数据范围完全可以n^2写，所以我们对每次询问都对区间[L,R]的数建立一颗01字典树

把一个数转化为二进制后，从高位往树上插入

至于每次对一个数val查询谁和他异或起来最大，我们可以采取贪心的策略

我们同样把val转化为二进制，也从高位开始，然后如果该位是1，我们就在树上找0，反之，同理

因为这样能够保证最后得到的答案是最优的

// Problem: 小 Q 与异或
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11171/A
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
const ll mod = 1e9 + 7;

#define pb push_back
#define mst(x, a) memset(x, a, sizeof(x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define dep(i, a, b) for (int i = (a); i >= (b); --i)

inline ll read() {
    ll x = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
        f |= ch == '-', ch = getchar();
    while ('0' <= ch && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

void out(ll x) {
    int stackk[20];
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (!x) {
        putchar('0');
        return;
    }
    int top = 0;
    while (x)
        stackk[++top] = x % 10, x /= 10;
    while (top)
        putchar(stackk[top--] + '0');
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}
ll n, m, val[maxn];
int son[maxn][2],indexx;
ll find(ll x) {
    ll ans=0;
    int p =0 ;
    for(int i=11 ;i>=0 ;i--)
    {
        int op = (x>>i)&1;
        int opp;
        if(op==0) opp=1;
        else opp=0;
        if(son[p][opp]) ans+=(1<<i),p=son[p][opp];
        else p = son[p][op]; 
    }
    return ans;
}
void insert(ll x) {
    int p =0;
    for(int i=11 ;i>=0 ;i--)
    {
        int op = (x>>i)&1;
        if(son[p][op]==0) son[p][op]=++indexx;
        p=son[p][op]; 
    }
}
int main() {
    n = read(), m = read();
    rep(i, 1, n) val[i] = read();
    while (m--) {
        int l = read();
        int r = read();
        if (l == r) {
            puts("0");
            continue;
        }
        mst(son,0);
        ll ans = 0;
        indexx=0;
        for (int i = l; i <= r; i++)
            ans = max(ans, find(val[i])), insert(val[i]);
        out(ans);
        puts("");
    }

    return 0;
}
/*


*/
View Code

51Nod-1295 XOR key ：

题目大意：

给出一个长度为N的正整数数组A，再给出Q个查询，每个查询包括3个数，L, R, X (L <= R)。求A[L] 至 A[R] 这R - L + 1个数中，与X 进行异或运算(Xor)，得到的最大值是多少？

2 <= N <= 50000 2 <= Q <= 50000

题目思路：

 因为数据范围较大，而且也是询问区间，这里选择将tire树可持久化

来存一发板子

写法的话，思想跟主席树相同

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
const ll mod = 1e9 + 7;

#define pb push_back
#define mst(x, a) memset(x, a, sizeof(x))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define dep(i, a, b) for (int i = (a); i >= (b); --i)

inline ll read() {
    ll x = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
        f |= ch == '-', ch = getchar();
    while ('0' <= ch && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

void out(ll x) {
    int stackk[20];
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (!x) {
        putchar('0');
        return;
    }
    int top = 0;
    while (x)
        stackk[++top] = x % 10, x /= 10;
    while (top)
        putchar(stackk[top--] + '0');
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}
int n, qq, val[maxn], rt[maxn];
struct node {
    int sum;
    int num[2];
} tire[maxn * 35];
int indexx;
void insert(int pre, int &now, int num) {
    now = ++indexx;
    int pre1 = pre;
    int now1 = now;
    for (int i = 31; i >= 0; i--) {
        tire[now1] = tire[pre1];
        tire[now1].sum++;
        int op = (num >> i) & 1;
        tire[now1].num[op] = ++indexx;
        now1 = indexx;
        pre1 = tire[pre1].num[op];
    }
    tire[now1] = tire[pre1];
    tire[now1].sum++;
}
int query(int v, int u, int num) {
    int ans = 0;
    for (int i = 31; i >= 0; i--) {
        int op = (num >> i) & 1;
        int opp = (op == 1) ? 0 : 1;
        if (tire[tire[u].num[opp]].sum - tire[tire[v].num[opp]].sum > 0) {
            u = tire[u].num[opp];
            v = tire[v].num[opp];
            ans += (1 << i);
        } else {
            u = tire[u].num[op];
            v = tire[v].num[op];
        }
    }
    return ans;
}
int main() {
    n = read(), qq = read();
    rep(i, 1, n) val[i] = read(), insert(rt[i - 1], rt[i], val[i]);
    while (qq--) {
        int x = read();
        int l = read();
        int r = read();
        l++, r++;
        out(query(rt[l - 1], rt[r], x));
        puts("");
    }
    return 0;
}
/*


*/
View Code
/*�ɳ־û��ֵ���*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data, v) memset(_data, v, sizeof(_data))
#define sc(n) scanf("%d", &n)
#define SC(n, m) scanf("%d %d", &n, &m)
#define SZ(a) int((a).size())
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define drep(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 5e4 + 5;
int n, q, cnt = 0, a;
int son[maxn * 35][2], root[maxn * 35], sum[maxn * 35];
il int Insert(int val, int pre) {
    int x = ++cnt, t = x;
    for (int i = 31; i >= 0; --i) {
        son[x][0] = son[pre][0], son[x][1] = son[pre][1];
        sum[x] = sum[pre] + 1;
        int id = 1 & (val >> i);
        son[x][id] = ++cnt;
        x = son[x][id], pre = son[pre][id];
    }
    sum[x] = sum[pre] + 1;
    return t;
}
il int Query(int val, int l, int r) {
    int ans = 0;
    for (int i = 31; i >= 0; --i) {
        int id = !(1 & (val >> i));
        if (sum[son[r][id]] - sum[son[l][id]] > 0) {
            ans |= (1 << i);
            l = son[l][id], r = son[r][id];
        } else
            l = son[l][!id], r = son[r][!id];
    }
    return ans;
}
int main() {
    std::ios::sync_with_stdio(0);
    cin >> n >> q;
    rep(i, 1, n) cin >> a, root[i] = Insert(a, root[i - 1]);
    int x, l, r;
    rep(i, 1, q) {
        cin >> x >> l >> r;
        l++, r++;
        cout << Query(x, root[l - 1], root[r]) << endl;
    }
    return 0;
}
View Code

 

推荐阅读