ACM学习历程—POJ 3764 The xor-longest Path(xor && 字典树 && 贪心)

题目链接:http://poj.org/problem?id=3764

题目大意是在树上求一条路径,使得xor和最大。

由于是在树上,所以两个结点之间应有唯一路径。

而xor(u, v) = xor(0, u)^xor(0, v)。

所以如果预处理出0结点到所有结点的xor路径和,问题就转换成了求n个数中取出两个数,使得xor最大。

这个之前用字典树处理过类似问题。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long

using namespace std;

const int maxN = 100005;

//求n个数中取出两个数能xor的最大值
//Trie Tree字典树
//len*n, len为数的二进制最大长度
const int len = 31;//len表示数的二进制最大长度
struct Trie
{
    int next[2];
}tree[maxN*len];
int cntTree;

void initTree()
{
    cntTree = 0;
    memset(tree, -1, sizeof(tree));
}

void add(int x)
{
    int now = 0;
    bool k;
    for (int i = len; i >= 0; i--)
    {
        k = x&(1<<i);
        if (tree[now].next[k] == -1)
            tree[now].next[k] = ++cntTree;
        now = tree[now].next[k];
    }
}

//返回当前数中能和x合成最大数的数
int query(int x)
{
    int v = 0, now = 0;
    bool k;
    for (int i = len; i >= 0; i--)
    {
        k = x&(1<<i);
        if (tree[now].next[!k] != -1)
            k = !k;
        v = v|(k<<i);
        now = tree[now].next[k];
    }
    return v;
}

//链式前向星
struct Edge
{
    int to, next;
    int val;
}edge[maxN*2];

int head[maxN], cnt;

void addEdge(int u, int v, int w)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    edge[cnt].val = w;
    head[u] = cnt;
    cnt++;
}

void initEdge()
{
    memset(head, -1, sizeof(head));
    cnt = 0;
}

int n, p[maxN];

void dfs(int now)
{
    int to;
    for (int i = head[now]; i != -1; i = edge[i].next)
    {
        to = edge[i].to;
        if (p[to] == -1)
        {
            p[to] = p[now]^edge[i].val;
            dfs(to);
        }
    }
}

void input()
{
    initEdge();
    memset(p, -1, sizeof(p));
    int u, v, w;
    for (int i = 1; i < n; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    p[0] = 0;
    dfs(0);
}

void work()
{
    int ans = 0;
    initTree();
    for (int i = 0; i < n; ++i)
    {
        add(p[i]);
        ans = max(ans, p[i]^query(p[i]));
    }
    printf("%d\n", ans);
}

int main()
{
    //freopen("test.in", "r", stdin);
    while (scanf("%d", &n) != EOF)
    {
        input();
        work();
    }
    return 0;
}

时间: 11-09

ACM学习历程—POJ 3764 The xor-longest Path(xor && 字典树 && 贪心)的相关文章

ACM学习历程—HDU 3915 Game(Nim博弈 &amp;&amp; xor高斯消元)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3915 题目大意是给了n个堆,然后去掉一些堆,使得先手变成必败局势. 首先这是个Nim博弈,必败局势是所有xor和为0. 那么自然变成了n个数里面取出一些数,使得xor和为0,求取法数. 首先由xor高斯消元得到一组向量基,但是这些向量基是无法表示0的. 所以要表示0,必须有若干0来表示,所以n-row就是消元结束后0的个数,那么2^(n-row)就是能组成0的种数. 对n==row特判一下. 代码:

ACM学习历程——POJ3468 A Simple Problem with Integers(线段树)

Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval. In

ACM学习历程—HDU 4726 Kia&#39;s Calculation( 贪心&amp;&amp;计数排序)

DescriptionDoctor Ghee is teaching Kia how to calculate the sum of two integers. But Kia is so careless and alway forget to carry a number when the sum of two digits exceeds 9. For example, when she calculates 4567+5789, she will get 9246, and for 12

ACM学习历程—HDU 5023 A Corrupt Mayor&#39;s Performance Art(广州赛区网赛)(线段树)

Problem Description Corrupt governors always find ways to get dirty money. Paint something, then sell the worthless painting at a high price to someone who wants to bribe him/her on an auction, this seemed a safe way for mayor X to make money. Becaus

2014百度之星资格赛—— Xor Sum(01字典树)

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 0    Accepted Submission(s): 0 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起

ACM学习历程—HDU 5536 Chip Factory(xor &amp;&amp; 字典树)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5536 题目大意是给了一个序列,求(si+sj)^sk的最大值. 首先n有1000,暴力理论上是不行的. 此外题目中说大数据只有10组,小数据最多n只有100.(那么c*n^2的复杂度应该差不多) 于是可以考虑枚举i和j,然后匹配k. 于是可以先把所有s[k]全部存进一个字典树, 然后枚举s[i]和s[j],由于i.j.k互不相等,于是先从字典树里面删掉s[i]和s[j],然后对s[i]+s[j]这个

HDU 4825 Xor Sum(经典01字典树+贪心)

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 1555    Accepted Submission(s): 657 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Ze

CODEVS1187 Xor最大路径 (字典树)

由于权值是在边上,所以很容易发现一个性质:d(x,y)=d(x,root) xor d(y,root). 因为有了这个性质,那么就很好做了.对于每一个点统计到root的距离,记为f 数组. 将f数组里的每个值插进按照二进制位插进字典树里面. 枚举每一个点,然后在字典树中搜索最大的xor值就可以了. Program CODEVS1187; const maxn=100008; type arr=record u,v,w,next:int64; end; type arr1=record next:

ACM学习历程—HDU 3949 XOR(xor高斯消元)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3949 题目大意是给n个数,然后随便取几个数求xor和,求第k小的.(重复不计算) 首先想把所有xor的值都求出来,对于这个规模的n是不可行的. 然后之前有过类似的题,求最大的,有一种方法用到了线性基. 那么线性基能不能表示第k大的呢? 显然,因为线性基可以不重复的表示所有结果.它和原数组是等价的. 对于一个满秩矩阵 100000 010000 001000 000100 000010 000001