今天写了下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) 编辑 收藏 引用 所属分类:
学习笔记