xiaoguozi's Blog
Pay it forword - 我并不觉的自豪,我所尝试的事情都失败了······习惯原本生活的人不容易改变,就算现状很糟,他们也很难改变,在过程中,他们还是放弃了······他们一放弃,大家就都是输家······让爱传出去,很困难,也无法预料,人们需要更细心的观察别人,要随时注意才能保护别人,因为他们未必知道自己要什么·····

今天写了下http://acm.pku.edu.cn/JudgeOnline/problem?id=1451
两份代码在vc下ac,用g++交RE...
如下:

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <string>
  4 #include <vector>
  5 
  6 using namespace std;
  7 
  8 int const NUM=26;
  9 vector< vector<char> >vec;
 10 struct Node
 11 {
 12     string ss;
 13     int pro;
 14     bool operator<(const Node& c)const{
 15         if(pro!=c.pro)return pro>c.pro;
 16         return ss<c.ss;
 17     };
 18     Node(string m="",int p=0):ss(m),pro(p){};
 19 };
 20 class _Trie
 21 {
 22 public:
 23     _Trie():val(0){
 24         for(int i=0;i<NUM;i++)next[i]=NULL;
 25     }
 26     ~_Trie(){
 27         for(int i=0;i<NUM;i++)delete next[i];
 28     }
 29     _Trie* next[NUM];
 30     int val;
 31 };
 32 Node ans[505];
 33 string ss;
 34 void dfs(_Trie* now,int level,string sm)
 35 {
 36     if(ss[level]=='1')return;
 37     string mm=sm;
 38     for(int i=0;i<vec[ss[level]-48].size();i++){
 39         _Trie* p=now->next[vec[ss[level]-48][i]-'A'];
 40         if(p!=NULL){
 41             mm+=(vec[ss[level]-48][i]+32);
 42             if(p->val>ans[level+1].pro&&level+1<505){
 43                 ans[level+1].pro=p->val;
 44                 ans[level+1].ss=mm;
 45             }
 46             else if(p->val==ans[level+1].pro){
 47                 if(ans[level+1].ss>mm){
 48                     ans[level+1].ss=mm;
 49                 }
 50             }
 51             dfs(p,level+1,mm);
 52             mm=sm;
 53         }
 54     }
 55     return;
 56 }
 57 int main()
 58 {
 59     vec.resize(29);
 60     vec[2].push_back('A'),vec[2].push_back('B'),vec[2].push_back('C');
 61     vec[3].push_back('D'),vec[3].push_back('E'),vec[3].push_back('F');
 62     vec[4].push_back('G'),vec[4].push_back('H'),vec[4].push_back('I');
 63     vec[5].push_back('J'),vec[5].push_back('K'),vec[5].push_back('L');
 64     vec[6].push_back('M'),vec[6].push_back('N'),vec[6].push_back('O');
 65     vec[7].push_back('P'),vec[7].push_back('Q'),vec[7].push_back('R'),vec[7].push_back('S');
 66     vec[8].push_back('T'),vec[8].push_back('U'),vec[8].push_back('V');
 67     vec[9].push_back('W'),vec[9].push_back('X'),vec[9].push_back('Y'),vec[9].push_back('Z');
 68     int T;
 69     cin>>T;
 70     for(int r=1;r<=T;r++){
 71         _Trie root;
 72         int n;
 73         cin>>n;
 74         string str;
 75         int pro;
 76         while(n--){
 77             _Trie* point=&root;
 78             cin>>str>>pro;
 79             for(int i=0;i<str.size();++i){        
 80                 if(!point->next[str[i]-'a'])
 81                     point->next[str[i]-'a']=new _Trie;                
 82                 point=point->next[str[i]-'a'];
 83                 point->val+=pro;
 84             }
 85         }
 86         cout<<"Scenario #"<<r<<":\n";
 87         cin>>n;
 88         while(n--){
 89             memset(ans,0,sizeof(ans));
 90             cin>>ss;
 91             int cnt=0;
 92             for(int i=0;i<ss.size();i++){
 93                 if(ss[i]=='1')break;
 94                 else cnt++;
 95             }
 96             _Trie* now=&root;
 97             dfs(now,0,"");
 98             sort(ans+1,ans+cnt+1);
 99             for(int i=0;i<cnt;++i){
100                 if(ans[i+1].pro!=0)cout<<ans[i+1].ss<<endl;
101                 else cout<<"MANUALLY"<<endl;
102             }
103             cout<<endl;
104         }    
105         cout<<endl;
106     }
107     return 0;
108 }
109 
经过两个多小时周折,终于在G++下也ac......聪明的你...能否改改...同样也能在G++下ac...
ps:绝对是一个挑战...至少忍耐力会上一个台阶...(我几乎已崩溃,没找出错误,我在G++下
1 if(p->val>ans[level+1].pro&&level+1<505){
2                 ans[level+1].pro=p->val;
3                 ans[level+1].ss=mm;
4             }
5             else if(p->val==ans[level+1].pro){
6                 if(ans[level+1].ss>mm){
7                     ans[level+1].ss=mm;
8                 }
9             }
ans[level+1].ss=mm,跳出"程序访问违例(段异常)",
改完ac的acmers留个言...^_^,值得挑战...
原因分析:是memset时出了问题...不能对本身有构造函数的类或类成员中有构造函数的类成员memset..本例就是
string出了问题...
posted on 2008-08-15 16:33 小果子 阅读(317) 评论(0)  编辑 收藏 引用 所属分类: 学习笔记

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理