64 条题解

• @ 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;
}
``````
• @ 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;
}

求大家帮忙看看，帮忙测试下数据 我考虑了只有一种字母的情况 但不知道考虑得对不对 求大家看看有什么会出错的数据 谢谢！

``````
• @ 2016-09-04 14:26:35

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

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

这个 没处理不合并的+1

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

太简单

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

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

如果样例1是这样:

A-0

B-10

C-11

D-101

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

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

传说中的脑精急转弯- -

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

html://red fgfg

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

2次过

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

第二次 AC

未优化的哈夫曼即可

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

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

编译通过...

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

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

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

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

贪心

怎么写着动态规划

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

和楼下一样的杯具……

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

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

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

太BT了，数据只有1个

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

我也经历了

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

├ 标准行输出 208..

├ 错误行输出 40 7..

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

详情见lxxxxxxxxxxxxx。。。

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

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

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

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

orzLX的牛：

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

├ 标准行输出 208..

├ 错误行输出 40 7..

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

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

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

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

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

但是这里我们需要吗？

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

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

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

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

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

编译通过...

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

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

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

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

为什么我的错误

是编译通过...

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

├ 标准行输出 208..

├ 错误行输出 40 7..

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

• @ 2009-10-11 14:46:47

队列好强大！

ID
1079

6

(无)

1432

413

29%

5