64 条题解
-
0
Goodhao LV 10 @ 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
求帮忙测试下数据 显示答案错误但找不出原因
#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
Spirit_Night LV 10 @ 2009-11-08 22:33:36
2次过
第一次 忽略了只有一种字符的情况
第二次 AC
未优化的哈夫曼即可
-
0
pheetleern LV 8 @ 2009-11-02 15:09:36
和楼下一样的杯具……
不过能和神牛犯一样的错误那就是我的荣幸阿
一开始还准备写一个猥琐的链表实现的堆来记录，然后才发现其实扫一遍就可以了…… -
0
qyjubriskxp LV 10 @ 2009-10-23 13:43:43
哈夫曼树！！第三个输出的就是压缩率
orzLX的牛：
├ 测试数据 01：答案错误...
├ 标准行输出 208..
├ 错误行输出 40 7..
报出这种错还真是让人不知怎么办
其实问题在于没有判断不需要合并[/red]的情况 -
0
SecretAgent LV 10 @ 2009-10-22 20:10:08
我被雷到了，居然只有一个测试点。
求带权最短路是可以用堆维护的方法。
但是这里我们需要吗？
26个字母加上一个下划线才27个数据。
首先2个单调队列肯定比前者非常快的
然后是冒泡排序，因为数据的关系，再加上常数因子小，冒泡其实也很优秀。堆的复杂度虽然很低，但是常数因子很大，在27的数据面前体现不了作用的。
有点真是吃力不讨好的感觉。编译通过...
├ 测试数据 01：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
prince_hao LV 10 @ 2009-10-11 14:46:47
队列好强大！
Goodhao
LV 10
@ 2018-08-01 13:54:30
