UVALive 7043 International Collegiate Routing Contest 字典树,递归

By | 03月08日
Advertisement

题目链接:这里
题意:给出n个IPv4的子网地址,格式是a-b-c-d/l,a b c d l都是十进制数,然后l是网络地址的长度,最长到32,要求输出最低限度的所有的未能划分出的子网地址,这些子网和给出的n个子网没有交集,这些地址和给出的n个地址能组成完整的网络地址。
解法:把所有的ip地址插进字典树,并且标记单词节点,之后然后暴力递归找所有未被包含在已有子网里的子网地址。其实就是trie树上暴力。。。。不过题意看pdf看了超久,还是在网上的解题报告弄清题意的,读题需要训练了。

//LA 7043

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;

struct Trie{
    struct node{
        int a, b, c, d, l;
        node(){}
        node(int a, int b, int c, int d, int l) : a(a), b(b), c(c), d(d), l(l) {}
    };
    int n, cnt, ans[40];
    char s[40];
    vector <node> v;
    int root, sz, ch[maxn][2], flag[maxn];
    void get(int x){
        for(int i = 7; i >= 0; i--){
            if((x>>i)&1) s[cnt++] = '1';
            else s[cnt++] = '0';
        }
    }
    void init(){
        root = 0;
        sz = 1;
        memset(ch[0], 0, sizeof(ch[0]));
        v.clear();
    }
    void insert(char *s, int len){
        int u = root;
        for(int i = 0; i < len; i++){
            int now = s[i] - '0';
            if(!ch[u][now]){
                memset(ch[sz], 0, sizeof(ch[sz]));
                flag[sz] = 0;
                ch[u][now] = sz++;
            }
            u = ch[u][now];
        }
        flag[u] = 1;
    }
    void query(int u, int cur){
        if(flag[u]) return;
        for(int j = 1; j >= 0; j--){
            ans[cur] = j;
            if(ch[u][j]){
                query(ch[u][j], cur+1);
            }
            else{
                int a, b, c, d;
                int tt, l, r;
                tt = 0, l = 0, r = 7;
                for(int i = l; i <= r; i++) tt = tt * 2 + ans[i];
                a = tt;
                tt = 0, l = 8, r = 15;
                for(int i = l; i <= r; i++) tt = tt * 2 + ans[i];
                b = tt;
                tt = 0, l = 16, r = 23;
                for(int i = l; i <= r; i++) tt = tt * 2 + ans[i];
                c = tt;
                tt = 0, l = 24, r = 31;
                for(int i = l; i <= r; i++) tt = tt * 2 + ans[i];
                d = tt;
                v.push_back(node(a, b, c, d, cur));
            }
        }
    }
    void run(){
        int T, ks = 0;
        scanf("%d", &T);
        while(T--){
            init();
            scanf("%d", &n);
            printf("Case #%d:\n", ++ks);
            if(n == 0){
                printf("1\n");
                printf("0.0.0.0/0\n");
            }
            else{
                for(int i = 0; i < n; i++){
                    int a, b, c, d, l;
                    scanf("%d.%d.%d.%d/%d", &a, &b, &c, &d, &l);
                    cnt = 0;
                    get(a), get(b), get(c), get(d);
                    s[cnt] = 0;
                    insert(s, l);
                }
                query(0, 0);
                cout << v.size() << endl;
                for(int i = 0; i < (int)v.size(); i++){
                    printf("%d.%d.%d.%d/%d\n", v[i].a, v[i].b, v[i].c, v[i].d, v[i].l + 1);
                }
            }
        }
    }
}ac;
int main()
{
    ac.run();
    return 0;
}

Similar Posts:

  • HDU 1671 (字典树统计是否有前缀)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1671 Problem Description Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers: 1. Emergenc

  • HDU 1671 (Trie 字典树)

    #include <stdio.h> #include <iostream> #include <string.h> #include <stdlib.h> #define MAX 50021 using namespace std; typedef struct trie { trie *next[26]; int v; }trie; trie *root; void creat_trie(char str[]) { int len = strlen(st

  • HDUOJ 1004 Let the Balloon Rise ——三种解法:字典树,暴力,排序

    Let the Balloon Rise Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 70944 Accepted Submission(s): 26378 Problem Description Contest time again! How excited it is to see balloons floating around.

  • Codeforces Round #311 (Div. 2) E - Ann and Half-Palindrome(字典树+dp)

    E. Ann and Half-Palindrome time limit per test 1.5 seconds memory limit per test 512 megabytes input standard input output standard output Tomorrow Ann takes the hardest exam of programming where she should get an excellent mark. On the last theoreti

  • 杭电1671字典树

    Phone List Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8253 Accepted Submission(s): 2833 Problem Description Given a list of phone numbers, determine if it is consistent in the sense that no n

  • python 数据结构转换,将线性元祖转换成字典树

    有一个数据表 id fid title 1 -1 python 2 -1 ruby 3 -1 php 4 -1 lisp 5 1 flask 6 1 django 7 1 webpy 8 2 rails 9 3 zend 10 6 dblog 这是一个栏目表,title 是栏目名称, id 是栏目 id, fid 是栏目的父id.构建一个多级栏目分类 通过 python 查询处理,会得到下面的一个元祖, t = ( (1, -1, 'python'), (2, -1, 'ruby'), (3,

  • Hash树(散列树)和Trie树(字典树、前缀树)

    1.Hash树 理想的情况是希望不经过任何比较,一次存取便能得到所查的记录, 那就必须在记的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和一个唯一的存储位置相对应.因而在查找时,只要根据这个对应关系f找到 给定值K的像f(K).由此,不需要进行比较便可直接取得所查记录.在此,我们称这个对应关系为哈希(Hash)函数,按这个思想建立的表为哈希表. 在哈希表中对于不同的关键字可能得到同一哈希地址,这种现象称做冲突.在一般情况下,冲突只能尽可能地减少,而不能完全避免.因为哈希函数是从

  • 字典树(Trie tree)

    Trie,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高. 性质 它有3个基本性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串. 每个节点的所有子节点包含的字符都不相同. [编辑]图示 这是一个Trie结构的例子: 在这个Trie结构中,保存了

  • 字典树trie

    字典树经常用于单词搜索,现在网络引擎中也应用了trie树: public class Trie{ private int SIZE = 26; private TrieNode root; Trie(){ root = new TrieNode(); } private class TrieNode{ private int num;//the times that words passing this node private TrieNode[] son;//son point privat

  • hdoj 1247 Hat’s Words(字典树)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1247 思路分析:题目要求找出在输入字符串中的满足要求(该字符串由输入的字符串中的两个字符串拼接而成)的字符串. 对于长度为LEN的字符串,其可能由LEN种可能的拼接可能:现在问题转化为查找能够拼接成该字符串的可能的两个字符串是否都在 输入的字符串中,使用字典树可以实现快速的字符串查找,算法复杂度为O(N*M),N为输入字符串的个数,M为字符串长度. 代码如下: #include <cstdio>

Tags: