题解

64 条题解

  • 0
    @ 2019-01-10 16:39:59
    import java.util.*;
    import java.io.*;
    import java.lang.Math.*;
    import java.text.DecimalFormat;
    class Tree {
        public Tree left, right;
        public char value;
        public int frequency;
        public Tree (char value, int frequency) {
            this.value = value;
            this.frequency = frequency;
        }
        
        private void showTreedepth(Tree t, int depth) {
            if (t == null) return;
            showTreedepth(t.right, depth + 1);
            int i;
            for (i = 0 ; i < depth; i++) System.out.print("\t\t");
            System.out.println("(" + t.value + ", " + t.frequency + ")");
            showTreedepth(t.left, depth + 1);
        }
        
        public void showTree() {
            showTreedepth(this, 0);
        }
        
        public void preorder(int[] depth, int step) {
            if (this == null) return;
            if (this.left == null && this.right == null) {
                if (this.value == '_') {
                    depth[26] = step;
                } else if (this.value >= 'A' && this.value <= 'Z') {
                    depth[this.value - 'A'] = step;
                }
                return;
            }
            this.left.preorder(depth, step + 1);
            this.right.preorder(depth, step + 1);
        }
    }
    
    class NodeComparator implements Comparator<Tree> {
        @Override
        public int compare(Tree t1, Tree t2) {
            if (t1.frequency > t2.frequency) return 1;
            return -1;
        }
    }
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str;
            int pl;
            double ratio;
            // DecimalFormat df = new DecimalFormat("###.0");
            while ((str = sc.nextLine())!= null) {
                if (str.compareTo("END") == 0) {
                    break;
                }
                if (str.length() == 0) continue;
                pl = HuffmanPattern(str);
                ratio = (double) str.length() * 8.0 / (pl * 1.0);
            
                System.out.println(str.length() * 8 + " " + pl + " " + String.format("%.1f", ratio));
            }
        }
        
        public static int HuffmanPattern(String str) {
            Tree[] pattern = new Tree[27];
            int[] depth = new int[27];
            Tree t1 = null, root = null, t2 = null;
            int i;
            char ch;
            for (i = 0 ; i < 27; i++) {
                if (i != 26) {
                    ch = (char) (65 + i);
                    pattern[i] = new Tree(ch, 0);
                } else {
                    pattern[i] = new Tree('_', 0);
                }
            }
            Comparator<Tree> cmp = new NodeComparator();
            PriorityQueue<Tree> queue = new PriorityQueue<Tree>(64, cmp);
            for (i = 0 ; i < str.length(); i++) {
                if (str.charAt(i) == '_') {
                    pattern[26].frequency++;
                } else if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') {
                    pattern[str.charAt(i) - 'A'].frequency++;
                }
            }
            
            for (i = 0 ; i < 27; i++) {
                if (pattern[i].frequency != 0) {
                    queue.add(pattern[i]);
                }
            }
            if (queue.size() == 0) return 0;
            if (queue.size() == 1) return queue.remove().frequency;
            // root = queue.peek();
            while (queue.size() > 1) {
                t1 = queue.remove();
                t2 = queue.remove();
                root = new Tree('0', t1.frequency + t2.frequency);
                root.left = t1;
                root.right = t2;
                queue.add(root);
            }
            root = queue.remove();
            root.preorder(depth, 0);
            
            int ans = 0;
            for (i = 0 ; i < 27; i++) {
                ans += depth[i] * pattern[i].frequency;
            }
            return ans;
        }
        
    }
    
  • 0
    @ 2018-08-01 13:54:30

    发现我变成LV 10了~~

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7777777;
    const double eps=1e-8;
    
    string s;
    int a[27];
    int b[27];
    vector<int> g[101];
    struct node {
        int id,v;
        bool operator<(node x) const {
            return v>x.v;
        }
    };
    priority_queue<node> pq;
    void insert(int x,int y) {
        g[x].pb(y);
        g[y].pb(x);
    }
    void dfs(int x,int fa=-1,int dep=0) {
        bool ok=0;
        for (int i=0;i<g[x].size();i++) {
            int to=g[x][i];
            if (to!=fa) {
                ok=1;
                dfs(to,x,dep+1);
            }
        }
        if (!ok) {
            b[x]=a[x]*dep;
        }
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        while (cin>>s) {
            if (s=="END") {
                break;
            }
            memset(a,0,sizeof a);
            memset(b,0,sizeof b);
            REP(i,0,100) g[i].clear();
            while (pq.size()) pq.pop();
            int sz=s.size();
            for (int i=0;i<sz;i++) {
                if (s[i]=='_') ++a[0];
                else ++a[s[i]-'A'+1];
            }
            int cnt=26;
            bool flag=0;
            REP(i,0,26) if (a[i]==sz) {
                printf("%d %d %.1lf\n",8*sz,sz,8.0);
                flag=1;
                break;
            }
            if (flag) continue;
            REP(i,0,26) if (a[i]) {
                pq.push(node{i,a[i]});
            }
            while (pq.size()) {
                if (pq.size()==1) {
                    dfs(pq.top().id);
                    pq.pop();
                } else {
                    node x=pq.top();pq.pop();
                    node y=pq.top();pq.pop();
                    node z=node{++cnt,x.v+y.v};
                    insert(x.id,z.id);
                    insert(y.id,z.id);
                    pq.push(z);
                }
            }
            int res=0;
            REP(i,0,26) res+=b[i];
            printf("%d %d %.1lf\n",8*sz,res,(double)8*sz/res);
        }
        return 0;
    }
    
  • 0
    @ 2017-05-01 10:51:00

    求帮忙测试下数据 显示答案错误但找不出原因

    #include <string>
    #include <list>
    #include <iostream>
    #include <iomanip>
    using namespace std;
    
    template <typename T>
    class Bnode{
    public:
        T data;
        Bnode<T>* parent;
        Bnode<T>* lc;
        Bnode<T>* rc; 
        Bnode():parent(NULL),lc(NULL),rc(NULL){}
        Bnode(const T &e,Bnode<T>* p=NULL,Bnode<T>* lc=NULL,Bnode<T>* rc=NULL):data(e),parent(p),lc(lc),rc(rc){}
    };
    
    template <typename T>
    class Btree{
    public:
        int _size;
        Bnode<T>* _root;//约定 树的对象只有这两个数据 整个树结构中其他所有数据(结点)都是new来的
        Btree():_size(0),_root(NULL){}
        Btree(T &e):_size(0){ _root=new Bnode<T>(e); }
        ~Btree(){deleteAll();}//如果只想删除Btree而不想删除Bnode,就在Btree析构前将_root置为NULL,当然,同时要保证所有Bnode应转移至别的Btree了
        void deleteAll(){delete_zishu(_root);}//清空整个树并使_root=NULL
    
        void delete_zishu(Bnode<T>* &zishu);
    
        void insertroot(T &e);  //初始化,函数内假定_root此时为NULL  不做此假定的话可以在函数内添加delete保证安全(不过意义不大)
        void insertlc(Bnode<T>* &node,T &e);//函数内假定node->lc=NULL(即node无左子树)  (在使用时在函数外部做判断或直接在使用前删去了左子树)
        void insertrc(Bnode<T>* &node,T &e);//函数内假定node->rc=NULL
    private:
        void delete_0(Bnode<T>* &node);//删除子树node但没有将node置为NULL,所以设为private
    };
    
    template <typename T>
    void Btree<T>::delete_0(Bnode<T>* &node){ //按后序来delete,置NULL过程写到外面,即delete_zishu里面
        if(node!=NULL){
            delete_0(node->lc);
            delete_0(node->rc);
            delete node;
        }
    }
    template <typename T>
    void Btree<T>::delete_zishu(Bnode<T>* &zishu){
        delete_0(zishu);zishu=NULL;
    }
    template <typename T>
    void Btree<T>::insertroot(T &e){ _root = new Bnode<T>(e); }
    template <typename T>
    void Btree<T>::insertlc(Bnode<T>* &node,T &e){
        node->lc = new Bnode<T>(e); node->lc->parent = node;
    }
    template <typename T>
    void Btree<T>::insertrc(Bnode<T>* &node,T &e){
        node->rc = new Bnode<T>(e); node->rc->parent = node;
    }
    
    class zifu{
    public:
        char c;
        int c_cishu;
        int weishu;
        zifu():c(0),c_cishu(0),weishu(0){}
        zifu(char cc,int cc_cishu,int ccweishu=0):c(cc),c_cishu(cc_cishu),weishu(ccweishu){}
    };
    
    template <typename T>
    Btree<T>* treehebing(Btree<T>* &ptree1,Btree<T>* &ptree2){
        T ccc=T();
        Btree<T> * ptree0 = new Btree<T>(ccc);
        ptree0->_root->lc=ptree1->_root;
        ptree0->_root->rc=ptree2->_root;
        ptree1->_root->parent=ptree0->_root;
        ptree2->_root->parent=ptree0->_root;
        ptree1->_root=NULL;
        ptree2->_root=NULL;
        return ptree0;
    }
    
    
    
    int changdu(string &yuanshuju){
        list<zifu> Z;
        bool x;//用于下面的判断
        for(int i=yuanshuju.size()-1;i>=0;--i){
            x=0;
            char ccc=yuanshuju[i];
            for(list<zifu>::iterator it = Z.begin(); it != Z.end(); ++it){
                if((*it).c==ccc) {(*it).c_cishu++;x=1;}
            }
            if(!x) Z.push_back(zifu(ccc,1));
        }
    
        list< Btree<zifu>* > HFMsenlin;
        list< Bnode<zifu>* > HFMbiao;
        for(list<zifu>::iterator it = Z.begin(); it != Z.end(); ++it){
            HFMsenlin.push_back(new Btree<zifu>(*it));//生成带根结点的树
            HFMbiao.push_back(HFMsenlin.back()->_root);
        }
        while(HFMsenlin.size()>1){
            Btree<zifu>* min1=HFMsenlin.front();
            Btree<zifu>* min2=HFMsenlin.back(); //二者必然不相等
            Btree<zifu>* x=min1;
            int min1cishu=min1->_root->data.c_cishu,min2cishu=min2->_root->data.c_cishu,xcishu=min1cishu;
            if(min1cishu>min2cishu) {min1=min2;min1cishu=min2cishu;min2=x;min2cishu=xcishu;}
            for(list< Btree<zifu>* >::iterator it = HFMsenlin.begin(); it != HFMsenlin.end(); ++it){
                int itcishu = (*it)->_root->data.c_cishu;
                if(itcishu<min1cishu){min2=min1;min2cishu=min1cishu;min1=*it;min1cishu=itcishu;}
                else if((min1!=(*it))&&(itcishu<min2cishu)){min2=*it;min2cishu=itcishu;}
            }
            Btree<zifu>* xin = treehebing(min1,min2);//内部min1 min2 处理了
            xin->_root->data.c_cishu=min1cishu+min2cishu;
            delete min1;
            delete min2;
            HFMsenlin.remove(min1);
            HFMsenlin.remove(min2);
            HFMsenlin.push_back(xin);
        }
        Btree<zifu>* HFMtree=*(HFMsenlin.begin());
        int ans=0;
        for(list< Bnode<zifu>* >::iterator it = HFMbiao.begin(); it != HFMbiao.end(); ++it){
            int i=0;
            Bnode<zifu>* ii=*it;
            if(!(ii->parent)) ++i;/////特殊考虑只有一种字符的情况
            while(ii->parent){++i;ii=ii->parent;}
            ans += ((*it)->data.c_cishu)*i;
        }
        delete HFMtree;
        return ans;
    }
    
    int main(){
        list<string> shuju;
        while(true){
            string yuanshuju;
            getline(cin,yuanshuju);
            if(yuanshuju=="END") break;
            shuju.push_back(yuanshuju);
        }
        while(shuju.size()>0){
            string s = shuju.front();
            int siz = s.size()*8;
            int chang=changdu(s);
            float f= (siz*1.0)/(chang*1.0);
            cout<<siz<<' '<<chang<<' ';
            cout<<fixed<<setprecision(1)<<f<<endl;
            shuju.pop_front();
        }
        return 0;
    }
    
    求大家帮忙看看,帮忙测试下数据 我考虑了只有一种字母的情况 但不知道考虑得对不对 求大家看看有什么会出错的数据 谢谢!
    
    
  • 0
    @ 2016-09-04 14:26:35

    果然水题需细心。。特判错误+10086

  • 0
    @ 2012-09-27 23:51:30

    这个 没处理不合并的+1

  • 0
    @ 2012-09-27 16:34:01

    太简单

  • 0
    @ 2012-08-16 00:44:46

    虽然看题解发现是哈夫曼树,但还是没理解唯一性是怎么回事。。如楼下所说

    如果样例1是这样:

    A-0

    B-10

    C-11

    D-101

    那么AAAAABCD换成01串就是000001011101(长度只有12),如果不删减任何数字的话貌似没可能翻译成其他字符的。

  • 0
    @ 2010-07-08 22:46:24

    传说中的脑精急转弯- -

  • 0
    @ 2009-11-18 21:32:36

    html://red fgfg

  • 0
    @ 2009-11-08 22:33:36

    2次过

    第一次 忽略了只有一种字符的情况

    第二次 AC

    未优化的哈夫曼即可

  • 0
    @ 2009-11-07 12:54:18

    特判!不需要合并的情况!

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-11-02 20:05:30

    贪心

    怎么写着动态规划

  • 0
    @ 2009-11-02 15:09:36

    和楼下一样的杯具……

    不过能和神牛犯一样的错误那就是我的荣幸阿

    一开始还准备写一个猥琐的链表实现的堆来记录,然后才发现其实扫一遍就可以了……

  • 0
    @ 2009-11-02 13:32:36
    • -囧掉了
      特意特判,可惜特判错了啊- -
      囧死了
  • 0
    @ 2009-11-01 20:59:31

    太BT了,数据只有1个

  • 0
    @ 2009-10-30 17:24:16

    我也经历了

    ├ 测试数据 01:答案错误... 

    ├ 标准行输出 208..

     ├ 错误行输出 40 7..

    后来发现,这是评测机的问题,其实错的点并不是这个。。。。。。

    详情见lxxxxxxxxxxxxx。。。

  • 0
    @ 2009-10-24 20:31:04

    哈夫曼树,跟合并果子差不多

  • 0
    @ 2009-10-23 13:43:43

    哈夫曼树!!第三个输出的就是压缩率

    orzLX的牛:

    ├ 测试数据 01:答案错误... 

    ├ 标准行输出 208..

     ├ 错误行输出 40 7..

    报出这种错还真是让人不知怎么办

    其实问题在于没有判断不需要合并[/red]的情况

  • 0
    @ 2009-10-22 20:10:08

    我被雷到了,居然只有一个测试点。

    求带权最短路是可以用堆维护的方法。

    但是这里我们需要吗?

    26个字母加上一个下划线才27个数据。

    首先2个单调队列肯定比前者非常快的

    然后是冒泡排序,因为数据的关系,再加上常数因子小,冒泡其实也很优秀。

    堆的复杂度虽然很低,但是常数因子很大,在27的数据面前体现不了作用的。

    有点真是吃力不讨好的感觉。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-18 13:58:57

    为什么我的错误

    是编译通过...

    ├ 测试数据 01:答案错误... 

    ├ 标准行输出 208..

     ├ 错误行输出 40 7..

    连字符串的长度的8倍都错了?

信息

ID
1079
难度
6
分类
贪心 点击显示
标签
(无)
递交数
1340
已通过
387
通过率
29%
上传者